ASD Ćwiczenia 11

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Niech będzie grafem spójnym, a funkcją, która każdej krawędzi przypisuje nieujemną, całkowitoliczbową wagę . Dla każdego podgrafu definujemy wagę jako sumę wag jego krawędzi. Drzewo rozpinające grafu , którego waga jest nie większa od wagi każdego innego drzewa rozpinającego w tym grafie, nazywamy minimalnym drzewem rozpinającym grafu . 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

Zadanie 2

Załóżmy, że graf jest reprezentowany przez listy sąsiedztw i krawędzie grafu są już posortowane niemalejąco według wag. Zaproponuj algorytm, który w czasie obliczy dla G minimalne drzewo rozpinające.

Wskazówka

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 . 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 w czasie proporcjonalnym do długości tej ścieżki.

Rozwiązanie

Zadanie 4

Niech będzie spójnym grafem z wagami i niech będzie wyróżnionym wierzchołkiem. Dla każdego wierzchołka ustalmy jedną, najlżejszą ścieżkę łączącą z .

a) Niech będzie zbiorem wszystkich krawędzi występujących na ustalonych ścieżkach. Udowodnij, że podgraf jest drzewem. Drzewo 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