4 votos

El complemento de un gráfico G

Tengo un problema de tarea en el que tengo un gráfico $G$ y tengo la tarea de demostrar que al menos uno de $G$ y $G$ complemento está conectado. Sin embargo, no tengo claro el significado exacto de $G$ complemento.

Por ejemplo, imaginemos que tengo un gráfico desconectado con cuatro vértices $(V_1, V_2, V_3, \text{and } V_4)$ . Si los bordes forman una especie de caja en la que el borde inferior queda desconectado, ¿podría $G$ complemento tienen ese borde rellenado junto con los bordes transversales también? Además, ¿el $G$ contienen todas las aristas de $G$ o sólo los bordes no contenidos en $G$ ? Gracias por tomarse el tiempo de leer.

3voto

Lissome Puntos 31

El complemento es el gráfico con los mismos vértices y las aristas que faltan.

Sugerencia para el problema Si $G$ está conectado, ya está hecho. Si $G$ está desconectado, dejemos que $u, v$ sean vértices en dos componentes diferentes de $G$ .

Entonces $uv$ es una arista en el complemento de $G$ . Además, si $w$ es cualquier otro vértice en $G$ , entonces al menos uno de $uw, vw$ tiene que ser un borde en el complemento. De esta manera se puede coonectar $w$ a ambos $u$ y $v$ en el complemento, y a partir de aquí se puede demostrar que el complemento está conectado.

0voto

user2566092 Puntos 19546

$G$ tiene exactamente las aristas no contenidas en $G$ y $G$ tiene los mismos vértices que $G$ .

0voto

Jaded Puntos 593

Dado un gráfico $G=(V,E)$ su gráfico complementario es precisamente el gráfico $(V,V^{(2)}-E)$ , donde $V^{(2)}$ consiste en todos los subconjuntos de 2 de $V$ . Por lo tanto, el gráfico del complemento tiene el mismo conjunto de vértices que $G$ y su conjunto de aristas está formado exactamente por todas las aristas del grafo completo $K_n$ que no están en $G$ , donde $n=|V|$ es el número de vértices de $G$ .

Por lo tanto, el gráfico del complemento de $G=(V,E)$ consiste exactamente en $\binom{n}{2} - |E|$ aristas, y el número total de aristas en $G$ y en su complemento sumará exactamente el número de aristas del grafo completo $K_n$ es decir, a $\binom{n}{2}$ .

Para demostrar que al menos uno de $G$ o su complemento $\overline{G}$ está conectado, supongamos que $G$ no está conectado y tiene componentes conectados $G_1,G_2,\ldots$ . Entonces, en el gráfico del complemento cada vértice de $G_i$ está conectada a todos los vértices de $G_j$ , siempre que $i \ne j$ . Así, $\overline{G}$ está conectado.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X