Wymagania i kryteria oceniania
Należy zaimplementować algorytm wyznaczający centroid albo dekompozycję centroidową zadanego drzewa oraz opanować (ze zrozumieniem) dotyczącą go teorię. Centroidem drzewa o V wierzchołkach nazywamy taki wierzchołek c, którego usunięcie rozbija drzewo na spójne części, z których każda zawiera co najwyżej ⌊V/2⌋ wierzchołków. Centroid c nazywamy rozdzielającym części powstałe po jego usunięciu, oraz rozdzielającym wierzchołki leżące w różnych częściach. Każde drzewo ma albo jeden centroid albo dwa połączone krawędzią.
Program powinien wczytać drzewo (np. do list sąsiedztwa) albo mieć je wprowadzone na stałe w programie. Ocena zależy od wybranego wariantu.
Warianty
Wyznaczanie centroidu drzewa (na ocenę 3)
Należy zaimplementować algorytm wyznaczający centroid drzewa (dowolny z dwóch, jeśli drzewo ma dwa) o V wierzchołkach w czasie O(V).
Dekompozycja centroidowa i najkrótsze ścieżki (na ocenę 4,5)
Należy zaimplementować dekompozycję centroidową drzewa (z nieujemnymi wagami na krawędziach) oraz wykorzystać ją do wyznaczania długości najkrótszej ścieżki (sumy wag krawędzi) pomiędzy zadaną parą wierzchołków. Dekompozycja centroidowa polega na rekurencyjnym wyznaczaniu centroidu: najpierw wyznaczamy centroid c całego drzewa, następnie usuwamy go z drzewa (wraz z incydentnymi krawędziami) i powtarzamy tę procedurę dla każdej z powstałych spójnych części. W ten sposób powstaje drzewo centroidowe, którego korzeniem jest c, a poddrzewami – dekompozycje kolejnych części. Dekompozycję (wraz z niezbędnymi odległościami) należy zbudować w czasie O(V log(V)). Można ją zapamiętać w postaci V ścieżek w drzewie centroidowym, od c do każdego wierzchołka, czyli list przodków centroidowych mających po O(log(V)) elementów (łącznie O(V log(V)) elementów); każdy element przechowuje m.in. odległość do danego przodka w wejściowym drzewie. Wyznaczenie odległości pomiędzy parą wierzchołków powinno mieć złożoność czasową O(log(V)).
Odtwarzanie ścieżki (na ocenę 5)
Dodatkowo program powinien wypisywać nie tylko długość, ale i samą najkrótszą ścieżkę (ciąg odwiedzanych wierzchołków od zadanego wierzchołka początkowego do końcowego). Zakładając że centroid rozdzielający jest już znaleziony, odtworzenie ścieżki powinno działać w czasie proporcjonalnym do liczby wierzchołków, przez które ta ścieżka przechodzi.
Wskazówka: do odtworzenia ścieżki warto – dla każdego wierzchołka i każdego jego przodka centroidowego – zapamiętać sąsiada (poprzednika) tego wierzchołka na ścieżce w kierunku tego przodka; można go wyznaczyć podczas przeszukiwania (DFS) prowadzonego z centroidu. Umożliwia to przejście o jeden wierzchołek w kierunku centroidu rozdzielającego w czasie O(1), a w konsekwencji odtworzenie całej ścieżki w czasie proporcjonalnym do jej długości.
Przykładowe pytania sprawdzające
Dla wszystkich wariantów
- Co to jest centroid drzewa? Jaką własność spełnia? Ile centroidów może mieć drzewo i dlaczego każde drzewo ma centroid?
- Zilustrować działanie zaimplementowanego algorytmu dla zadanego drzewa.
- Jaka jest złożoność czasowa i pamięciowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie (pętle, rekurencje), które za to odpowiadają.
- Jak działa użyte przeszukiwanie drzewa (np. DFS) i dlaczego działa w czasie O(V)?
Dla wariantu wyznaczania centroidu (na ocenę 3)
- W jaki sposób, znając rozmiary poddrzew, stwierdzić, czy dany wierzchołek jest centroidem?
- Jak wyznaczyć centroid, gdy znane są już rozmiary poddrzew? Dlaczego wystarczy zejść w kierunku „cięższej” części?
Dla wariantu z dekompozycją centroidową (na ocenę 4,5 oraz 5)
- Jak działa rekurencyjna budowa dekompozycji centroidowej? Jaka jest głębokość powstałego drzewa centroidowego?
- Dlaczego każdy wierzchołek ma O(log(V)) przodków centroidowych, a budowa dekompozycji (wraz z wyznaczeniem odległości) działa w czasie O(V log(V))?
- Jak zbudowana jest struktura wspomagająca – jakie informacje przechowujemy o wierzchołkach?
- Jak odpowiadać na zapytanie o długość najkrótszej ścieżki w czasie O(log(V)) (zilustrować przykładem)? Dlaczego wystarczy rozważyć jeden, odpowiednio wybrany centroid (rozdzielający oba wierzchołki) i dlaczego leży on na ścieżce łączącej te wierzchołki?
Dla wariantu z odtwarzaniem ścieżki (na ocenę 5)
- Zilustrować sposób odtwarzania najkrótszej ścieżki dla przykładowych danych.
- Jaka jest złożoność odtwarzania ścieżki? Odpowiedź uzasadnić.