0000039 2

wierzchołków X no klooy obotrakcjl 1 graf (hipergraf) G na okładowe opójnoścl.

ikeynalny

Składowa opójnoścl J

podgrof, który Jeot grafom opójnyn.

Liczba okładowych opójnoścl 3C(C) grafu (hlpergrafu) G Joot jednę z wożnlojezych chorak -teryatyk grafu (hlpergrafu).

Nojliczr, lejoze okładowa opój-n o ś e i joot ekłodowę opójnoścl o nojwiękozoj ilości wierzchołków.

Rzędem grofu rz(G) nazywamy Ilość wierzchołków najllcznloJezoj okładowej opójnoścl. Ola grafu epójnego rz(C) - |X| .

Skłodowe opójności molna wyznaczyć przez utworzenie eyme-

1 fldy <x₁,x_J>CS

0 gdy <x_i,x_j>fS

MoZno łotwo wykazać, Ze $^b moZno otrzymać z binarnej macierzy przyległości R^b nod pierścloniem algebry Boole'a

gdzie R^bl^k> -

gdzie R    - k-to potęga macierzy

MoZno również wykazać. Ze wprowadzając    gdzie I-

macierz jodnoetkowe, otrzymamy

S^b .B*¹'-¹! . (| vK^b)"-^ł

W praktyco, dla wyznoczenio wszystkich składowych spójności nożna stosować neatępujęcę procedurę cechowania wlorzchołków grafu (hlpergrafu) i Wyblorany dowolny wierzchołek 1 cechujemy go cechę c ■ 1. Naetępnlo wezyetkle wierzchołki przylogłe do ocochowonych cechę c ■ 1 również cechujemy cechę c ■ 1, do tej pory, aż nie będziemy mogli ocechować następnych wierzchołków. Gożoli pozoetały wierzchołki nleocechowane, to c: ■ c ♦ 1, cechujemy dowolny nleocechowany wierzchołek nowę wartoóclę cechy 1 powtarzamy proces cechowania.

Procedurę kończymy z chwilę ocechowanio wszystkich wierzchołków x6X. Wartoóć ostatniej nodanej cechy jest równa JC(G), a okładowe opójnoścl tworzę podzbiory wierzchołków ocechowanych tę eamę wartoóclę cechy.

Opisana procedura Jest bardzo efektywna 1 wymego posługiwonio się Jedynie binornę maclerzę przyległoócl wlorzchołków R^b lub ryeunklem.

Wierzchołki i gałęzie (hlpergałęzle) sę klasyfikowane zo względu no epójnoóć podgrafów (podhlpergrafów) i grafów (hiper-grefów) częściowych, powstojęcych przez ich usunięcie z grafu (hlpergrafu).

Wierzchołek Jest złęczem w grafie (hlpergrofie) G. Jeżoli podgrof otrzymany po Jego*ueunięciu na wlęcoj składowych spójności niż graf (hipergraf) G.

Cołęź (hipergałęź) Jeot klamrę (nootkiom) w grafie (hipergrafie) G, Jeżeli po joj uounięciu pozostojo graf (hipergraf) częściowy o większej ilości okładowych spójności niż tt(G). Gałęzie, które nie eę klamrami, nazywane oę gełęzioml cyklicznymi.

5.3. Silna epójnoóć

Graf (hipergraf) nazywamy ellnle spójnym wtedy i tylko wtedy. gdy dla każdej pory wierzchołków <x,y>£X'X lotnlojo droga _<u(x,y). Każdy graf oilnie spójny Jeet grafom epójnym lecz nie na odwrót.

Dla dowolnego grafu wprowadzimy relację ollnoj opójnoścl S c x «X określonę nostępujęco

77