2. Klasówka 2002/03#
Zadanie 1#
Zaprojektuj strukturę danych umożliwiającą wykonywanie na skończonym zbiorze liczb rzeczywistych \(X\) następujących operacji:
\(Empty(X) ::\) \(X := \emptyset\)
\(Insert(X) ::\) \(X := X \cup x\)
\(Delete(X, x) ::\) \(X := X - x\)
\(Closest(X) ::\) return \(min_{x \neq y} | x - y]\)
Opisz algorytm wykonywania poszczególnych operacji i zanalizuj ich złożoność.
Zadanie 2#
Dany jest spójny, nieskierowany graf \(G = (V, E)\) i zbiór krawędzi \(F\subseteq E\) pewnego drzewa rozpinającego. Zaproponuj efektywny algorytm, który sprawdza, czy można tak zbudować listy sąsiedztwa dla grafu \(G\), żeby krawędzie z \(F\) były krawędziami DFS-drzewa rozpinającego \(G\) o korzeniu w wierzchołku \(1\). (Uwaga: zakładamy, że V = \(\{ 1, 2, \cdots, n \}\) i że graf \(G\) jest dany przez listy sąsiedztwa.) Uzasadnij poprawność i przeanalizuj złożoność swojego rozwiązania.
Zadanie 3#
Kaktusem nazywamy graf spójny, w którym każda dwuspójna składowa jest cyklem elementarnym. Rozważamy kaktusy z wagami na krawędziach. Zaproponuj efektywny algorytm obliczania minimalnego drzewa rozpinającego w kaktusie z wagami. Uzasadnij poprawność i przeanalizuj złożoność swojego rozwiązania.