2. Klasówka 2002/03#
Zadanie 1 [8 punktów]#
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 := X \cup \{x\}\)
\(Delete(X, x) ::\) \(X := X \setminus \{x\}\)
\(Closest(X) ::\) return \(\min_{x, y \in X,\ x \neq y} |x - y|\)
Opisz algorytm wykonywania poszczególnych operacji i zanalizuj ich złożoność.
Zadanie 2 [7 punktów]#
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 [5 punktów]#
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.