ASD – Klasówka 2
15.01.2011

Zadanie 1 [11 punktów]

Mamy n stałych funkcji fi: [ai,bi]->{1,...,n}, 1≤ai≤bi≤n. Zaproponuj algorytm obliczenia maksimum z wartości fi(j), dla każdego j z {1, 2, ..., n} i tych funkcji fi, które zawierają j w swojej dziedzinie. Jeśli takiej funkcji nie ma, to za maksimum przyjmujemy 0.

Uwagi: rozwiązania w czasie O(nlog n) będą punktowane za maksimum 7 punktów; 11 punktów można uzyskać za rozwiązanie w czasie o(nlog n).

Zadanie 2 [9 punktów]

a)[3 punkty]
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.

b)[6 punktów]
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.