¿Cuál es la diferencia entre un bucle, un ciclo y componentes fuertemente conectados en Teoría de Grafos?

Question

¿Qué gráfico es/contiene un ciclo? ¿bucle? ¿componente fuertemente conectado?

Creo que lo siguiente es correcto con respecto a los gráficos anteriores:

• todos los ciclos son bucles
• todos los gráficos contienen ciclos, pero $G_3$ tiene dos ciclos: $\{(a,b), (b,c)\}$ y $\{(a,b),(b,c),(c,a)\}$?
• todos los gráficos se consideran fuertemente conectados?

Pero si todos los gráficos anteriores se consideran fuertemente conectados y todos contienen ciclos, entonces ¿cuál es la diferencia entre un ciclo y un componente fuertemente conectado?

Actualización:

• Un ciclo es un camino simplemente cerrado $v_1, ..., v_k, v_1$ con $v_1, ..., v_k$ todos distintos, y $k\geq3$
• Un ciclo es un camino cerrado. Es decir, comenzamos y terminamos en el mismo vértice. En el medio, no viajamos a ningún vértice dos veces.
• Se dice que un gráfico es fuertemente conectado si todos los vértices son alcanzables desde cualquier otro vértice.

Para completar, agregué un gráfico $G_0$ con un bucle real:

• $G_0$: Este es un gráfico dirigido con un bucle ya que hay un borde que va desde el vértice $a$ hacia sí mismo.
• $G_1$: Este es un gráfico dirigido conectado con un ciclo, y este gráfico también es un componente fuertemente conectado. Este NO es un gráfico simple porque tiene un par de vértices con bordes que van en ambas direcciones entre sí.
• $G_2$: Este es un gráfico dirigido simple-conectado con un ciclo simple.
• $G_3$: Este es un gráfico dirigido conectado con múltiples componentes fuertemente conectados.

Answer 1

Un bucle se define comúnmente como un borde (o borde dirigido en el caso de un digrafo) con ambos extremos en el mismo vértice. (Por ejemplo de $a$ a sí mismo). Aunque los bucles son ciclos, no todos los ciclos son bucles. De hecho, ninguno de los digrafos anteriores tiene bucles.

Los ciclos suelen definirse como caminos cerrados que no repiten bordes ni vértices excepto el vértice de inicio y final. Esta definición generalmente permite ciclos de longitud uno (bucles) y ciclos de longitud dos (bordes paralelos).

Observa que los ciclos (y caminos) no hacen ninguna referencia a la orientación de los bordes en cuestión. Los ciclos dirigidos (y caminos dirigidos) solo pueden viajar en la dirección "hacia adelante" de los bordes. En particular, eso implica que $G_3$ mostrado arriba tiene un tercer ciclo, $(\color{blue}{(a,b)},(b,c),(c,a))$ donde $\color{blue}{(a,b)}$ se refiere a la arista que va de $b$ a $a$.

Técnicamente, todos los grafos anteriores excepto $G_2$ son multigrafos dirigidos ya que en cada uno hay bordes paralelos. Aunque en grafos simples (grafos sin bucles ni bordes paralelos) todos los ciclos tendrán una longitud de al menos $3$, un ciclo en un multigrafo puede tener una longitud más corta. Por lo general, en los multigrafos preferimos dar etiquetas específicas a las aristas para poder referirnos a ellas sin ambigüedad.

En cuanto a ser fuertemente conectados, sí, todos ellos lo son y tu definición es correcta.

---

Tu pregunta adicional, "¿cuál es la diferencia entre un ciclo y un componente conectado?"

El grafo anterior contiene un ciclo (aunque no un ciclo dirigido) pero no es fuertemente conectado.

Se puede demostrar que si un multigrafo dirigido es fuertemente conectado, entonces contiene un ciclo (realiza un recorrido dirigido desde un vértice $v$ hasta $u$, luego un recorrido dirigido desde $u$ hasta $v$. Cualquier recorrido cerrado contiene un ciclo).

También se puede demostrar que si tienes un ciclo dirigido, será parte de un componente fuertemente conectado (aunque no necesariamente será todo el componente, ni todo el grafo necesariamente será fuertemente conectado).