Sea G = (V; E) un grafo. Demostrar que si para cada partición de V en subconjuntos no vacíos, V1 y V2, hay una arista con un extremo en V1 y otro en V2 entonces G es un grafo conexo.
Respuesta
¿Demasiados anuncios?
Brian Yao
Puntos
111
Una forma de resolver el problema es demostrando el contrapositivo: si $G$ no es un grafo conexo, entonces existe una partición de $V$ en subconjuntos no vacíos $V_1$ y $V_2$ tal que ninguna arista tenga una arista en $V_1$ y un borde en $V_2$ . Recordemos que la definición de un grafo conexo es aquella en la que hay un camino entre cada par de vértices. Por lo tanto, empezamos asumiendo que $G$ contiene un par de vértices no conectados por un camino, lo que hace que $G$ no están conectados por definición.
Supongamos que existe $s,t \in V$ de manera que no exista ningún camino entre $s$ y $t$ . A continuación, considere el componente conectado $C_s$ que contiene $s$ y el componente conectado $C_t$ que contiene $t$ .
Pista 1: Demuestra que $C_s \neq C_t$ y por lo tanto, en particular, no hay ninguna arista con un punto final en $C_s$ y el otro en $C_t$ .
Pista 2: Denota un conjunto de vértices $$V' = \{v \mid v \text{ is a vertex in any connected component other than $ C_s $ or $ C_t $}\}$$ Entonces considera la partición de vértices $$V_1 = \{v \mid v \text{ is a vertex in } C_s\} \cup V'$$ $$V_2 = \{v \mid v \text{ is a vertex in $ C_t $}\}$$ Demuestre que no puede existir una arista con un extremo en $V_1$ y el otro en $V_2$ completando así la prueba.
