0000059 2

3° Ula kożdogo wierzchołka ocochowenogo cechy k wybierany dokładnie Jedną gołyż, łyczycy ten wierzchołek z wlerzchoł -kłem o wartości cochy k-1 1 włyczomy ty gałąź do zbioru gałęzi karkasu. W ten opoaób wybierany w tumie n(G) - łt(C) gołyzl tworzycych przypadkowo wybrany karkaa T grafu G.

Przedstawiony algorytm Jest podobny do algorytmu tr/2na -czanla drzewa nejkrótozych połączeń (łańcuchów najkrótszych). Gednak zasadnicze różnica wyotypuje w punkcie 2°, gdzie w odnle-oleniu od poprzedniego algorytmu nla wymaga ely, aby cechować wszystkie nieocechowena wierzchołki cochy k*l przy -ległe do wierzchołka ocechowanego cechy k. Taki eposób cecho -wonie zapewnia, *e znieniejye Srlerzchołkl początkowe (cecha -O)

1 oposób cechowania, możoay otrzymać dowolny karkas ze zbioru wszystkich karkasów danego grafu.

Przykład 7.4

Wyznaczymy opisanym algorytmom karkas grafu przedstawionego na rys.7.1.

W wyniku procedury cechowanlo możemy uzyskać no przykład war -tości cech przedstawione na rysunku Jako liczby przy wierzchołkach. Wybrane gałyzlo tworzyce karkao przedstawiono na rysunku liniami pogrubionymi.

Olo karkosu T ■ <X,U^T,P^T> grafu C ■ <X,U,P> gałyzie uCU \ U^T nazywamy cięciwami tego karkasu. Każdy karkaa ma dokłodnle A(G) cięciw.

Rangą grafu G nazywamy llezbę <j>(G)

?(G) - m(G) - A(C) . n(G) - #(C)

Gest ona równa ilości gałęzi każdego korkaou grafu G.

TWIERDZENIE 7.13

Ola dowolnej cięciwy u dowolnego korkaau T grafu C iet -niojo w grafie C dokładnie jeden cykl prosty, zawierający wyłącznie cięciwę u i gałęzie korkaeu T.

Dowód tego twierdzenia wynika bezpośrednio z twierdzeń 7.11

1 7.3.

Twierdzenie 7.13 stanowi podstawę elgorytau tworzenia z jednego karkaeu T, innego karkasu T*danego grafu C. Dodajęc mie-nowicle do karkasu T dowolną Jago cięciwę, nie będącą pętlą, usuwany Jednocześnie jedną gałąź karkasu T należącą do powste-Jącego cyklu prostego. W tan epoaób otrzymujemy nowy karkas T¹ różny od T. Stosując cyklicznie tę operację nożemy przejść od dowolnego karkaeu T, do dowolnego Innego karkasu T^M.

Przy wyznoczaniu ilości różnych karkasów danego grafu C ■<X,U,P> korzysta eię z twierdzenia Lantleri-Trenta [28,46]. Wprowadźmy nadarz

S(C> “ [*ij]n»n ' " ’ »^xl

gdzie

2‘»(x₁) - r(x_i) dla 1 - J

przy tyn r^ - alanent nadarzy przyległości R> [^rij]_n,_n ' TWIERDZENIE 7.14    (Lent lari-Trenta, 1950,1954)

Niech K będzie dowolnym, głównym ninoran rzędu f(G) macierzy S(G), otrzymanym przez wykreślenie X(G) wierszy i tych saaych kolumn. Deżell wykreślone wiersze odpowiadają wierzchołkom grafu G, wziętym dowolnie po jednyn z każdej składowej opójnoścl, to wartość K jeet równa ilości różnych karkasów grafu G. w pozostałych wypadkach K^a O.

Dowód tego twierdzenia przedstawiony jeet w dodatku 0.3.

117