ASD Ćwiczenia 11

From Studia Informatyczne

Niech G=(V,E) będzie grafem spójnym, a w:E\rightarrow 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.

Spis treści

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 := \emptyset; 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]], \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.