Ćwiczenia

Niech \( G=(V,E) \) będzie grafem spójnym, a \( w:Earrow Z \) funkcją, która każdej krawędzi \( e \) przypisuje nieujemną, całkowitoliczbową wagę \( w(e) \). Dla każdego podgrafu \( G'=(V',E') \) definujemy wagę \( W(G') \) 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ą.

posortuj krawędzie według wag, od najmniejszej do największej, i niech 
//e_1, e_2,..., e_m będzie ciągiem posortowanych krawędzi. 
 F := emptyset; i := 0; 
 while |F|  <  n-1 do 
 begin 
   i := i+1; 
   if graf  (V,F cup {e_i}) nie zawiera cyklu then 
     F := F  cup {e_i} 
 end; 
 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]], \ldots, < math>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.