DSC00298 (8)

3.    Określamy nowe składowe silnej spójności. Możliwe są przy tym następujące sytuacje:

a)    X„ 1*0. Wtedy X_tt stanowi kolejną, składową silnej spójności, którą zaliczamy do zbioru S. Jeżeli pozostało zbiory X_ot, X_0i i X_l0 tą puste, to przechodzimy do punktu 4, W przeciwnym przypadku zapamiętujemy niepusće zbiory i będziemy je oddzielnie rozpatrywali w następnych etapach procedury, ponieważ każda nie wyznBozona do tej pory składowa silnej spójności zawiera się całkowicie w jednym z tych zbiorów. Przechodzimy do punktu 4.

b)    X₁₁ m0. Wtedy zbiórko zawiera wierzchołek x₀, tworzący jedno-wierzchołkową składową silnej spójności {x₀}. Zapamiętujemy zbiór *oo \ {x₀}, jeżeli jest on niepusty, wraz z pozostałymi niepustymi zbiorami spośród X_i0 i *01- Przechodzimy do punktu 4.

4.    Pytamy: czy są zapamiętane nierozpatrzone zbiory powstałe w wyniku realizacji punktu 3? Jeżeli są to wybieramy dowolny z nich i traktując go jako nowy zbiór X°, tworzymy podgraf <J° — (X^c, J"°>, z którym przechodzimy do punktu 2. Jeżeli nie ma już zapamiętanych i nierozpa-trzanych zbiorów, to zbiór S zawiera wszystkie podzbiory tworzące składowe silnej spójności. Oznacza to koniec procedury algorytmu Leifinana.

. Podstawę przedstawionego algorytmu stanowią twierdzenia 7.2, 7.3 i 7.4. Stosując oznaczenia przyjęte w algorytmie, oznaczymy Q_ltm(X',,, Uip, P|,> podgraf tworzony przez podzbiór wierzchołków X,_r, będący jednym z czterech podzbiorów uzyskanych w wyniku procedury cechowania wierzchołków podgrafit G? <• (X°, Ł'°, P°>, w punkcie 2 algorytmu Leif-mana.

Twibrdzenib 7.2. Jeżeli X_li¥>0, to podgraf Gu“Ifui Pu) jest składową silnej spójnoicl, a wierzchołek x₀, od którego zaczyna sit cechowanie wierzchołków, należy do 2T_U.

Twierdzenie 7.3. Jeżeli X_n Jest zbiorsm pustym,: to wierzchołek początkowy x* stanowi Jednowlerzcholkową składową silnąj spójnoicl l należy do zbioru *00 ■

Twierdzenie 7.4. Każda składowa silnej spójnoiol grafu O⁰ zawiera sit całkowicie w Jednym z czterech podgrąfów G/,« U_lp, P|,>.