3. Las rozpinający
Niech G = <V, E> będzie skończonym, spójnym, niezorientowanym
grafem.
Definicaja 3.1 Lasem rozpinającym dla grafu G =<V,
E> nazywamy
rodzinę drzew
d1 = <V1, T1>,...,
dk = <Vk, Tk>.
taką że rodzina zbiorów wierzchołków tych drzew tworzy podział zbioru V
(tzn. zbiory V
1,...,V
k są niepuste i parami
rozłączne, a ich sumą jest zbiór wierzchołków grafu) , a zbiory T
i
, dla i =1,..., k, są podzbiorami zbioru krawędzi grafu G.
Przykłady lasów rozpinających graf przedstawiono na rysunku 12.5(a) i
(b). Las rozpinający na rysunku 12.5(a) składa się z trzech drzew
<{A,B,G},{AB,AG}>, <{F,I,E},{FI,IE}>,
<{H,C,D},{HD,DC}>. Każdy wierzcholek grafu należy do dokładnie
jednego z drzew tego lasu. Las na rysunku 12.5(b) składa się tylko z
dwóch drzew. Lasem rozpinającym jest też rodzina : {<A, >, <B,
>, <C, > ...,<I,>}. Każde drzewo tej rodziny składa się
z jednego tylko wierzchołka i nie posiada krawędzi.
Pytanie 4:Czy dwa różne drzewa lasu rozpinającego mogą mieć
wspólną krawędź?
Niech c będzie funkcją kosztu dla grafu G = <V, E>, c: E ->
R+, i niech będzie dany las rozpinający
LR(G): d1 = <V1,
T1>,..., dk = <Vk, Tk>
grafu G. Załóżmy, że e jest krawędzią o minimalnym koszcie wśród
krawędzi, które łączą wierzchołki należące do różnych drzew tego lasu
rozpinającego.
Rozważmy rodzinę DR drzew rozpinających grafu G, które są
rozszrzeniem lasu LR(G), tzn, rozważamy drzewa rozpinające, które
zawierają wszystkie krawędzie wszystkich drzew danego lasu.
Twierdzenie 3.1
W zbiorze DR nie istnieje drzewo rozpinające <V,T*> grafu G,
którego koszt jest najmniejszy wśród wszystkich drzew rozpinających
rodziny DR i takie, że krawędz e do niego nie należy .
Dowód. Przypuśćmy przeciwnie, że takie drzewo istnieje d* = <V,
T*>,
d* ÎD
R,
e Ï T* , c(d*) =
min {c(d): dÎDR}.
Niech e = (u,v) oraz u Î Vi, a v Î Vj dla pewnych dwóch różnych indeksów
i, j, por rysunek 12.6.
Ponieważ T* jest drzewem, zatem istnieje dokładnie jedna droga w tym
drzewie, łącząca wierzchołki u i v, i która nie przechodzi przez
krawędź
e ( z założenia e nie należy do T*). Weźmy krawędź (u',v') na tej
drodze, taką że u' Î Vi, a v' Ï Vi. Krawędź (u',v') nie należy do żadnego z
drzew lasu rozpinającego LR(G). Stąd i z założenia krawędź e miała
koszt najmniejszy wśród krawędzi nienależących do lasu, wynika że
c(u',v') > c(u,v).
Tworzymy nowe drzewo rozpinające grafu G, usuwając z drzewa d* krawędź
(u',v') i zastępując ją krawędzią e. Otrzymane drzewo ma koszt
miniejszy niż drzewo d*, co jest sprzeczne z przyjętym założeniem.
Pytanie 5: Ile co najwyżej drzew może się znajdować w lesie
rozpinającym dla danego grafu o n wierzchołkach?
