2. Klasówka 2013/14#
Zadanie 1#
Dla dodatniej liczby całkowitej \(n\), drabiną \(D_n\) nazywamy graf nieskierowany o \(2n\) wierzchołkach, ponumerowanych \(1, 2, \cdots, 2n\), i krawędziach postaci:
\((2i - 1)-(2i)\), dla każdego \(i = 1, 2, \cdots, n\) oraz
\((2i - 1)-(2i + 1), (2i)-(2i + 2)\), dla każdego \(i = 1, 2, \cdots,n - 1\).
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.
Ile jest różnych BFS-drzew w drabinie \(D_5\) o korzeniu w wierzchołku \(5\)?
Ile jest różnych DFS-drzew w drabinie \(D_5\) o korzeniu w wierzchołku \(5\)?
Ile jest różnych BFS-drzew w drabinie \(D_n\) o korzeniu w wierzchołku \(1\)?
Zadanie 2#
Dla dodatniej liczby całkowitej \(n\), drabiną \(D_n\) nazywamy graf nieskierowany o \(2n\) wierzchołkach, ponumerowanych \(1, 2, \cdots, 2n\), i krawędziach postaci:
\((2i - 1)-(2i)\), dla każdego \(i = 1, 2, \cdots, n\) oraz
\((2i - 1)-(2i + 1), (2i)-(2i + 2)\), dla każdego \(i = 1, 2, \cdots,n - 1\).
Załóżmy, że każdej krawędzi \(e\) drabiny \(D_n\) przypisano dodatnią, całkowitoliczbową wagę \(w(e)\). Zaproponuj efektywny algorytm obliczania najlżejszej ścieżki z wierzchołka \(1\) do wierzchołka \(2n\).
Zaproponuj strukturę danych, która na drabinie \(D_n\) 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#
Do początkowo pustego AVL-drzewa wstawiamy kolejno klucze \(1, 2, \cdots, n\), gdzie \(n\) jest dodatnią liczbą całkowitą. Podaj klucze, które kiedykolwiek znajdą się w korzeniach kolejno powstających drzew.