0000064

3/ Nim istnieje enł^u(x_o,y). ani -9(y.x_o). Wtedy wszystkie wierzchołki zbioru Y otrzymuję cechy    ^ ■ 0 1 tym samym

cały zbiór Y nalały do X_£X). Kończy to dowód twierdzenie.

Zo pomocą algorytmu Lalfaana można efektywnie etwlerdzić Istnienie bądź nieistnienie w hiporgrafie 1 grafie eklerowanya dróg cyklicznych.

TWIERDZENIE 8.6

Graf sklarowany (hlpergrsf skierowany) bez pętli nie zawiera dróg cyklicznych wtedy 1 tylko wtedy, gdy Wszystkie Jego składowe ellnej epójnoócl tę jedno-Wierzchołkowe.

Dowód tego twierdzenie wynika wprost z definicji drogi cyklicznej 1 definicji okładowej silnej spójności.

8.3. Warstwy grafu

Zbiór wierzchołków grafu lub hipergrofu oklerowenego, nie zowlerajęcogo dróg cyklicznych nożna podzielić na pewno podzblo* ry zwane warstwami. Podział taki ułatwia analizę zbioru dróg • istniejących w tym grafie.

Na przykłod warstwy nogę określać etapy aetody programowania dynamicznego zostosowenej do wyznacz*anla dróg ekstremel-nycit w sieciach skierowanych.

Wprowadzimy następujące określenia dle grafu lub hlper-grafu G •<X,U,P> o binarnej macierzy przejść P(G) "[Pij]_n*n^; n • | X | .

Zbiorem następników, wierzchołka nazywany zbiór

Zbiorem poprzedników wierzchołka x^ nazywamy zbiór

W • -r • t w ą grafu (hlpergrafu) a klarowana go, nla zowierojęcego dróg cyklicznych, nazywa olę podzbiór X_kC X ; k ■ 0,1,...,K wierzchołków tego grafu, określony naatępujęco

1/ x₀ . (x«X j r‘^ł(x) - p}

^2/ [^x€xkJ^[r‘V)c v₀^xj]^A[r“¹(M^x_k / p]

dla k - O.K-1.

Przykład 6.1

Ważmy pod uwagę graf aklarowany baz pętli, przedstawiony na rya.6.1.

Rya.6.1

Wyznaczając składowe silnej spójności tego grafu za po -aocę algorytmu Lclfaana atwlardzamy, żs jest ich 15 l wszyst -kia oę jodnowierzchołkowo.

Zatem zgodnie z twierdzeniem 8.8 graf ten nie zawiera dróg cyklicznych (jest acykliczny w eenele dróg). Wobec tego aotbay określić warstwy tego grafu, która przedstawia rys.8.2.

W zastosowaniach praktycznych użyteczna sę naetępujęee twierdzenia dotyczęce warstw.

127