Skierowany graf acykliczny

Skierowany graf acykliczny (ang. directed acyclic graph, DAG) – graf skierowany, który nie posiada cyklów skierowanych. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych.

Przykład skierowanego grafu acyklicznego

Przykład

Jeśli chcemy przedstawić pewne obliczenia za pomocą drzewa, może ono się wykładniczo rozrosnąć:

b = a + a; c = b + b; d = c + c
e = d + d; f = e + e; g = f + f
h = g + g

Drzewo dla h ma już 128 liści, operowanie na tej postaci nie jest więc wygodne. Z drugiej strony dla ogólnych grafów skierowanych trudno jest stworzyć algorytm wyliczania wartości wyrażeń, gdyż łatwo jest się zapętlić.

Jeśli skorzystamy ze skierowanych grafów acyklicznych i programowania dynamicznego, otrzymamy wyliczenia (jeżeli a=10):

h = g + g (brak g, wyliczmy najpierw g)
  g = f + f (brak f, wyliczmy najpierw f)
    f = e + e (brak e, wyliczmy najpierw e)
      e = d + d (brak d, wyliczmy najpierw d)
        d = c + c (brak c, wyliczmy najpierw c)
          c = b + b (brak b, wyliczmy najpierw b)
            b = a + a = 10 + 10 = 20
          c = b + b = 20 + 20 = 40
        d = c + c = 40 + 40 = 80
      e = d + d = 80 + 80 = 160
    f = e + e = 160 + 160 = 320
  g = f + f = 320 + 320 = 640
h = g + g = 640 + 640 = 1280

Na zasadzie skierowanych grafów acyklicznych działa m.in. algorytm unifikacji, działający w czasie liniowym (a którego wynik przedstawiony jako drzewo ma potencjalnie wykładniczy rozmiar).

Zastosowania

Przykład zastosowania skierowanego grafu acyklicznego jako drzewa genealogicznego dynastii Ptolemeuszy. Ze względu na małżeństwa pomiędzy spokrewnionymi członkami rodu nie da się go przedstawić jako drzewo w rozumieniu informatycznym.

Grafy takie, mają szerokie zastosowania w obliczeniach numerycznych, przetwarzaniu potokowym (np. projektowaniu procesorów), tworzeniu układów kombinacyjnych z bramek logicznych, kompresji, kompilatorach, diagramach przepływu, przepływie danych czy zasobów (transport, energia elektryczna, woda). Grafy takie mogą również opisywać porządek częściowy.

Spójny DAG w którym istnieje jeden wyróżniony wierzchołek, do którego nie ma krawędzi wchodzących (tzw. korzeń), można zmienić na drzewo, które posiada powtarzające się poddrzewa. Operacje odwrotną (wyszukiwanie powtarzających się poddrzew w drzewie, i zamienianie go w DAG), wykorzystuje się m.in. w kompilatorach przy tzw. eliminacji wspólnych podwyrażeń. Grafy z wieloma wierzchołkami nieposiadającymi krawędzi wchodzących, można sprowadzić praktycznie do wymaganej postaci poprzez dodanie nowego wierzchołka, który sam nie posiada krawędzi wchodzących, a krawędzie wychodzące kierują do rzeczonych wierzchołków (tzw. początkowych).

Bibliografia

• Thomas H. Cormen, Leiserson Chalres E., Rivest Ronald L., Stein Clifford: Introduction to Algorithms. Massachusetts Institute of Technology, 2009, s. 589-683. ISBN 978-0-262-03384-8.

Zobacz też

• sortowanie topologiczne
• drzewo (informatyka)