2. Klasówka 2010/11#
Zadanie 1#
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#
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.
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.