0000062

•Yozyotklm nie ocechowanym wierzchołkom x ^, którym w tym wlor-ezu odpowiadaj# wartości • 1 nadajemy coch# c • 1. F’ro-codurę punktu 2° kontynuujemy dot#d, ei nie będzie można ocechować Żadnych nowych wierzchołków.

3° W wierszu i-tym macierzy D(G) wotawlamy Jedynki na pozy -cjach odpowiadających wierzchołkom ocechowanym coch# c • 1. Znajęc macierz oslogalnoici moZemy łatwo wyznaczyć wszystkie składowe ellnej spójności grafu (patrz pkt.S.3). Przypomnijmy.

Ze układowo sllnoj spójności grafu nazywamy każdy maksymalny podgraf tego grafu, b#d#cy grafem ellnie opójnym. t-pooób wyznaczania tych-składowych na podstawie macierzy oslogalnoici okroiła ponlZoze twierdzenia.

TWIERDZENIE 8.4

Każdy maksymalny podzbiór wierzchołków, którym odpowiadaj# identyczne wiersze macierzy oslogalnoici. tworzy

składów# sllnoj spójności.

Dowód i

Elementy głównej przek#tnej macierzy oslogalnoici O(G) s# z definicji Jedynkami. DeZeli zatem weźmiemy dowolne dwa identyczne wiersze macierzy O(C), np. wiersze i-ty i J-ty, to d^ - dj_A • 1. Oznacza to. Ze w grafie istnieje jednocześnie droga ^^u(^xi«^Kj) oraz    x ^ * x ^) i z definicji wierzchołki

oraz naleZ# do tej samej składowej silnej spójności. Blo -r#c zatem wszystkie wierzchołki, którym odpowiadaj# Identyczne wiersze, otrzymujemy cał# składów# sllnoj spójności.

Kohczy to dowód twierdzenia.

Przedstawiony spooób wyznaczania składowych silnej opój-noścl jest jednak praktycznie mało uZytoczny dla grafów (hlper-grafów) o znacznej liczbie wierzchołków, ponieważ wymaga on wyznaczenia całej macierzy oslogalnoici D(G). W zwl#zku z tym poszukiwano bardziej efektywnych metod wyznaczania tych składo -wych.    ,

Dodn# z najefektywniejszych mrtod opracował L.Lelfman (1966). [29],

6.2. Algorytm Lolfman*

Algorytm ton duły do wyznaczenia wszystkich okładowych silno J opójnoócl. Dzięki owoj efektywności znajduj* oh ozoro -kl* zaotosowonie jako olemant wielu różnych algorytmów doty -częcych dróg w grafach i sieciach ekiorowanych.

Danymi do algorytmu a«t

Graf skierowany lub hipergraf skierowany, G ■ <X,U,P> oraz etop-nio zewnętrzna s*(x) i wewnętrzna e'(x) Jogo wierzchołków, w procedurze algorytmu atoeowaho *ę naatępujęc* oznaczaniat ^U(x) - lewa cecha wierzchołka xi 4(x) - prawa cecha wlerzćhdłka x;

8    - zbiór podzbiorów wlśrzchołków tworzęcych okładowa sil

nej spójności.

Procedura i

1° W grafie G poszukujemy wierzchołków x, dla których e*(x)*0 lub s“(x) * 0. Do£ell takie wierzchołki, to zaliczamy je do S jako jedhbfciarzchólkow* akładowe oilnoj spójności. Usuwamy j* t rfrafu G twOrzęc odpowiedni podgraf (podhipSr-graf) 6° * <X ,U°,P°> i dla tego podgrafu kontynuujomy cżynnośćl punktu 1°»    ^

Dożęli ni* ma takich wierzchołków, to przechodzimy do punktu 2°.

2⁶ w podgrafi* G° ■ <X°,U⁰,P°> uzyskanym w wyniku czynności punktu 1° lub 4° wybieramy dowolny wierzchołek x_Q i rozpoczynamy proce* cechowania wierzchołków podwójnymi co chęci (<u(x). -D( x)) _# który realizujemy w naetępujęcy apoaóbi Na poczętku wszystkim wierzchołkom x6X° nadajemy cechy (O.O).

Wszystkim następnikom x wierzchołka x₀ nadajemy ^u(x) • 1. Następnikom tych ocechowanych wierzchołków też nadajemy ca-rtrę • i ltd. aż dojdziemy do sytuacji, w której ni* bę« dzio można powiększyć zbioru wierzchołków ocechowanyoh rt* chę (a* i. w wyniku tego postępowania cechę ^u* 1 będę miały wozystkl* wierzchołki osięgalne z wierzchołka x_Q. Teraz etartujęc znów z wierzchołka x_Q, lecz poruezajęc się przeciwnie do zwrotu łuków (hiporłuków). nadajemy w sposób

123