Lekcja_11 - algorytmy na grafach1. Algorytmy na grafach2. Algorytmy na grafach(w przygotowaniu)WyjścieAlgorytmy na grafach1. (1p) Niech G będzie grafem o 5 wierzchołkach ponumerowanych od 1 do 5. Koszt krawędzi (i,j) definiujemy jako c(i,j) = (i+j) div 2. c(i,j) = 0 oznacza brak krawędzi (i,j). Jaki jest koszt minimalnego drzewa rozpinającego otrzymanego w wyniku działania algorytmu Kruskala dla grafu G? 12 4 6 8Zastanów się! Jaki jest koszt minimalnego drzewa rozpinającego grafu o 25 wierzchołkach i krawędziach zdefiniowanych jak w powyższym grafie?2. (1p) Niech G będzie grafem niezorientowanym o pięciu wierzchołkach ponumerowanych od 1 do 5. Koszt krawędzi (i,j) wynosi (i+j) mod 5. Jeśli (i+j)mod5 = 0, to wierzchołki i, j nie są połączone krawędzią. Jakie krawędzie tworzą minimalne drzewo rozpinające grafu G? Zastosuj algorytm Kruskala. (1,2), (2,3), (3,4) (1,2), (2,4), (4,3), (3,5) (1,5), (2,4), (2,5), (3,4) (1,5), (5,4), (4,3), (3,2)3. (1p) W jakiej kolejności odwiedzane są wierzchołki grafu G (z poprzedniego pytania) metodą DFS, jeśli odwiedzanie zaczynamy od wierzchołka 1, a listy incydencji grafu są uporządkowane rosnąco? 1, 2, 3, 4, 5 1, 3, 5, 4, 2 1, 2, 4, 3, 5 1, 5, 4, 3, 2 1, 2, 4, 5, 34. (1p) Niech G będzie grafem o 6 wierzchołkach {0,1,2,3,4,5} i krawędziach E określonych następująco: (a,b) należy do E wttw, gdy w(a,b) >0, gdzie w(a,b) = (a+b) mod 3. Jaki jest koszt minimalnego drzewa rozpinającego w tym grafie, jeżeli wagą krawędzi (a,b) jest w(a,b). 5 6 7 175. (1p) Rozważmy graf z poprzedniego pytania reprezentowany jako tablica list incydencji. Zakładamy, że wierzchołki na listach incydencji występują w kolejności rosnących numerów. W jakiej kolejności odwiedzane będą wierzchołki tego grafu, jeśli odwiedzanie zaczynamy od wierzchołka o numerze 0? Kolejność 0,1,3,2,5,4, jeśli zastosowano metodę BFS. Kolejność 0,1,3,2,5,4, jeśli zastosowano rekurencyjną metodę DFS. Kolejność 0,1,2,3,4,5, jeśli zastosowano metodę DFS z użyciem stosu, zamiast rekursji.6. (1p) Jaki jest koszt algorytmu Kruskala zastosowanego do grafu o n wierzchołkach i m krawędziach? O(m x lg n) n x lg m O( n x n) O(m x m>7. (1p) Ile krawędzi znajduje się w lesie rozpinającym, złożonym z k drzew o n1 , n2 ,..., nk wierzchołkach? n1 * n2 *... * nk n1 * n2 *... * nk -1 n1 + n2 +... + nk n1 + n2 +... + nk -1 n1 + n2 +... + nk – k8. (1p) Które ze zdań jest prawdziwe? Algorytm Kruskala i algorytm Dijkstry zawsze wyznaczają takie samo drzewo rozpinające. Drzewo rozpinające otrzymane w wyniku algorytmu Kruskala ma koszt nie większy niż koszt drzewa najkrótszych ścieżek otrzymanego algorytmem Dijkstry. Scieżka łącząca dwa wierzchołki w minimalnym drzewie rozpinającym jest najkrótszą ścieżką między tymi wierzchołkami.Zadanie Rozważmy strukturę Find-Union zaimplementowaną na drzewach z kompresją ścieżek i z balansowaniem. Niech nazwami zbiorów będą korzenie drzew, które reprezentują te zbiory, a operacja Union wykonywana na dwóch drzewach o tej samej wysokości daje w wyniku drzewo, którego korzeniem jest korzeń drzewa o mniejszej etykiecie. Jak zmienia się wysokość drzewa tworzonego w wyniku wykonania (w tej strukturze) instrukcji następującego algorytmu. Przed wykonaniem algorytmu, wartością P jest początkowy podział zbioru {1,2,3,4,5,6,7,8}. Algorytm:{ for i:=1 to 4 do P := Union(P,2i-1,2i) od; P:= Union(P,1,3); P:=Union(P,5,7); P:= Union(P,1,5); Find (P,8); Find(P,4); Find(P,6);} Po wykonaniu pętli Po wykonianiu instrukcji Union(P,1,3), najwyższe drzewo podziału ma wysokość 2. Po wykonaniu wszystkich instrukcji Union otrzymamy dwa drzewa. Wynikiem wykonania wszystkich operacji Union jest drzewo o wysokości 3. Instrukcje Find nie zmieniają struktury drzewa, zatem po wykonaniu pierwszej instrukcji Find, wysokość drzewa nie zmieni się. W wyniku wykonania wszystkich instrukcji otrzymamy drzewo o wysokości 2. W wyniku wykonania wszystkich instrukcji otrzymamy drzewo o wysokości 1. Czy koszt algorytmu Kruskala znajdowania minimalnego drzewa rozpinającego grafu zależy istotnie od sposobu implementacji struktury Find-Union?NieTak9. (1p) Niech G będzie grafem o 5 wierzchołkach ponumerowanych od 1 do 5. Koszt krawędzi (i,j) definiujemy jako c(i,j) = (i+j) mod 2. c(i,j) = 0 oznacza brak krawędzi (i,j). Jaki jest koszt minimalnego drzewa rozpinającego otrzymanego w wyniku działania algorytmu Kruskala dla grafu G?8745Odpowiedzi :  Wyniki