ASD – klasówka II
13.01.2013

W zadaniach 1 i 2 obiektem badań jest graf nazywany drabiną. Dla dodatniej liczby całkowitej n, drabiną Dn nazywamy graf nieskierowany o 2n wierzchołkach, ponumerowanych 1,2, …, 2n, i krawędziach postaci:

(2i-1)–(2i), dla każdego i = 1,2, …n, oraz
(2i-1)–(2i+1), (2i)–(2i+2), dla każdego i =1, …, n-1.

Drabina D5 ma postać:
                  1        3        5        7       9

                  2        4        6        8      10

Zadanie 1 [6 pkt]

Na potrzeby tego zadania BFS-drzewem o korzeniu w wyróżnionym wierzchołku s nazywamy każde drzewo w którym ojciec każdego węzła v różnego od s jest pierwszym węzłem na pewnej najkrótszej ścieżce z v do s, natomiast DFS-drzewem o korzeniu w wierzchołku s nazywamy każde drzewo, w którym krawędzie niedrzewowe łączą potomków z przodkami.
O dwóch drzewach z korzeniami, rozpiętych na tych samych zbiorach wierzchołków, mówimy, że są różne, gdy co najmniej jeden wierzchołek ma różnych ojców w obu drzewach.

a)	[1 pkt] Ile jest różnych BFS-drzew w drabinie D5 o korzeniu w wierzchołku 5?
b)	[2 pkt] Ile jest różnych DFS-drzew w drabinie D5 o korzeniu w wierzchołku 5?
c)	[3 pkt] Ile jest różnych BFS-drzew w drabinie Dn o korzeniu w wierzchołku 1?

Zadanie 2 [8 pkt]

a)	[3 pkt] Załóżmy, że każdej krawędzi e drabiny Dn przypisano dodatnią, całkowitoliczbową wagę w(e). Zaproponuj efektywny algorytm obliczania najlżejszej ścieżki z wierzchołka 1 do wierzchołka 2n.
b)	[5 pkt] Zaproponuj strukturę danych, która na drabinie Dn z wagami umożliwia efektywne wykonywanie następujących operacji:
Ini: zainicjuj strukturę danych; pierwsza operacja, wykonywana tylko raz;
Zmień(e,y):: zmień wagę krawędzi e na nową o wartości y;
Najlżejsza:: podaj wagę najlżejszej ścieżki z wierzchołka 1 do wierzchołka 2n.

Zadanie 3 [6 pkt]

Do początkowo pustego AVL-drzewa wstawiamy kolejno klucze 1, 2, …, n, gdzie n jest dodatnią liczbą całkowitą. Podaj klucze, które kiedykolwiek znajdą się w korzeniach kolejno powstających drzew.

Uwaga: uzasadnij poprawność swoich rozwiązań oraz dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów. Rozwiązanie każdego zadania oddajemy na osobnej kartce (kartkach).

Rozwiązania

Zadanie 1

a)
Każde BFS drzewo o wierzchołku 5 ma 4 warstwy. Rozważmy warstwy na lewo od 5 (na prawo symetrycznie). Ojcem 3 i 6 jest zawsze 5, ojcem 1 jest zawsze 3. Ojcem 4 może być 3 lub 6, zaś ojcem 2 wierzchołek 1 lub wierzchołek 4. Zatem drzew „na lewo” jest 4. Podobnie drzew na prawo jest 4. Zatem wszystkich 16.

b)
Rozważmy dwa przypadki. 
1: Krawędź 5-6 jest krawędzią drzewową. Wówczas część grafu na lewo od 6 można przeszukać na dwa sposoby. Podobnie na prawo od 6. To daje 4 różne drzewa.
2: Krawędź 5-6 nie jest krawędzią drzewową. Załóżmy, że krawędzią drzewową jest 5-3. Wówczas lewą część grafu można przeszukać na 2 sposoby. Z szóstki prawą część grafu można przeszukać też na dwa sposoby. To daje nam 4 drzewa z krawędzią 5-3. Symetrycznie mamy 4 drzewa z krawędzią 5-7. Zatem w rozważanym przypadku mamy łącznie 8 drzew.
Odpowiedź: 12 drzew.
c)
Możliwych drzew jest 2n-1. Indukcja po liczbie warstw w drzewie. Warstwy numerujemy od 1. Od warstwy i-tej (wierzchołki 2i-1 oraz 2i-2, dla i > 1) do warstwy (i+1)-szej (wierzchołki 2i+1 oraz 2i) można przejść na dwa sposoby – ojcem wierzchołka 2i może być wierzchołek 2i-1 lub 2i-2). Ojcem wierzchołka 2i+1 musi być 2i-1.

Zadanie 2

a)
Parę wierzchołków 2i-1, 2i nazwiemy i-tym szczeblem drabiny. Zauważmy, że najlżejsza ścieżka z wierzchołka 1 do wierzchołka 2n ma taką własność, że musi przejść przez wszystkie szczeble (co najmniej jeden wierzchołek ze szczebla) oraz po osiągnięciu wierzchołka ze szczebla i, nigdy nie wraca do wcześniejszych szczebli (ponieważ wagi są dodatnie). Może za to przejść do drugiego wierzchołka tego samego szczebla. Zatem algorytm jest prosty: obliczamy wagi W2i-1 oraz W2i najlżejszych ścieżek z wierzchołka 1 do wierzchołków odpowiednio 2i-1 oraz 2i w drabinie 
Di, a następnie rozszerzamy nasze obliczenia na drabinę Di+1. Najlżejsza ścieżka do wierzchołka 2i+1 jest lżejszą ze ścieżek: z 1 do 2i-1 rozszerzoną o krawędź (2i-1)-(2i+1) lub z 1 do 2i rozszerzoną o krawędzie (2i)-(2i+2) i (2i+2)-(2i+1). Podobnie wyznaczamy wagę najlżejszej ścieżki z 1 do 2i+2 w Di+1. W ten sposób dostajemy algorytm działający w czasie liniowym.

b)
Dla 1<=i<=j<n blokiem Bi,j nazwiemy fragment drabiny zaczynający się na szczeblu i-tym i kończący na szczeblu j-tym. Wierzchołek 2i-1 nazywamy górnym lewym końcem tego bloku, a wierzchołek 2i jego dolnym lewym końcem. Podobnie niech wierzchołek 2j-1 będzie górnym prawym końcem tego bloku, a 2j jego dolnym prawym końcem. Niech B i B’ będą blokami takimi, że skrajnie prawy szczebel w B jest skrajnie lewym szczeblem w B’. Jeśli znamy wagi najlżejszych ścieżek pomiędzy skrajnie lewymi i skrajnie prawymi końcami w blokach B i B’, to w czasie stałym natychmiast wyznaczamy wagi najlżejszych ścieżek pomiędzy skrajnie lewymi i skrajnie prawymi końcami bloku będącym „sumą” bloków B i B’. Dalej to już łatwe. Budujemy pełne drzewo binarne, w którego liściach są kolejno od lewej bloki B1,2, B2,3, …, Bn-1,n. Każdy węzeł wewnętrzny reprezentuje blok, który jest sumą bloków w jego liściach. W każdym węźle pamiętamy wagi najlżejszych ścieżek pomiędzy skrajnie lewymi i skrajnie prawymi końcami bloku reprezentowanego przez ten węzeł. Budowa drzewa bloku (Ini) zajmuje czas O(n). Wagę najlżejszej ścieżki doczytujemy z korzenia drzewa (czas O(1)). Zmiana wagi krawędzi polega na przejściu w górę drzewach i aktualizacji wag najlżejszych ścieżek pomiędzy skrajnymi końcami bloków zawierającymi tę krawędź – czas O(log n).

Zadanie 3

Rozwiązywanie tego zadania należy zacząć od wstawienia kilkunastu elementów i zauważyć, że korzeniami drzew mogą być tylko kolejne potęgi dwójki. Dla n > 1, największą taką potęgą jest największe 2k takie, że 2k+2k-1<=n. Na początku w korzeniu jest 1. Dla i>0, 2i pojawia się po raz pierwszy w korzeniu po wstawieniu klucza 2i+2i-1. Wówczas w lewym poddrzewie jest pełne drzewo o 2i-1 elementach, a w prawym poddrzewem jest pełne drzewo o 2i-1-1 elementach z doczepionym skrajnie prawym liściem. Ostatni raz 2i jest w korzeniu po wstawieniu klucza min(n, 2i+1+2i-1). Gdy tym kluczem jest 2i+1+2i-1, to lewe poddrzewo jest pełnym drzewem binarnym o 2i-1 elementach, a prawe poddrzewo pełnym drzewem binarnym pełnym drzewem binarnym o 2i+1-1 elementach. Reszta dowodu, to indukcja po i, czyli kluczach w korzeniu.