2. Klasówka 2003/04#
Zadanie 1#
Grafem trójkątnym nazywamy każdy graf płaski (graf narysowany na płaszczyźnie, w którym jednymi wspólnymi punktami różnych krawędzi są ich końce) zdefiniowany następująco:
trójkąt jest grafem trójkątnym;
jeżeli \(G\) jest grafem trójkątnym, to graf otrzymywany z \(G\) przez umieszczenie wierzchołka (punktu) wewnątrz dowolnej ściany wewnętrznej (trójkąta bez żadnych wierzchołków w jego wnętrzu) i połączenie go odcinkami z wierzchołkami tej ściany, jest też grafem trójkątnym;
żaden inny graf nie jest grafem trójkątnym.
Zaproponuj strukturę danych, która umożliwia efektywne wykonywanie następujących operacji na dynamicznym trójkątnym grafie \(G\):
\(Ini\):: inicjalizacja grafu \(G\) jako pojedynczego trójkąta o wierzchołkach ponumerowanych \(1, 2, 3\); ta operacja jest wykonywana tylko raz na samym początku;
\(Dodaj(a, b, c)\):: sprawdź, czy w grafie \(G\) istnieje cykl elementarny (trójkąt) \([a, b, c]\); jeśli tak i wewnątrz tego cyklu (trójkąta) nie leżą żadne inne wierzchołki grafu, to dodaj nowy wierzchołek wewnątrz trójkąta \([a, b, c]\), połącz go krawędziami (odcinkami) z wierzchołkami \(a, b, c\) i nadaj mu etykietę równą najmniejszej dodatniej liczbie całkowitej różnej od pozostałych etykiet wierzchołków w grafie;
\(Usun(a, b, c)\):: sprawdź, czy w \(G\) istnieje cykl elementarny (trójkąt) \([a, b, c]\); jeśli tak, to usuń z \(G\) wszystkie wierzchołki leżące wewnątrz cyklu (trójkąta) \([a, b, c]\) oraz krawędzi incydentne z tymi wierzchołkami;
\(Ile(a, b, c)\):: sprawdź, czy w grafie istnieje cykl elementarny (trójkąt) \([a, b, c]\); jeśli tak, to podaj liczbę wierzchołków leżących wewnątrz cyklu (trójkąta) \([a, b, c]\).
Uzasadnij poprawność swojego rozwiązania i dokonaj analizy czasów wykonywania poszczególnych operacji.
Zadanie 2#
W \(n\)-węzłowym drzewie poszukiwań binarnych liczba węzłów zewnętrznych (,,nili”) wynosi \(n + 1\). Każdy nowy klucz zajmuje pozycje jednego z węzłów zewnętrznych. Zaprojektuj efektywny algorytm, który dla danego AVL-drzewa sprawdzi, ile jest w nim węzłów zewnętrznych, w których umieszczenie klucza wymaga wykonania rotacji w celu przywrócenia własności AVL-drzewa. Należy przyjąć, że atrybutami każdego węzła wewnętrznego są: \(klucz\), \(lewy\_syn\), \(prawy\_syn\), \(wskaznik\_zrownowazenia\).
Do drzewa odwołujemy się przez korzeń. Uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoność czasowej zaproponowanego algorytmu.