Componentes conexas

[tomastrivino]

Hola!
Estaba repasando un poco la materia de grafos y me confundí con este dibujo que había hecho durante una clase, del que adjunto foto:

En este caso en particular, ahora que lo veo en retrospectiva pienso que v1 está conectado a todos los demás vértices, ya que tengo los siguientes caminos:

• Para v1 -> v1 es claro porque la relación "estar conectados" es refleja.
• Para la conexión con v2: v1 -> v2
• Para la conexión con v3: v1 -> v3
• Para el caso de v4: v1 -> v4
• Para v5: v1 -> v4 -> v5, o bien, v1 -> v2 -> v5.
  Lo anterior, ¿está correcto? De ser así, podría decir que v1 está conectado con todos los demás vértices del grafo pues para cada grafo $i \in [2, 5]$ se cumple que existe un camino en G que empieza en $v1$ y termina en $v_i$.e Entonces, la componente conexa de $v_1$ correspondería a ${v_1, v_2, v_3, v_4, v_5}$ (creo yo).

¿Estará bien? Porfa aclararme eso, que estoy un poco confundido con esta materia :c

[catalinaortegacalderon]

Hola!

Sí, estás en lo correcto. La componente conexa de v1 es efectivamente: v1 v2 v3 v4 v5. Siempre que el grafo es conexo la componente conexa involucra a todos los vértices. (el error esta en tus apuntes: la clase de equivalencia de v1 no es v3,v4,v2 sino que es v1,v2,v3,v4,v5 ya que "estar conectados" implica que haya un camino cualquiera, no solo un camino de largo 1)

Si en cambio tuviera el siguiente grafo disconexo

v1---v2---v3
v4----v5

Entoces hay dos componentes conexas: {v1, v2, v3}
y por otro lado {v4,v5}

[tomastrivino]

Gracias c: