2. Klasówka 2010/11

Zadanie 1

Słowa kluczowe: sortowanie, Find-Union

Mamy \(n\) stałych funkcji \(f_i\): \([a_i, b_i] \leftarrow \{1, \cdots ,n\}\), \(1 \leq a_i \leq b_i \leq n\). Zaproponuj algorytm obliczenia maksimum z wartości \(f_i(j)\), dla każdego \(j\) z \(\{1, 2, \cdots, n\}\) i tych funkcji \(f_i\), które zawierają \(j\) w swojej dziedzinie. Jeśli takiej funkcji nie ma, to za maksimum przyjmujemy \(0\). Uwagi: rozwiązania w czasie \(O(n \log n)\) będą punktowane za maksimum \(7\) punktów; 11 punktów można uzyskać za rozwiązanie w czasie \(o(n \log n)\).

Zadanie 2

Słowa kluczowe: grafy

1. Niech \(G\) będzie grafem \(n+1\) wierzchołkowym, \(n > 4\), w którym jeden wierzchołek jest połączony ze wszystkimi innymi, a podgraf rozpięty na pozostałych \(n\) wierzchołkach jest cyklem elementarnym. Ile jest różnych drzew przeszukiwania w głąb w grafie \(G\) - dwa drzewa się różnią, jeśli istnieje wierzchołek, który w obu drzewach ma różnych ojców. Opisz sposób obliczania tej liczby.

2. Niech \(G=(V,E)\) będzie grafem dwuspójnym o co najmniej trzech wierzchołkach, a \(u\) jego wyróżnionym wierzchołkiem. Dobrą orientacją grafu \(G\) z wierzchołka \(u\) nazywamy graf skierowany otrzymany z \(G\) w następujący sposób: uruchomiamy algorytm przeszukiwania w głąb z wierzchołka \(u\), a następnie orientujemy krawędzie drzewa przeszukiwania od ojca do syna, a krawędzie niedrzewowe od potomka do przodka.

   Dany jest graf zorientowany \(H\) z wyróżnionym wierzchołkiem \(u\). Zaproponuj algorytm, który stwierdzi, czy \(H\) jest dobrą orientacją pewnego grafu \(G\) z wierzchołka \(u\).

Uzasadnij poprawność swoich rozwiązań i dokonaj analizy ich złożoności obliczeniowej.