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

Question

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

Sólo puedo decir visualmente que este grafo es acíclico porque no hay ningún camino en el grafo en el que el vértice inicial sea igual al vértice final. Pero, ¿es esto realmente una razón que puedes decir si alguien te pregunta?

¿Existe tal vez algún tipo de regla / fórmula donde se pueda determinar esto comparando la cantidad de vértices con la cantidad de aristas?

Tenemos aquí $6$ vértices y $10$ bordes.

Espero que me podáis ayudar porque si alguien me pregunta por qué este grafo dirigido o en general un grafo dirigido es acíclico, yo me pondría así aquí y no me siento bien.

Answer 1

Una aproximación más general a esto viene dada por clasificación topológica . En particular, existe una ordenación topológica si y sólo si el grafo es un grafo acíclico dirigido. Los "algoritmos" descritos en las otras respuestas realizan efectivamente una ordenación topológica, en el sentido de que eliminan repetidamente los vértices sin aristas de entrada/salida.

Por ejemplo, una ordenación topológica de su grafo viene dada por $A,B,C,D,E,F$ y si se redibuja el gráfico de forma que los vértices anteriores estén más altos que los posteriores (no necesariamente de forma lineal) se puede ver que no hay aristas "hacia arriba", por lo que no puede haber ningún ciclo.

Answer 2

Paso 1. Como $A$ no tiene ningún grado, no puede formar parte de ningún ciclo. Así que elimínalo. Ahora tenemos el gráfico $G_1$ .

Paso 2. Como $C$ no tiene ningún indegree no puede ser parte de ningún ciclo (en este nuevo gráfico $G_1$ ). Así que quítalo. Obtenemos $G_2$

Paso 3. Ahora en $G_2$ nodos $B$ y $D$ no tienen ningún grado, así que elimínalos.

Answer 3

Un ciclo dirigido no puede implicar $F$ ya que ninguna flecha parte de $F$ . Así que puedes borrar $F$ y todas las flechas que caen en $F$ del gráfico. El grafo original es acíclico si y sólo si el nuevo grafo lo es.

Repita el procedimiento con $E$ ahora. Entonces con $D$ , entonces con $B$ y $C$ .

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

Answer 4

Como indica la respuesta de B. Mehta, se puede resolver este problema en el caso general mediante una topo-clasificación. Aquí tienes una guía rápida de cómo hacerlo:

• Comienza coloreando todos los nodos de color verde.

Ahora haga los siguientes pasos para cada nodo :

• Si el nodo está en rojo, sáltalo. Ya hemos comprobado los ciclos.
• Si el nodo es amarillo, tienes un ciclo. Hemos terminado.
• El nodo debe ser verde. Recolócalo en amarillo.
• Vuelva a iniciar este algoritmo para todos los vecinos salientes del nodo actual.
• Cuando estén todos hechos, colorea este nodo de rojo.

Una vez hecho esto, o bien has encontrado un nodo amarillo, o bien no lo has hecho. Si no lo hiciste, no hay ciclo. Si lo hiciste, entonces hay un ciclo, y contiene el nodo amarillo.

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

A becomes yellow. We must now look at B, C, D next.
  B becomes yellow. We must look at E next.
    E becomes yellow. We must look at F next.
      F becomes yellow.
      F becomes red. 
    E becomes red.
  B becomes red.
  C becomes yellow. We must look at F next.
    F is red, so we skip it.
  C becomes red.
  D becomes yellow. We must look at E and F next.
    But they are both red, so skip them.
  D becomes red.
  A becomes red.
B, C, D, E and F are all red, so we're done, and the graph is acyclic.

Ahora supongamos que tenemos A -> B -> C -> A. Todos son verdes.

A becomes yellow; we have to look at B next.
  B becomes yellow; we have to look at C next.
    C becomes yellow; we have to look at A next.
      A is yellow. There is a cycle.

¿Tiene sentido?

Algoritmo de bonificación: Supongamos que el grafo es acílico. Cuando colorees 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 eliminas los nodos del grafo en ese orden, tendrías nunca eliminar un nodo que tenía un borde de salida .

Por eso se llama "ordenación topológica". Nos permite encontrar un orden en un DAG en el que una flecha que apunta de A a B significa que "la tarea A no puede hacerse hasta que la tarea B esté hecha". En nuestro ejemplo, F tiene que ser la primera en hacerse, y efectivamente, lo es. Quitamos F del gráfico, y ahora hay que hacer E a continuación. Quitamos E del gráfico y ahora B, C o D son igualmente buenas, así que podemos hacerlas, y entonces debemos hacer A en último lugar.

Answer 5

Sólo puedo decir visualmente que este grafo es acíclico porque no hay ningún camino en el grafo en el que el vértice inicial sea igual al vértice final. Pero, ¿es esto realmente una razón que puedes decir si alguien te pregunta?

No si no puedes demostrarlo, pero en tu ejemplo particular, puedes hacerlo muy fácilmente, y eso hace que sea un enfoque válido para usar aquí.

Mueve F un poco hacia abajo. Una vez hecho esto, todas las aristas y, por tanto, todos los caminos (no vacíos) van de arriba a abajo, por lo que, trivialmente, no puede haber ningún camino de un vértice a sí mismo.