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 nieujemną, 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 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 $(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ędzi powoduje połączenia dwóch drzew (zbiorów) w jedno drzewa (jeden zbiór). Naturalną strukturą danych do implementacji dynamicznego lasu $T$ jest struktura zbiorów rozłącznych (Find-Union). Podany algorytm jest znany pod nazwą algorytmu Kruskala.

Zadanie 3

W przedstawionym przez nas algorytmie Dijkstry obliczaliśmy długości najlżejszych ścieżek łączących wszystkie wierzchołki grafu z wyróżnionym wierzchołkiem $s$. Zastanów się, w jaki sposób poprawić algorytm Dijkstry, żeby po zakończeniu jego działania można było dla każdego wierzchołka wyznaczyć najlżejszą ścieżkę łączącą ten wierzchołek z $s$ w czasie proporcjonalnym do długości tej ścieżki.

Rozwiązanie

Za każdym razem, gdy w wierszu 17 aktualizujemy wartość $w[v]$ na $w[u]+w(u-v)$, należy w zmiennej $p[v]$ zapamiętać wierzchołek $u$. Po zakończeniu wykonywania algorytmu najlżejszą ścieżkę z $v$ do $s$ tworzą wierzchołki $v,p[v],p[p[v]],\dots ,s$.

Zadanie 4

Niech $G=(V,E)$ będzie spójnym grafem z wagami $w$ i niech $s$ będzie wyróżnionym wierzchołkiem. Dla każdego wierzchołka $v\in V$ ustalmy jedną, najlżejszą ścieżkę łączącą $v$z$s$.

a) Niech $F$ będzie zbiorem wszystkich krawędzi występujących na ustalonych ścieżkach. Udowodnij, że podgraf $H=(V,F)$ jest drzewem. Drzewo $H$ nazywamy drzewem najlżejszych ścieżek. Może być wiele drzew najlżejszych ścieżek.

b) W rozwiązaniu zadania 3 pokazaliśmy, w jaki sposób obliczyć drzewo najlżejszych ścieżek algorytmem Dijkstry. Zmodyfikuj algorytm Dijsktry w taki sposób, żeby posłużył on do obliczania minimalnego drzewa rozpinającego.

Rozwiązanie

Wystarczy zmienić regułę przenoszenia wierzchołków ze zbioru $R$ do zbioru $L$. Do zbioru $L$ przenosimy ten wierzchołek z $R$, który jest połączony z wierzchołkiem z $L$ krawędzią o najmniejszej wadze. Ten algorytm jest znany pod nazwą algorytmu Prima.