Poniżej zamieszczono zadania z klasówek nr 2 z lat poprzednich.
a) [6 punktów] Drzewo AVL nazywamy wysmukłym jeśli zawiera minimalną liczbę wierzchołków wśród drzew AVL 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.
b) [2 punkty] Podaj ciąg różnych liczb całkowitych, które po wstawieniu do początkowo pustego drzewa dadzą wysmukłe AVL-drzewo o wysokości 4. Kolejność liczb powinna być taka, żeby podczas całego procesu wstawiania wystąpiła dokładnie jedna pojedyncza rotacja.
c) [2 punkty] Podaj przykład 9-wierzchołkowego drzewa czerwono-czarnego, które nie jest AVL-drzewem.
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ą \( p(v) \) jako minimalną liczbę krawędzi niedrzewowych na ścieżce zorientowanej w \( H(G,T) \), prowadzącej z \( 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) \).
Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.
Zaprojektuj (efektywny) algorytm, który sprawdza, czy w danym grafie (zadanym przez listy sąsiedztwa) istnieje cykl bez powtarzających się krawędzi o długości parzystej.
Dany jest skierowany multigraf \( G=(V,E) \), reprezentowany przez listy sąsiedztwa. \( G \) jest regularny, co oznacza, że dla dowolnych dwóch wierzchołków \( u, v \), ich stopnie wejściowe oraz ich stopnie wyjściowe są takie same i parzyste.
Opisz algorytm, który podzieli zbiór krawędzi grafu \( G \) na 2 rozłączne zbiory \( E_1 \) i \( E_2 \) w taki sposób, że multigrafy \( G_1=(V, E_1) \) i \( G_2=(V, E_2) \) są regularne, oraz dla dowolnych wierzchołków \( u, v \), liczby krawędzi od \( u \) do \( v \) w \( G_1 \) i \( G_2 \) różnią się co najwyżej o 1.
Uwaga: na liście krawędzi wychodzących z wierzchołka \( u \), każda multikrawędź \( u \rightarrow v \) jest reprezentowana przez swój koniec \( v \) i liczbę określającą jej krotność. Tak więc rozmiar danych wynosi co najwyżej \( O(n^2) \).
Niech \( W \) będzie \( n \)-kątem wypukłym, którego wierzchołki ponumerowano kolejno \( 1, 2, \ldots, n \), zgodnie z ruchem wskazówek zegara. Zaproponuj strukturę danych, która umożliwi (wydajne) wykonywanie następujących operacji:
\( Przekątna(u,v) \):: sprawdza, czy w wielokącie \( W \) jest przekątna łącząca wierzchołki \(u, v\).
\( DodajPrzekątną(u,v)\):: umieść w wielokącie \( W \) przekątną łączącą wierzchołki \( u, v \), jeśli tylko takiej przekątnej nie ma w wielokącie i nowa przekątna nie przetnie się z żadną inną przekątną we wnętrzu wielokąta.
\( UsuńPrzekątną(u,v)\):: usuń przekątną łączącą \(u\) z \(v\), jeśli tylko taka przekątna jest w wielokącie.
Początkowo w wielokącie nie umieszczono żadnej przekątnej.
Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.