0000063

analogiczny prawe cechy $(x) • 1 nierzchołkom x, z których jest oaiogalny wierzchołek *₀ za pomoce drOg o niezerowej długości. Po zakończeniu tego etapu każdy wierzchołek xC X° aa nadane wartości (zero lub jeden) dla obu cech ^u(x) i ^(x). w ten sposób zbiór X^Ł zoatał podzielony na cztery rozłyczne podzbiory

^X00^^X01^UX10^VX11

gdzie indekey oznaczaj® odpowiednio wartości cech - lewej i prawej, wierzchołków należęcych do tych podzbiorów. Z tyai czteroma podzbiorami przechodzimy do punktu 3°.

3° Określamy nowe okładowe oilnej epójności. Możliwe a® przy tym neetępujęce sytuacje:

a/ X_n / fi. Wtedy X.j etanowi koiejn® składów® eilnej epójności, któr® zaliczamy oo zbioru S.

Detali pozoetałe zbiory X_QQ, X_Ql i X_lQ e« puete, to przechodzimy do punktu 4°, w przeciwnym wypadku zapa -mięt ujemy niepuete zbiory i będziemy je oddzielnie rozpatrywali w naatępnycn etapach procedury poniewoZ każda, nie wyznaczona do tej pory okładowa silnej epójności zo-_#    wlera el® całkowicie w którymś z tych zbiorów.

Przechodzimy do punktu 4°,

b/ x • p. wtedy zbiór zawiera jadnowierzchołkow® okładów® eilnej epójności { x_Q| . któr® zaliczamy do zbioru S 1 zapamiętujemy zbiór X_Q0\ {x_Q} , o ile jeet on nie -puety wraz z pozostałymi niepuetymi zbiorami spośród ^XiO ^{1 X}01* ^pr**chodzimy ⁰⁰ Punktu 4°.

4° Pytamy: czy e® zapamiętane niarozpatrzone zbiory powstałe w wyniku realizacji punktu 3° ? Detali e®, to wybieramy dowolny z , ch i traktuj®c go Jako nowy zbiór X° tworzymy podgref •<X°,U°,P⁰^ , z którym przechodzimy do punktu 2°. Dożęli nie ma już zapamiętanych 1 nlerozpatrzonych zbiorów, to zbiór S zawiera wszystkie składowe eilnej spójności. Oznacza to STOP dla procedury algorytmu Leifoana.

Podstawę przedstawionego algorytmu stanowi® twierdzenia: 6.5. 8.6 1 8.7. Stosujtc oznaczania przyjęte w algorytmie oznaczymy przez C ^ • <X, Uy®.    podgraf tworzony przez pod -

zbiór wierzchołków X^ę . będęcy jednym z czterech podzbiorów uzyokenych w wyniku procedury Cechowania wierzchołków podgrafu C° -<X°,U°,P⁶>    , w punkcie 2° algoryteu Leifeena.

TWIER02ENIE 8.5

Oetell X_Ł1 p p. to podgref C_n • <^xu'^uu'^Pa> J*^#t okładowe eilnej epójności. a wierzchołek x₀, od którego zaczyna alę cechowanie wierzchołków, naleiy do

^Xłl*

Dowód tego twierdzenia jeet zbędny ze względu ne jego oczywistość. Naotępne twierdzenie tet jeet oczywlete.

TWIEROZENIE 8.6

Doleli X_1Ł jeet zbiorea puetya. to wierzchołek pó-ctętkowy x_Q etanowi jedhowlarzcholkowę ekłodowę eil-nej epójności 1 naloty do zbioru ^X00*

TWIERDZENIE 8.7

Każde okładowa eilnej epójności grafu C° zawiera elę całkowicie w jednya z czterech podgrafów

^C<u9 " < V* ' ^9 ’ ^P^9> •

Dowód i

Niech zbiór YCX° etanowi ekładowę eilnej epójności grafu C° •<X°.U⁰.P°> . Woźay dowolny wierzchołek yCY. Wierzchołek x_Q jeet poczętkowya wierzchołkiem procedury cechowania. Detali w grafie C° ietnleję drogi ^(x₀,y) i 9(y.x₀). to na aoey twierdzenia 8.5 zbiór X_1JL ■ Y.

Pozoetoje przypadek, gdy nie ietnleję jednocześnie drogi

^(V^{v) 1} ^^y*^x0>- ^{być prty ty}* ^{tr2y ,ytua}O* *

1/ letnieje droga ^u(x₀,y) i nie letnleje -9(y,x₀). Wtedy wierzchołek y otrzyauje cechę ^u» 1,    9-0. Tya eaaya woryet-

kie wierzchołki naletęee do Y na aocy definicji eilnej opśjności auezę a leć cechy ■ l.a *$ • O, a zatea YCX_lQ.

2/ Nie letnleje droga ^(*₀#y). • letnieje 9(y.x₀).Wtedy wierzchołek y otrzyauje cechę pm O. 9» i. Zatea wezyetkle wierzchołki naletęee do Y otrzymuję te eaae wartości ceoh 1 cały zbiór Y naloty do X_0ł#