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

Wykaż, ż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)$; 

Zadanie 2

Załóżmy, że graf $G$ jest reprezentowany przez listy sąsiedztw i krawędzie grafu są już posortowane niemalejąco według wag. Zaproponuj algorytm, który w czasie $O(n{\log }^{*}n)$ obliczy dla G minimalne drzewo rozpinające.

Wskazówka

Wykorzystaj algorytm podany we wskazówce do zadania 1. W trakcie działania tego algorytmu graf $T=(V,F)$ jest lasem, czyli zbiorem rozłącznych drzew. Zbiory wierzchołków drzew w lesie tworzą podział zbioru $V$. Żeby sprawdzić, czy dołączenie nowej krawędzi do lasu powoduje powstanie cyklu, wystarczy wiedzieć, czy końce tej krawędzi łączą wierzchołki w tym samym drzewie (zbiorze). Dodanie krawędzie powoduje połączenia dwóch drzew (zbirów) w jedno (jeden). Naturalną strukturą danych do implementacji dynamicznego lasu $T$ jest struktura zbiorów rozłącznych (Find-Union).