2. Klasówka 2008/09

Zadanie 1

Słowa kluczowe: struktury danych; AVL

1. AVL-drzewo nazywamy wysmukłym, jeśli zawiera minimalną liczbę wierzchołków wśród AVL-drzew o wysokościach równych wysokości tego drzewa. Udowodnij, że wierzchołki każdego wysmukłego AVL-drzewa można pokolorować w taki sposób, żeby otrzymać drzewo czerwono-czarne.

2. Podaj ciąg różnych, dodatnich liczb całkowitych, które po wstawieniu do początkowo pustego drzewa dadzą wysmukłe AVL-drzewo o wysokości \(3\). Kolejność liczb powinna być taka, żeby podczas całego procesu wstawiania wystąpiła dokładnie jedna pojedyncza rotacja. Uwaga: wysokość drzewa mierzy się liczbą krawędzi od korzenia do najdalszego liścia.

3. Podaj przykład \(9\)-wierzchołkowego drzewa czerwono-czarnego, które nie jest AVL-drzewem.

Zadanie 2

Słowa kluczowe: grafy; DFS

Niech \(G\) będzie grafem dwuspójnym wierzchołkowo o co najmniej \(3\) wierzchołkach i niech \(T\) będzie DFS-drzewem rozpinającym grafu \(G\). Przez \(H_{G, T}\) oznaczamy graf zorientowany otrzymany z \(G\) przez zorientowanie wszystkich krawędzi drzewowych w kierunku od ojca do syna, a krawędzi niedrzewowych w kierunku od potomka do przodka.

Dla każdego wierzchołka \(v\) w grafie \(G\) definiujemy liczbę powrotną w grafie \(H_{G, T}\) jako minimalną liczbę krawędzi niedrzewowych na ścieżce zorientowanej w \(H_{G, T}\), prowadzącej od \(v\) do korzenia drzewa \(T\).

Załóżmy, że graf \(G\) jest reprezentowany przez listy sąsiedztwa. Zaproponuj algorytm, który w czasie liniowym wyznacza pewne DFS-drzewo \(T\) w grafie \(G\) i oblicza dla każdego wierzchołka jego liczbę powrotną w \(H_{G, T}\). Uzasadnij poprawność swojego rozwiązania.