¿Qué es un grafo acíclico dirigido (DAG)?

Question

Estoy leyendo este enlace en Wikipedia En él se establece la siguiente definición para un DAG.

Definición: A DAG es un grafo finito y dirigido sin ciclos dirigidos.

La lectura de esta definición me hace pensar que el dígrafo de abajo sería un DAG ya que aquí no hay ciclos dirigidos (hay ciclos del grafo subyacente pero no hay ciclos dirigidos).

Sin embargo, todas las imágenes de Wikipedia muestran ejemplos de DAG con flechas que apuntan en la misma dirección. Por lo tanto, creo que estoy interpretando mal esta definición. En particular, ¿por qué la definición menciona más adelante que una definición equivalente es que debe tener un ordenamiento topológico tal que "cada arista está dirigida de anterior a posterior en la secuencia"? La lectura de la definición anterior me llevaría a creer que el grafo anterior es un DAG, pero luego la definición equivalente me haría pensar lo contrario.

Answer 1

El gráfico que muestra es un DAG.

Es convencional a dibujar DAGs con todas las flechas que van aproximadamente en la misma dirección, porque eso suele dar una intuición más clara sobre lo que está pasando en el gráfico.

Pero recuerde que las ubicaciones y direcciones son no forma parte de la definición formal de un gráfico -- son sólo características incidentales de la particular dibujo en el gráfico que estás viendo, y sería el el mismo gráfico si dibujaras los vértices en diferentes lugares del papel.

(Incluso en tu dibujo, todos los bordes van en dirección sureste, o al menos más al sureste que al noroeste, por lo que estás siguiendo la convención).

En particular, ¿por qué la definición menciona más tarde una definición equivalente es que debe tener un ordenamiento topológico tal que "cada arista se dirige de anterior a posterior en la secuencia"?

Porque es otra forma de definir la misma clase de grafos, y a veces (pero no siempre) una forma más productiva de pensar en ellos. Deberías poder demostrar que los grafos finitos dirigidos que no tienen ciclos dirigidos son exactamente los mismos que los grafos finitos dirigidos que tienen un ordenamiento topológico.

Answer 2

El gráfico dado es efectivamente un DAG,

La definición equivalente dice que un gráfico $(V, E)$ es un dag si y sólo si se puede encontrar un orden total que extienda el orden dado por $E$ . En términos más sencillos, dejemos que $u_1, \ldots, u_n$ sean los elementos de $V$ (los vértices), entonces $(V, E)$ es un dag si y sólo si puedes encontrar una orden $<$ de manera que si $(u_i, u_k)\in E$ entonces $u_i < u_k$ .

Answer 3

Las dos respuestas hasta ahora afirman que lo que has dibujado es un DAG. Sin embargo, no es un DAG según una definición de uso común, porque tiene múltiples aristas entre los dos vértices más a la izquierda. Es común definir un grafo dirigido como un par $(V,E)$ donde $V$ es un conjunto, llamado los vértices, y $E \subseteq V \times V$ es un conjunto, llamado los bordes (excluyendo $(v,v)$ para todos $v \in V$ ). Un DAG es entonces un tipo particular de grafo dirigido (que no tiene ciclos dirigidos). En particular, dado que $E$ es un conjunto, no hay forma de expresar que hay dos aristas con los mismos vértices iniciales y finales (eso requeriría un multiset ). Por lo tanto, yo llamaría a lo que has dibujado un "multigrafo acíclico dirigido". Sin embargo, el razonamiento de por qué la forma de dibujarlo no afecta a si es un DAG, como se explica en la respuesta de Henning Makholm, parece haber respondido a la pregunta que realmente querías hacer.

Answer 4

Se pueden definir las cosas de muchas maneras como el gráfico acíclico dirigido en: https://en.m.wikipedia.org/wiki/Magma_(álgebra) bajo tipos de espectáculos de magma. Usted puede definir un gráfico de múltiples maneras, Por lo tanto, cualquier tipo de gráfico tiene múltiples definiciones. Su dibujo es un DAG bajo una definición de: un gráfico, cuyos vértices carecen de un gráfico de ciclo, cuando se sigue el camino dirigido ordenado por dirección.