¿Cómo razonas correctamente que este grafo dirigido es acíclico?

Question

¿Cómo puedes razonar correctamente que este grafo dirigido es acíclico?

Solo puedo decir visualmente que este grafo es acíclico porque no hay un solo camino en el grafo donde el vértice inicial sea igual al vértice final. Pero ¿es esto realmente una razón que puedas decir si alguien te pregunta?

¿Quizás hay alguna regla / fórmula donde puedas determinar esto comparando la cantidad de vértices con la cantidad de aristas?

Aquí tenemos $6$ vértices y $10$ aristas.

Espero que puedas darme algo de ayuda porque si alguien me pregunta por qué este grafo dirigido o en general un grafo dirigido es acíclico, yo respondería como aquí y no me siento bien al respecto.

Answer 1

Una aproximación más general a esto se da mediante ordenación topológica. En particular, una ordenación topológica existe si y solo si el grafo es un grafo dirigido acíclico. Los 'algoritmos' descritos en las otras respuestas realizan efectivamente una ordenación topológica, en el sentido de que eliminan repetidamente vértices sin aristas entrantes/salientes.

Por ejemplo, una ordenación topológica de tu gráfico es dada por $A,B,C,D,E,F$ y si redes el gráfico de manera que los vértices anteriores estén más altos que los posteriores (no necesariamente de forma lineal) puedes ver que no hay aristas 'hacia arriba', por lo que no puede haber ciclo.

Answer 2

Paso 1. Dado que $A$ no tiene grado de entrada, no puede formar parte de ningún ciclo. Entonces, retíralo. Ahora tenemos el grafo $G_1$.

Paso 2. Dado que $C$ no tiene grado de entrada, no puede formar parte de ningún ciclo (en este nuevo grafo $G_1$). Así que retíralo. Obtenemos $G_2$.

Paso 3. Ahora en $G_2$ los nodos $B$ y $D$ no tienen grado de entrada, así que retíralos.

Answer 3

Un ciclo dirigido no puede involucrar a $F$ ya que no hay flechas que comiencen desde $F$. Por lo tanto, puedes eliminar $F$ y todas las flechas que lleguen a $F$ del gráfico. El gráfico original es acíclico si y solo si el nuevo gráfico lo es.

Repite el procedimiento con $E$ ahora. Luego con $D$, luego con $B$ y $C.

Al final, solo queda $A$, sin aristas, lo que es un gráfico acíclico.

Answer 4

Como indica la respuesta de B. Mehta, puedes resolver este problema en el caso general haciendo un ordenamiento topológico. Aquí tienes una guía rápida de cómo hacerlo:

• Empieza coloreando cada nodo de verde.

Ahora sigue los siguientes pasos para cada nodo:

• Si el nodo es rojo, omítelo. Ya lo hemos revisado en busca de ciclos.
• Si el nodo es amarillo, tienes un ciclo. Hemos terminado.
• El nodo debe ser verde. Recolócalo a amarillo.
• Reinicia este algoritmo para todos los vecinos salientes del nodo actual.
• Cuando todos estén listos, colorea este nodo de rojo.

Una vez que hayas terminado, o bien encuentras un nodo amarillo o no. Si no encontraste uno, no hay ciclo. Si lo encontraste, entonces hay un ciclo y contiene al nodo amarillo.

Vamos a ver tu ejemplo. Empezamos con todo en verde. Supongamos que vamos a mirar los nodos en orden A, B, C, D, E, F.

A se vuelve amarillo. Ahora debemos mirar B, C, D a continuación.
  B se vuelve amarillo. Luego debemos mirar E a continuación.
    E se vuelve amarillo. Luego debemos mirar F a continuación.
      F se vuelve amarillo.
      F se vuelve rojo.
    E se vuelve rojo.
  B se vuelve rojo.
  C se vuelve amarillo. Luego debemos mirar F a continuación.
    F es rojo, así que lo omitimos.
  C se vuelve rojo.
  D se vuelve amarillo. Luego debemos mirar E y F a continuación.
    Pero ambos son rojos, así que los omitimos.
  D se vuelve rojo.
  A se vuelve rojo.
B, C, D, E y F están todos en rojo, así que hemos terminado y el grafo es acíclico.

Ahora supongamos que tenemos A -> B -> C -> A. Todos están en verde.

A se vuelve amarillo; debemos mirar a B a continuación.
  B se vuelve amarillo; debemos mirar a C a continuación.
    C se vuelve amarillo; debemos mirar a A a continuación.
      A está en amarillo. Hay un ciclo.

¿Tiene sentido?

Algoritmo adicional: Supongamos que el grafo es acíclico. Cuando colores un nodo de rojo, ponle un número incrementado. En nuestro ejemplo, F = 1, E = 2, B = 3, C = 4, D = 5, A = 6. Si quitas los nodos del grafo en ese orden, nunca eliminarás un nodo que tenga una arista saliente.

Por eso se llama "ordenamiento topológico". Nos permite encontrar un orden en un DAG donde una flecha apuntando de A a B significa "la tarea A no puede realizarse hasta que se haya realizado la tarea B". En nuestro ejemplo, F debe hacerse primero, y efectivamente se hace. Quitamos F del grafo, y ahora E debe hacerse a continuación. Quitamos E del grafo y ahora B, C o D son igualmente buenos para hacerse, y luego debemos hacer A por último.

Answer 5

Solo puedo decir visualmente que este grafo es acíclico porque no hay un solo camino en el grafo donde el vértice inicial sea igual al vértice final. ¿Pero es realmente una razón que puedes decir si alguien te pregunta?

Si no puedes probarlo, entonces no, pero en tu caso particular, puedes hacerlo muy fácilmente, y eso lo convierte en un enfoque válido para usar aquí.

Mueve F un poco hacia abajo. Una vez que hayas hecho eso, todos los bordes y, por lo tanto, todos los caminos (no vacíos) van de arriba hacia abajo, por lo que trivialmente, no puede haber un camino de un vértice a sí mismo.