miniatura|alt=Exemplo dun grafo acíclico dirixido.|Exemplo dun grafo acíclico dirixido. En matemáticas, en particular na teoría de grafos, e en ciencias da computación, un grafo acíclico dirixido (GAD, ou DAG polo inglés) é un grafo dirixido sen ciclos dirixidos. É dicir, consta de vértices e arestas (tamén chamadas arcos), con cada aresta dirixida dun vértice a outro, de xeito que seguir esas direccións nunca formará un ciclo pechado. Un grafo dirixido é un GAD se e só se se pode ordenar topoloxicamente, dispoñendo os vértices nunha orde linear consistente con todas as direccións das arestas. Os GAD teñen numerosas aplicacións científicas e computacionais, desde a bioloxía (evolución, árbores xenealóxicas, epidemioloxía) ata a ciencia da información (redes de citas) e a computación (planificación).

Os grafos acíclicos dirixidos tamén se chaman grafos dirixidos acíclicos ou dígrafos acíclicos.

Definicións Agás indicación contraria, as propiedades e os algoritmos descritos aquí refírense a grafos finitos sen bucles. Un grafo fórmase con vértices e arestas que conectan pares de vértices, onde os vértices poden ser calquera tipo de obxecto conectado por pares mediante arestas. No caso dun grafo dirixido, cada aresta ten unha orientación, dun vértice a outro. Un percorrido nun grafo dirixido é unha secuencia (finita ou infinita) de vértices tal que cada par consecutivo está conectado por unha aresta dirixida. Un camiño é un percorrido no que todos os vértices son distintos. Un ciclo é un percorrido no que o único vértice repetido é , é dicir, o último vértice coincide co primeiro. Un grafo acíclico dirixido é un grafo dirixido que non ten ciclos....

Propiedades matemáticas Relación de alcanzabilidade, peche transitivo e redución transitiva miniatura|dereita|alt=Un GAD.|Un GAD. A relación de alcanzabilidade dun GAD pódese formalizar como unha orde parcial sobre os seus vértices. Nesta orde parcial, dous vértices e están ordenados como exactamente cando existe un camiño dirixido de a no GAD; é dicir, cando pode acadar .. Con todo, distintos GAD poden dar lugar á mesma relación de alcanzabilidade e á mesma orde parcial.. Por exemplo, un GAD con dúas arestas e ten a mesma relación de alcanzabilidade cun GAD con tres arestas , e . Ambos os dous GAD producen a mesma orde parcial, na que os vértices se ordenan como .

Na orde parcial de alcanzabilidade permítense camiños de lonxitude cero, polo que . En cambio, o peche transitivo do GAD engade unha aresta só cando e existe un camiño dirixido de a . Non engade bucles. É o GAD co maior número de arestas coa mesma alcanzabilidade. Reciprocamente, un conxunto finito parcialmente ordenado represéntase cun vértice por elemento e cunha aresta por cada par da relación estrita . Engadir arestas tamén para produciría bucles e deixaría de dar un grafo acíclico.

miniatura|300px|alt=Diagrama de Hasse da orde parcial de inclusión de conxuntos entre os subconxuntos dun conxunto de tres elementos.|Un diagrama de Hasse que representa a orde parcial da inclusión de conxuntos (⊆) entre os subconxuntos dun conxunto de tres elementos. A redución transitiva dun GAD é o grafo co menor número de arestas que ten a mesma relación de alcanzabilidade ca o GAD. Ten unha aresta para cada par de vértices (, ) na relación de cobertura da relación de alcanzabilidade do GAD. É un subgrafo do GAD, formado descartando as arestas para as que o GAD tamén contén un camiño dirixido máis longo de a .

Como o peche transitivo, a redución transitiva está definida de forma única para os GAD. Pola contra, para un grafo dirixido que non é acíclico pode haber máis dun subgrafo mínimo coa mesma relación de alcanzabilidade.. As reducións transitivas son útiles para visualizar as ordes parciais que representan, porque teñen menos arestas cá outros grafos que representan as mesmas ordes e, por tanto, dan lugar a debuxos máis simples. Un diagrama de Hasse dunha orde parcial é un debuxo da redución transitiva no que a orientación de cada aresta se amosa colocando o vértice inicial da aresta nunha posición inferior á do vértice final..

Ordenación topolóxica miniatura|dereita|alt=Ordenación topolóxica dun grafo acíclico dirixido.|Unha ordenación topolóxica dun grafo acíclico dirixido: cada aresta vai dun punto anterior na orde (arriba á esquerda) a un posterior (abaixo á dereita). Un grafo dirixido é acíclico se e só se ten unha ordenación topolóxica.

Unha ordenación topolóxica dun grafo dirixido é unha ordenación dos seus vértices nunha secuencia, tal que para cada aresta o vértice inicial aparece antes na secuencia có vértice final. Un grafo que ten unha ordenación topolóxica non pode ter ningún ciclo, porque a aresta que entra no vértice máis temperán dun ciclo tería que estar orientada ao revés. Por tanto, todo grafo cunha ordenación topolóxica é acíclico. Reciprocamente, todo grafo acíclico dirixido ten polo menos unha ordenación topolóxica. A existencia dunha ordenación topolóxica pódese usar xa que logo como definición equivalente de grafo acíclico dirixido: son exactamente os grafos que teñen ordenacións topolóxicas.

En xeral, esta ordenación non é única; un GAD ten unha ordenación topolóxica única se e só se ten un camiño dirixido que contén todos os vértices, e nese caso a ordenación é a mesma que a orde en que os vértices aparecen no camiño..

A familia das ordenacións topolóxicas dun GAD é a mesma que a das extensións lineais da relación de alcanzabilidade do GAD,. polo que dous grafos que representen a mesma orde parcial teñen o mesmo conxunto de ordes topolóxicas.

Enumeración combinatoria O problema de enumeración de grafos de contar grafos acíclicos dirixidos foi estudado por Robinson (1973).. Véxase tamén . O número de GAD sobre vértices etiquetados, para (sen restricións sobre a orde de aparición destes números nunha ordenación topolóxica), é 1, 1, 3, 25, 543, 29281, 3781503, … . Estes números pódense calcular coa relación de recorrencia

Eric W. Weisstein conxecturou, e McKay, Royle, Wanless e Oggier (2004) demostraron, que os mesmos números contan as matrices (0,1) nas que todos os valores propios son reais positivos. A proba é bixectiva: unha matriz é unha matriz de adxacencia dun GAD se e só se é unha matriz (0,1) con todos os valores propios positivos, onde denota a matriz identidade. Como un GAD non pode ter auto-bucles, a súa matriz de adxacencia debe ter diagonal nula, polo que engadir conserva a propiedade de que todos os coeficientes da matriz son 0 ou 1., artigo 04.3.3.

Familias de grafos relacionadas miniatura|alt=Unha multiárbore.|Unha multiárbore, un GAD no que o subgrafo alcanzable desde calquera vértice induce unha árbore non dirixida (por exemplo en vermello). miniatura|alt=Unha poliárbore.|Unha poliárbore, un GAD formado orientando as arestas dunha árbore non dirixida. Unha multiárbore é un GAD no que hai como máximo un camiño dirixido entre dous vértices calquera. Equivalentemente, é un GAD no que o subgrafo alcanzable desde calquera vértice induce unha árbore non dirixida..

Unha poliárbore (tamén chamada árbore dirixida) é unha multiárbore formada orientando as arestas dunha árbore non dirixida..

Unha arborescencia é unha poliárbore formada orientando as arestas dunha árbore non dirixida afastándose dun vértice concreto, chamado raíz da arborescencia.

Problemas computacionais Ordenación topolóxica e recoñecemento A ordenación topolóxica é o problema algorítmico de atopar unha ordenación topolóxica dun GAD dado. Pódese resolver en tempo linear.Cormen et al. 2001, sección 22.4, «Topological sort», páxinas 549–552. O algoritmo de Kahn para a ordenación topolóxica constrúe a ordenación dos vértices directamente. Mantén unha lista de vértices sen arestas entrantes doutros vértices que aínda non se incluíron na ordenación parcial; inicialmente esta lista consta dos vértices sen arestas entrantes. Despois, engade repetidamente un vértice desta lista ao final da ordenación parcial e comproba se os seus veciños deben engadirse á lista. O algoritmo remata cando se procesaron todos os vértices deste xeito. Alternativamente, pódese construír unha ordenación topolóxica invertindo unha numeración en postorde dunha busca en profundidade.

Tamén é posible comprobar se un grafo dirixido dado é un GAD en tempo linear, ben tentando atopar unha ordenación topolóxica e comprobando despois para cada aresta se a ordenación resultante é válida,Para o algoritmo de ordenación topolóxica baseado na busca en profundidade, esta comprobación de validez pódese intercalar co propio algoritmo; véxase Skiena 2009, páxinas 179–181. ben, para algúns algoritmos de ordenación topolóxica, verificando que o algoritmo ordena con éxito todos os vértices sen atopar unha condición de erro.Jungnickel 2012, páxinas 50–51.

Construción a partir de grafos cíclicos Calquera grafo non dirixido se pode converter nun GAD escollendo unha orde total para os seus vértices e dirixindo cada aresta desde o extremo anterior na orde ao posterior. A orientación resultante chámase orientación acíclica. Distintas ordes totais poden dar lugar á mesma orientación acíclica, polo que un grafo de vértices pode ter menos de orientacións acíclicas. O número de orientacións acíclicas é igual a , onde é o polinomio cromático do grafo dado..

miniatura|upright=1.5|alt=Condensación dun grafo dirixido.|O grafo acíclico dirixido amarelo é a condensación do grafo dirixido azul. Fórmase contraendo cada compoñente fortemente conexa nun único vértice e omitindo as arestas internas desas compoñentes. Calquera grafo dirixido se pode converter nun GAD eliminando un conxunto de vértices de retroalimentación ou un conxunto de arestas de retroalimentación, un conxunto de vértices ou arestas (respectivamente) que toque todos os ciclos. Con todo, atopar o conxunto máis pequeno é NP-difícil.Garey-Johnson, problemas GT7 e GT8, páxinas 191–192. Un grafo dirixido arbitrario tamén se pode transformar nun GAD, chamado a súa condensación, contraendo cada unha das súas compoñentes fortemente conexas nun único supervértice.. Cando o grafo xa é acíclico, os seus conxuntos de vértices e de arestas de retroalimentación máis pequenos son baleiros, e a súa condensación é o propio grafo.

Peche transitivo e redución transitiva O peche transitivo dun GAD dado, con vértices e arestas, pódese construír en tempo usando busca en anchura ou busca en profundidade desde cada vértice. A cota simplifícase a cando .Skiena 2009, p. 495. Alternativamente, pódese resolver mediante multiplicación de matrices, con cotas inferiores ás cúbicas; isto proporciona unha mellora teórica para grafos densos.Skiena 2009, p. 496.

En todos estes algoritmos de peche transitivo, é posible distinguir pares de vértices alcanzables por polo menos un camiño de lonxitude dous ou máis doutros pares que só se poden conectar por un camiño de lonxitude un. A redución transitiva consta das arestas que forman camiños de lonxitude un que son os únicos camiños que conectan os seus extremos. Por tanto, a redución transitiva pódese construír coas mesmas cotas asintóticas de tempo cá peche transitivo.Bang-Jensen e Gutin 2008, p. 38.

Problema do peche O problema do peche toma como entrada un grafo acíclico dirixido con pesos nos vértices e busca o peso mínimo (ou máximo) dun peche: un conxunto de vértices tal que ningunha aresta saia de . O problema pódese formular para grafos dirixidos sen supoñer aciclicidade, pero sen maior xeneralidade, porque neste caso equivale ao mesmo problema sobre a condensación do grafo. Pódese resolver en tempo polinómico reducíndoo ao problema de fluxo máximo..

Algoritmos de camiños