Ć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.

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.

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.

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.