DSC00296 (9)

7,1.1, Algorytm Lelfmana [37]. Algorytm ton służy do wyznaozania wszystkich składowych silnej spdjnośol, Dzięki swej efektywności znajduje on szerokie zastosowanie jako element wielu różnych algorytmów dotyczących dróg w grafach i sieciach skierowanych.

Dane

Graf Berge’a (7* (X, JT} oraz stopnie wierzchołków tego grafu:

5⁺(jc)-|r(x)|, ,-(x)-jr-‘(*)ji x»x

V/ procedurze algorytmu stosowane są następujące oznaczenia: l(x) «— lewa cecha wierzchołka x, p(x) — prawa cecha wierzchołka x,

S — zbiór podzbiorów wierzchołków tworzących składowe, silnej spójności,

Procedura

1.    W grafie G poszukujemy wierzchołków x, dla których j⁺(x) *t) lub s^m (x) m o, leżeli są takie wierzchołki, to zaliczamy je do S, jako jedno-wierzchołkowe składowej silnej spójności. Usuwamy je z grafu G, tworząc odpowiedni podgraf 0° « (X°, r°>, i dla tego podgrafu kontynuujemy czynności punktu 1, Jeżeli nie ma już takich wierzchołków, to przechodzimy do punktu 2.

2.    W podgrafie G° «=* <£⁰, r°>, uzyskanym w wyniku czynności punktu 1 lub 4, wybieramy dowolny wierzchołek x₀ i rozpoczynamy proces cechowania wierzchołków podwójnymi cechami (/(x),p(x)), który realizujemy w następujący sposób:

Na początku wszystkim wierzchołkom xe2T° nadajemy wartości cech (0,0). Wszystkim następnikom x wierzchołka x₀ nadajemy wartość cechy /(x)«1. Nieocechowanym następnikom tych ocechowanych wierzchołków też nadajemy wartość cechy /«1 itd,, aż dojdziemy do sytuacji, w której nie będzie można powiększyć zbioru wierzchołków ocechowanych cechą /«1. W wyniku tego postępowania, cechę /«1 będą miały wszystkie wierzchołki osiągalne z wierzchołka x₀ za pomocą dróg o Blezerowej długości. Teraz, startując znów z wierzchołka x₀, lecz poruszając się przeciwnie do zwrotu łuków, nadajemy w sposób analogiczny prawe cechy p(x)^m 1 wierzchołkom x, z których jest osiągalny wierzchołek x₀ za pomocą dróg o niezerowej długości. Po zakończeniu tego etapu każdy wierzchołek xeX° ma nadane wartości (zero lub jeden) obu cech /(x) ip(x). W ten sposób zbiór X° został podzielony na cztery rozłączne podzbiory

X⁰«;roouXoiV*ioV*ii    (7J)

gdzie indeksy oznaczają odpowiednio wartości cech (lewej i prawej) wierzchołków należąoych do tyoh podzbiorów,