DSC00291 (6)

Graf B«rgg*i (dtgrąflunigrąf)

Q*<w_fr>

gdzle:

W - zbiór wierzchołków, r - relacja dwuczłonowa, której elementy <x,y > określają łuk od wierzchołka x do y lub pętlęgdy x ^my.

Graf Berge'a moZna jednoznacznie przedstawić za pomocą binarnej macierzy przęjić.

r„ - (y: < X, y > € T f - zbiór następników wierzchołka x (określony jednoznacznie przez jedynki w wierszu x binarnej macierzy przejść )

F#* ^m (y: < y, x > € T } * zbiór poprzedników wierzchołka jc (określony jednoznacznie przez Jedynki w kolumnie x binarnej macierzy przejść )

Dendryt -spójny dlgraf, unigraf bez pętli mający dokładnie jeden wierzchołek X#, zwany początkiem dendrytu ( nie ma poprzedników) i pozostałe wierzchołki mąjące dokładnie po Jednym poprzedniku.

Antydendryt -spójny digraf, unigraf bez pętli mający dokładnie jeden wierzchołek x* zwany końcem dendrytu ( nie ma następników) i pozostałe wierzchołki mające dokładnie po jednym następniku.

Digrafy zawierające drogi cykliczne nazywamy cyklicznymi w sensie dróg. Digrafy bez dróg cyklicznych nazywamy acyklicznymi w sensie dróg.

Wiryttry..gntfti

Definicja: Warstwą digrąfu G ^m < W, T > nazywa się podzbiór W* zbioru wierzchołków digraju, określony następująco:

1.    Do Wę ( warstwy zerowej jnaletą takie wierzchołki x dlgrąfu dla których zbiór poprzedników jest pusty.

2.    Każdy wierzchołek należący do warstwy We (k> 0) ma poprzedniki tylko w warstwach od Odo k-1.

3.    Każdy wierzchołek, który ma poprzedniki i Jest w k - tej warstwie, musi mieć przynajmniej Jeden ze swoich poprzedników w warstwie bezpośrednio poprzedząjącej

Algorytm ma charakter rekurencyjny i polega na tworzeniu kolejnych podgrafów powstających przez usuwanie tych wierzchołków, które nie mają poprzedników.