ASD Ćwiczenia 11

Niech $G=(V,E)$ będzie grafem spójnym, a $w:E\to Z$ funkcją, która każdej krawędzi $e$ przypisuje nieujemą, całkowitoliczbową wagę $w(e)$. Dla każdego podgrafu $G^{\prime }=(V^{\prime },E^{\prime })$ definujemy wagę $W(G^{\prime })$ jako sumę wag jego krawędzi. Drzewo rozpinające grafu $G$, którego waga jest nie większa o od wagi każdego innego drzewa rozpinającego w tym grafie nazywamy minimalnym drzewem rozpinającym grafu $G$. W grafie może być więcej niż jedno drzewo rozpinające.

Zadanie 1

Udowodnij, że jeśli wagi krawędzi są parami różne, to w grafie istnieje dokładnie jedno minimalne drzewo rozpinające.

Wskazówka

Udowodnij, że następujący algorytm zachłanny oblicza minimalne drzewo rozpinające dla spójnego grafu $G=(V,E)$, a następnie wykaż, że gdy wagi są parami różne, to każde inne drzewo ma wagę większą.

1 posortuj krawędzie według wag, od najmniejszej do największej, i niech
   //e_1, e_2,\ldots, e_m będdzie ciągiem posortowanych krawędzi.
2 $F:=\mathrm{\varnothing }$; $i:=0$;
3 while $|F|<n-1$ do 
4 begin
5   $i:=i+1$;
6   if graf Parser nie mógł rozpoznać (błąd składni): {\displaystyle (V,F\cup \{e_i}\})}
 nie zawiera cyklu then 
7     $F:=F\cup \{e_i\}$ 
8 end;
9 return $T=(V,F)$;