ASD Ćwiczenia 11: Różnice pomiędzy wersjami

Aktualna wersja na dzień 10:18, 31 sie 2023

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^{'} = (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ą.

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]], \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.

@@ Linia 1: / Linia 1: @@
-Niech <math>G=(V,E)</math> będzie grafem spójnym, a <math>w:E\rightarrow Z</math> funkcją, która każdej krawędzi <math>e</math> przypisuje nieujemą, całkowitoliczbową wagę <math>w(e)</math>. Dla każdego podgrafu <math>G'=(V',E')</math> definujemy wagę <math>W(G')</math> jako sumę wag jego krawędzi. Drzewo rozpinające grafu <math>G</math>, którego waga jest nie większa o od wagi każdego innego drzewa rozpinającego w tym grafie nazywamy minimalnym drzewem rozpinającym grafu <math>G</math>. W grafie może być więcej niż jedno drzewo rozpinające.
+Niech <math>G=(V,E)</math> będzie grafem spójnym, a <math>w:E\rightarrow Z</math> funkcją, która każdej krawędzi <math>e</math> przypisuje nieujemną, całkowitoliczbową wagę <math>w(e)</math>. Dla każdego podgrafu <math>G'=(V',E')</math> definujemy wagę <math>W(G')</math> jako sumę wag jego krawędzi. Drzewo rozpinające grafu <math>G</math>, którego waga jest nie większa od wagi każdego innego drzewa rozpinającego w tym grafie, nazywamy ''minimalnym drzewem rozpinającym'' grafu <math>G</math>. W grafie może być więcej niż jedno drzewo rozpinające.
 ==Zadanie 1==
@@ Linia 7: / Linia 7: @@
 Wskazówka
 <div class="mw-collapsible-content" style="display:none">
-Wykaż, że następujący algorytm zachłanny oblicza minimalne drzewo rozpinające dla spójnego grafu <math>G=(V,E)</math>, a następnie wykaż, że gdy wagi są parami różne, to każde inne drzewo ma wagę większą.
+Udowodnij, że następujący algorytm zachłanny oblicza minimalne drzewo rozpinające dla spójnego grafu <math>G=(V,E)</math>, 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
@@ Linia 15: / Linia 15: @@
 '''begin'''
    <math>i := i+1</math>;
-   '''if''' graf <math>(V,F\cup \{e_i}\})</math> nie zawiera cyklu '''then'''
+   '''if''' graf <math>(V,F\cup \{e_i\})</math> nie zawiera cyklu '''then'''
      <math>F := F \cup \{e_i\}</math>
 '''end''';
@@ Linia 30: / Linia 30: @@
 <div class="mw-collapsible-content" style="display:none">
-Wykorzystaj algorytm podany we wskazówce do zadania 1. W trakcie działania tego algorytmu graf <math>T=(V,F)</math> jest lasem, czyli zbiorem rozłącznych drzew. Zbiory wierzchołków drzew w lesie tworzą podział zbioru <math>V</math>. Ż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ędzie powoduje połączenia dwóch drzew (zbirów) w jedno (jeden). Naturalną strukturą danych do implementacji dynamicznego lasu <math>T</math> jest struktura zbiorów rozłącznych (Find-Union).
+Wykorzystaj algorytm podany we wskazówce do zadania 1. W trakcie działania tego algorytmu graf <math>T=(V,F)</math> jest lasem, czyli zbiorem rozłącznych drzew. Zbiory wierzchołków drzew w lesie tworzą podział zbioru <math>V</math>. Ż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 <math>T</math> jest struktura zbiorów rozłącznych (Find-Union). Podany algorytm jest znany pod nazwą algorytmu Kruskala.
 </div>
 </div>
-'''Zadanie 3'''
+==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 <math>s</math>. 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 <math>s</math> w czasie proporcjonalnym do długości tej ścieżki.
+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 <math>s</math>. 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 <math>s</math> w czasie proporcjonalnym do długości tej ścieżki.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">
@@ Linia 42: / Linia 42: @@
 <div class="mw-collapsible-content" style="display:none">
-Za każdym razem, gdy w wierszu 17 aktualizujemy wartość <math>w[v]</math> na <math>w[u]+w(u-v)</math> należy w zmiennej <math>p[v]</math> zapamiętać wierzchołek <math>u</math>. Po zakończeniu wykonywania algorytmu najlżejszą ścieżkę z <math>v</math> do <math>s</math> tworzą wierzchołki <math>v, p[v], p[p[v]], \ldots, <math>s</math>.
+Za każdym razem, gdy w wierszu 17 aktualizujemy wartość <math>w[v]</math> na <math>w[u]+w(u-v)</math>, należy w zmiennej <math>p[v]</math> zapamiętać wierzchołek <math>u</math>. Po zakończeniu wykonywania algorytmu najlżejszą ścieżkę z <math>v</math> do <math>s</math> tworzą wierzchołki <math>v, p[v], p[p[v]], \ldots, s</math>.
 </div>
 </div>
-```Zadanie 4```
+==Zadanie 4==
-Niech <math>G=(V,E)</math> będzie spójnym grafem z wagami <math>w</math> i niech <math>s</math> będzie wyróżnionym wierzchołkiem. Dla każdego wierzchołka <math>v \in V</math> ustalmy jedną, najlżejszą ścieżkę łączącą <math>v</math> z <math>s</math>.
+Niech <math>G=(V,E)</math> będzie spójnym grafem z wagami <math>w</math> i niech <math>s</math> będzie wyróżnionym wierzchołkiem. Dla każdego wierzchołka <math>v \in V</math> ustalmy jedną, najlżejszą ścieżkę łączącą <math>v</math>z<math>s</math>.
-a) Niech <math>F</math> będzie zbiorem wszystkich krawędzi występujących na ustalonych ścieżkach. Udowodnij, że podgraf <math>H=(V,F)</math> jest drzewem. Drzewo <math>H</math> nazywamy ```drzewem najlżejszych ścieżek```. Może być wiele drzew najlżejszych ścieżek.
+a) Niech <math>F</math> będzie zbiorem wszystkich krawędzi występujących na ustalonych ścieżkach. Udowodnij, że podgraf <math>H=(V,F)</math> jest drzewem. Drzewo <math>H</math> 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.
@@ Linia 58: / Linia 58: @@
 <div class="mw-collapsible-content" style="display:none">
-Wystarczy zmienić regułę przenoszenia wierzchołków ze zbioru <math>R</math> do <math>L</math>. Do zbioru <math>L</math> przenosimy ten wierzchołek z <math>R</math>, który jest połączony  z wierzchołkiem z <math>L</math> krawędzią o najmniejszej wadze.
+Wystarczy zmienić regułę przenoszenia wierzchołków ze zbioru <math>R</math> do zbioru <math>L</math>. Do zbioru <math>L</math> przenosimy ten wierzchołek z <math>R</math>, który jest połączony  z wierzchołkiem z <math>L</math> krawędzią o najmniejszej wadze. Ten algorytm jest znany pod nazwą algorytmu Prima.
 </div>
 </div>

ASD Ćwiczenia 11: Różnice pomiędzy wersjami

Aktualna wersja na dzień 10:18, 31 sie 2023

Spis treści

Zadanie 1

Zadanie 2

Zadanie 3

Zadanie 4

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia