DSC00287 (4)

SPÓJNOŚĆ GRAFU

Grafem spójnym nazywamy taki graf, w którym dowolne dwa wierzchołki można połączyć marszrutą..

Składową spójności grafu jest każdy maksymalny podgraf będący grafem spójnym.

ce(G) - liczba składowych spójności grafu

Atonfln

1.    Wybieramy dowolny wierzchołek grafti i cochi^jcmy go cechą c*i.

2.    Wierzchołki przyległe do już ooechowanyoh cechujemy równie* cechą c, i powtarzamy

tą czynność dotąd, aż nie będziemy mogli ocechować więcej wierzchołków. Jeżeli ocechowane zostały wszystkie wierzchołki grafli to postępowanie kończymy i liczba składowych spójności jest równa wartości ostatnio stosowanej cechy c. Składowe spójności stanowią zbiory wierzchołków ocechowane tą samą wartością c.

Jeżeli pozostały wierzchołki nieocechowane to wybieramy dowolny z nich, zwiększamy o jedność wartość aktualnej cechy i powtarzamy punkt 2.

Graf nazywany silnie spójnym, jeżeli dla każdych jego dwóch wierzchołków x_lf Xj istnieje droga fi(Xb x) prowadząca od wierzchołka Xi do wierzchołka Xy

Składową silnej spójności nazywamy każdy maksymalny podgraf będący grafem silnie spójnym.

Algorytm Leijmana - algorytm do wyznaczania wszystkich składowych siłnęj spójności

Łańcuch Eulera - łańcuch zawierający wszystkie gałęzie grafit.

Twierdzenie (Euler 1736) Dowolny graf G zawiera łańcuch Eulera wtedy i tylko wtedy, gdy jest spójny (z wyjątkiem wierzchołków gołych) i gdy liczba wierzchołków o nieparzystych rozwidleniach w tym grafie jest równa 0 łub 2.

Algorytm

1.    Jeżeli wszystkie wierzchołki mąją parzyste rozwidlenia, to za wierzchołek początkowy

przyjmiemy dowolny wierzchołek. Natomiast, gdy istnieją dwa nieparzyste wierzchołki, to jf jest jednym z nich, a x drugim.

2.    Znajdujemy dowolny łańcuch prosty (lub cykl prosty dla ■**) łączmy wierzchołek y z jtr. Gałęzie tego łańcucha (cyklu) cechujemy cechą c - 0.

3.    Wśród gałęzi nieocechowanych znajdujemy dowolny cykl prosty za wiercący przynajmniej jedną gałąź przyległą do gałęzi już ocechowanej, a gałęzie tego cyklu cechujemy cechą o jeden większą od ostatnio nadanej cechy. Procedurę tę kontynuujemy do chwili ocechowania wszystkich gałęzi grafb.

4.    Tworzymy łańcuch Eulera poczynając od wierzchołka początkowego i zaliczając do łańcucha gałęzie o największych wartościach cech, incydentne z kolejnymi wierzchołkami Xi tworzonego łańcucha.

Braa Ełifrr*

Twierdzenie: W digrąfie istnieje droga cykliczna Eulera wtedy i tylko wtedy, gtty dla każdego wierzchołka x grafu spełniona Jest równość: s*(x) *» i“(x).

Jeśli istnieją tylko dwa takie wierzchołki x% i y* te s(xj - s~(xj -1 i 3 (yd • s'(yd ^m*ł, to istnieje droga Eulera o początku w. x$ i końcu w y$.