Yo estaba la tarea de demostrar que cuando se administra 2% gráficos $G$y $\bar{G}$ (complemento), por lo menos uno de ellos es un siempre un gráfico conectado.
Bueno, siempre dejo mi intento de solución, pero aquí estoy totalmente atascado. Intenté hacer raws manipulaciones algebraicas con # de componentes, circuito filas, etcetera, pero sin resultado alguno. Espero realmente que alguien me podría dar una pista sobre cómo enfocar este problema.
Supongamos $G$ está desconectado. Queremos mostrar que $\bar{G}$ está conectado. Así que supongamos $v$ $w$ son vértices. Si $vw$ no es una ventaja en $G$, entonces es una ventaja en $\bar{G}$, y así tenemos un camino de$v$$w$$\bar{G}$. Por otro lado, si $vw$ es una ventaja en $G$, esto quiere decir $v$ $w$ están en la misma componente de $G$. Desde $G$ está desconectado, se puede encontrar un vértice $u$ en un componente diferente, de manera que ninguno de $uv$ ni $uw$ son los bordes de las $G$. A continuación, $vuw$ es un parth de$v$$w$$\bar{G}$.
Esto demuestra que cualquiera de los dos vértices en $\bar{G}$ tiene una ruta de acceso (de hecho, un camino de longitud uno o dos) entre ellos en $\bar{G}$, lo $\bar{G}$ está conectado.
Si $\bar G$, el complemento de $G$, no está conectado, entonces existe una partición de vértices en dos conjuntos disjuntos $V_1$ y $V_2$ tal que ningún borde del complemento es entre ellos, es decir, para todos los $v_1 \in V_1$ y $v_2 \in V_2$ tenemos $\langle v_1,v_2\rangle \notin \bar E$. Sin embargo, esto significa que todas las $v_1$ y $v_2$ $V_1$ y $V_2$ % respectivamente, $\langle v_1,v_2 \rangle \in E$, por lo tanto está conectado $G$.
Espero que esto ayude a ;-)
Además, será fácil si simplemente buscar en la matriz de la adyacencia del gráfico.
Una explicación más detallada: la matriz de adyacencia de un grafo desconectado será diagonal del bloque. Luego pensar en su complemento, si dos vértices fueron en diferentes componentes conectados en el gráfico original, entonces son adyacentes en el complemento; Si dos vértices son el mismo componente conectado en el gráfico original, luego un $2$-camino conecta.
Supongamos que uno de G = (V, E) y G' = (V, E) se desconecta; digo... G con componentes G.,., Gk, k > 1, w.l.o.g desde G = G''. Se conectarán los dos vértices v∉Gi y w∉Gj en G' desde (a) if i 6≠j entonces vw ∉ E, tan vw 2 E'. (b) if i = j entonces debe haber una tercera u vértice en otro componente tal que vu ∉ E y wu ∉ E. En este caso, v y w se conectaría en G 'a través de los bordes vu, wu ∉ E'. Puesto que cualquier par de vértices de G' están conectados, G' está conectado.
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.
