¿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 esta realmente una razón que puedas dar si alguien te pregunta?

¿Existe tal vez algún tipo de regla o 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 diría algo así aquí y no me siento bien al respecto.

Answer 1

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

Por ejemplo, un ordenamiento topológico de tu grafo es dado por $A,B,C,D,E,F$ y si reorganizas el grafo de manera que los vértices anteriores son más altos que los posteriores (no necesariamente de manera 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 ser parte de ningún ciclo. Así que remuévalo. Ahora tenemos el grafo $G_1$.

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

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

Answer 3

Un ciclo dirigido no puede incluir a $F$ ya que ninguna flecha comienza en $F$. Por lo tanto, puedes eliminar $F$ y todas las flechas que llegan a $F$ del grafo. El grafo original es acíclico si y solo si el nuevo grafo lo es.

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

Al final, solo queda $A$, sin aristas, lo que es un grafo 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:

• Comienza coloreando cada nodo de verde.

Ahora haz los siguientes pasos para cada nodo:

• Si el nodo es rojo, omítelo. Ya lo hemos revisado para ciclos.
• Si el nodo es amarillo, tienes un ciclo. Estamos listos.
• 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 te encuentras con un nodo amarillo, o no. Si no lo hiciste, no hay ciclo. Si lo hiciste, entonces hay un ciclo, y contiene el nodo amarillo.

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

A se vuelve amarillo. Ahora debemos ver B, C, D a continuación.
  B se vuelve amarillo. Ahora debemos ver E a continuación.
    E se vuelve amarillo. Ahora debemos ver F a continuación.
      F se vuelve amarillo.
      F se vuelve rojo.
    E se vuelve rojo.
  B se vuelve rojo.
  C se vuelve amarillo. Ahora debemos ver F a continuación.
    F es rojo, así que lo omitimos.
  C se vuelve rojo.
  D se vuelve amarillo. Ahora debemos ver 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 rojos, 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 ver a B a continuación.
  B se vuelve amarillo; debemos ver a C a continuación.
    C se vuelve amarillo; debemos ver a A a continuación.
      A está amarillo. Hay un ciclo.

¿Tiene sentido?

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

Por eso esto se llama "ordenamiento topológico". Nos permite encontrar un orden en un DAG donde una flecha que va de A a B significa "la tarea A no se puede hacer hasta que la tarea B esté hecha". En nuestro ejemplo, F tiene que hacerse primero, y efectivamente lo está. Eliminamos F del grafo, y ahora E tiene que hacerse a continuación. Eliminamos E del grafo y ahora B, C o D son igualmente buenos para hacerlos, y luego debemos hacer A por último.

Answer 5

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

No si no puedes probarlo, pero en tu ejemplo 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, todas las aristas y, por lo tanto, todos los caminos (no vacíos) van de arriba abajo, por lo que trivialmente, no puede haber un camino desde un vértice hasta sí mismo.