0000058 2

TWIERDZENIE 7.9

Hipargref częściowy H* powstający przez usunięcie tałęzi u hlperdrzewe H o_<X.U,P> na k(u) okłodo-•ych spójności. X(H' ) w.k(u), gdzie k(u) Jest wy-maro* Poktora k takiego. Ze <x, u> c P; X •

*    j> . W szczególności, po uaunlęclu

gałęzi * drzowa C powstaje graf częściowy o dwóch okładowych spójności.

DPwód togo twierdzenie wynika z twierdzenia 7.D.

Niektóre wżyteczne w zaatoaowaniach twierdzenia odnoezę elę wy-łfcznie do grafów (drzew).

TWIERDZENIE 7.IO.

w dowolnye grafie spójny* C • <X.U,P> latnleje dla każdego wierzchołka x° graf częściowy T • <X,U^T.P^T> będęcy drzewem, w który* każdy łańcuch łęczęcy wierzchołek x° z dowolny* wierzchołki** x jeet łańcucha* najkrótszy*, łęczęcy* ta wierzchołki w grafie G.

Dowód s

Z twiardzania 5.9 otrzyaujoay wnloaak, żo każdy odcinek łańcucha najkrótszego Jest łańcucha* najkrótszy*. Algoryt* opisany w punkcie 5.4 wyznacza dla każdego uatalonago wierzchołka *o ^dr2#*⁰ najkrótszych połęczeń z pozostałym wierzchołkom grafu spójnego. Mianowicie, po ocechowaniu wierzchołków zgodnie z procedurę togo algorytmu, dla każdego wierzchołka * / wybierany jednę gełęż. w ten sposób dla grafu o n wierzchołkach wybierany n-1 gałęzi, zachowujęc spójność powatejęcego gra fu ozęś-ciowogo G'. Otrzyaujany zata* X(c' ) • 1, A(C) - O. Kończy to dowód twierdzenie.

TWIEROZENIE 7.11

Oeżall do dowolnego hipardrzewa H - <X.U.P> dodaey dwuczłonowa hlpergałęi u. to powstanie nadhlpargraf Mⁿ • <X,Uⁿ,Pⁿ> , taki że A(Hⁿ) • 1, to znaczy za -wlerajęcy dokładnie jadan aykl prosty z dokładnością do wierzchołka poczętkowego i kierunku tworzenia cifflu określającego ten cykl.

Dowód i

A(Hⁿ) - A(H) ♦ (k(u) - 1) • A( H) ♦ 1 . 1 TWIERDZENIE 7.12

Liczba cykloeetyczno dowolnego grafu C Jeat równa ilość gałęzi, która naloty uaunyć aby powalały graf częściowy C* był laaoa tokia, ta *(G') ■ 3e(C).

Dowód i

Aby nia zmieniać ilości okładowych apójnoścl motamy uou-wać z grafu C tylko gałęzla cykliczna. Ueunięcla gałęzi cyklicznej powodują zwnlejazania liczby cykloaatycznoJ grafu częściowego dokładnie o jedność. Zataa do wyzerowania liczby cykloma-tycznaj trzeba uaunyć dokładnie A(G). gałęzi cyklicznych.

7.3. Karkea grafu

K a rkaaoa grafu G • <X,U,P> nazywaay dowolny graf częściowy T •<X,li¹,P^T> epałnlajycy dowolna dwa z poda -nych trzech warunkówt

1/ a(T) - a(C) - A(G) ;

2/ *(T) . JC(C) ,

3/ A(T) - O /

gdzie a(C) - |U|, a(T) - | U^T |.

Z katdych dwóch warunków wynika trzeci.

Karkao grafu G joat laaoa o taj aaaej ilości okładowych apój -nośćl co graf G 1 jeot nośnlklea informacji o epójności wierzchołków grafu. Algoryta wyznaczania dowolnego karkaou wynika z tezy twierdzenia 7.5.

Algoryta wyznaczania Jednego z karkaeówt

1° W katdej okładowej apójnoścl grofu G wybierany po Jadnya dowolnya wierzchołku 1 cechujemy ja cachy 0.

2° Dowolnoau. nleocechoweneeu wierzchołkowi, przyległemu do wierzchołka ocechowanego, nadajemy wartość cachy o jedon wlękazy od cechy wierzchołka ocechowanego. Czynność tę powtarzany at ocechujemy wezyetkie wierzchołki.

115