Grafo acíclico dirigido

Grafo acíclico dirigido
Un DAG simple.

En ciencias de la computación y matemáticas un grafo acíclico dirigido (o gráfico dirigido acíclico) conocido como DAG por sus siglas en inglés, es un grafo dirigido que no tiene ciclos; esto significa que para cada vértice v, no hay un camino directo que empiece y termine en v. Los DAG aparecen en modelos donde no tiene sentido que un vértice tenga un camino directo a él mismo; por ejemplo, si un arco u→v indica que v es parte de u, crear un ciclo v→u indicaría que u es subconjunto de sí mismo y de v, lo cual es imposible. Informalmente un DAG "fluye" en solo una dirección.

Cada DAG da lugar a un ordenamiento parcial ≤ sobre sus vértices, donde u ≤ v exactamente cuando existe un camino directo desde u a v. Muchos DAG pueden generar el mismo ordenamiento parcial de los vértices siendo el de menor número de arcos denominado la reducción transitiva y el que mayor número de arcos la Clausura transitiva. En particular, la clausura transitiva es el orden de accesibilidad ≤.

Terminología

Una fuente es un vértice sin flujos (relaciones) de entrada, mientras que un sifón o sumidero es un vértice sin flujos (relaciones) de salida.

Un DAG finito tiene por lo menos una fuente y un sifón.

La profundidad de un vértice, en un DAG finito, es la longitud del camino más largo que existe desde una fuente a dicho vértice, la altura de un vértice es la longitud más larga del camino que exista desde el vértice a un sifón.

La longitud de una DAG finito es la longitud (número de arcos) del camino directo más largo. Dicha longitud es igual a la máxima altura de todas las fuentes e igual a la máxima profundidad de todas los sifones.

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Alineamiento estructural — de tiorredoxinas del ser humano y de la mosca Drosophila melanogaster. Las proteínas se muestran como cintas, con l …   Wikipedia Español

  • GEGL — El texto que sigue es una traducción defectuosa o incompleta. Si quieres colaborar con Wikipedia, busca el artículo original y mejora o finaliza esta traducción. Puedes dar aviso al autor principal del artículo pegando el siguiente código en su… …   Wikipedia Español

  • Mercurial — Desarrollador Matt Mackall http://mercurial.selenic.com/ …   Wikipedia Español

  • Red bayesiana — Una Red Bayesiana consta de dos componentes. El primero de ellos, más cualitativo, está representado por un grafo acíclico dirigido donde los nodos (el conjunto finito ) son variables aleatorias del problema, y los arcos ( ) indican relaciones… …   Enciclopedia Universal

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Ordenación topológica — Una ordenación topológica de un grafo acíclico G dirigido es una ordenación lineal de todos los nodos de G que conserva la unión entre vértices del grafo G original. La condición que el grafo no contenga ciclos es importante, ya que no se puede… …   Wikipedia Español

  • Red bayesiana — Saltar a navegación, búsqueda Una red bayesiana, o red de creencia, es un modelo probabilístico multivariado que relaciona un conjunto de variables aleatorias mediante un grafo dirigido que indica explícitamente influencia causal. Gracias a su… …   Wikipedia Español

  • Problema del camino más largo — Saltar a navegación, búsqueda En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en… …   Wikipedia Español

  • Teoría del orden — La teoría del orden es una rama de la matemática que estudia varias clases de relaciones binarias que capturan la noción intuitiva del orden matemático. Este artículo da una introducción detallada a este campo e incluye algunas de las… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”