0000056 2

Woźny teraz pod uwagę hlpergraf (graf) częściowy H* hipergrafu H • <X,U,P> . powetajęcy przoz utonięcia dokładnie jednaj gałęzi u za zbioru U, h'-<X,U\{u} , P^ł> . Nietrudno zauważyć, to liczba cyklomatyczna A(H')4 A(H). Gałęzie, których uaunięcia powoduje zmniejszenie eię liczby cykloaatycz-nej grafu (hipergrafu) częściowego nazwieay gałęziaai cyklicznymi. Pozostałe nazywane eg klamrami.

Deżoll G Jest grafom, a G¹ omawianym grafem częściowym, to

A(g')

A(C), gdy u Jest klamrę

A(G) - 1 , gdy u Jest gałęzlę cyklicznę

(7.3)

TWIERDZENIE 7.1

Liczba cyklomatyczna dowolnego grafu (hipergrafu) Jest

nleujenna.

Dowód t

Załóżmy, że A(H)<0. Wtedy ueuwejęc po kolei wszystkie hipergałęzie możemy Jedynie zmniejszać llozby cyklomatyczna powetajęcych hlpergrafów częściowych. Po usunięciu ostatniej hlpergałęzi otrzymujemy hlpergraf pusty, dla którego A(m' ) ■

■ 3Ł- n ■ 0. Otrzymana eprzeczność kończy dowód twierdzenia.

TWIERDZENIE 7.2

Liczba cyklomatyczna A(H) • 0 wtedy i tylko wtedy,

gdy hlpergraf (graf) H nie zawiera łańcuchów cyklicznych.

Dowód i

Załóżmy, że A(H) ■ 0 iw H Istnieje Jakiś łańcuch cyk-llctny.

Weźmy dowolnę hlpergałęź u naleźęcę do tego łańcucha cyklicznego. Ola tej gałęzi mamy pomnę wartość k(u). Po usunięciu tej gałęzi powstanie hlpergraf częściowy H* taki, że

A(H' ) - A(H) - (k(u) - 1) ♦ A*

A** k(o) - 2

Wobec tego A(H* ) <A(H)    1 doctajomy sprzeczność z tezy twier

dzenia 7.1.

Załóżmy teraz, że w H nie na łańcuchów cyklicznych 1 A(H)> O. Orok łańcuchów cyklicznych oznacza, te wszystkie hl- . pergałęzle eę klonraai. Usuwanie klaner nie zmniejsza liczby cyklonotycznej. Zatea po usunięciu wszystkich hlporgałęzl powstanie hlpergraf pusty, a jego liczba cykloaatyczna byłaby większa od zera. Otrzymaliśmy sprzeczność, która kończy dowód twierdzenia.

TWIERDZENIE 7.3

Hipergrof H, aajęcy wyłęcznie hlperkrawędzie, hlper-łukl l pętle, zawiera dokładnie Jeden łańcuch cykliczny prosty (z dokładnośclę do wierzchołka poczęt-kowego l kierunku tworzenie cięgu określajęcego ten łańcuch) wtedy i tylko wtedy, gdy A(H) ■ 1.

Dowód i

Załóżmy, te w H istnieje dokładnie Jeden cykliczny łańcuch prosty 1 A(H) ł- 2. Po usunięciu dowolnej gołęzl u nale -tęcej do tego łońcucha, w powstałya hlpargrafle częściowym u* nie ma łońcuchów cyklicznych. Natomiast A(H* ) ■ A(M) -- ( k( u) - 1) ♦    Wartość A3t w tym przypadku będzie równa

k(u) - 2. Równość ta wynika z definicji cyklicznego łańcucha prostego. Zatem A(h') • A(H) - 1£1. Otrzymujemy sprzeczność z tezę twierdzenia 7.2.

Załótay teraz, ta A(H) ■ 1    1 w H Istnieje więcej nlt

Jeden łańcuch cykliczny prosty. Wtedy Istnieje co najmniej Jedna taka hlpergałęź u, te jej usunięcie powoduje "rozerwanie" nie wszystkich tych łańcuchów cyklicznych, a tylko na przykład jednogo. Usuwajęc tę hlpergałęź (cyklicznę) otrzymujemy hlpergraf częściowy H* zawierajęcy jeszcze łańcuchy cykliczne 1 Jednocześnie A(H') • A(H) -1-0. Otrzymana sprzeczność z tezę twierdzenia 7.2 kończy dowód twierdzenia 7.3.

111