Olimpiada

Pora na zadanie o olimpiadzie! A przy okazji także o remontach dróg i terrorystach. Dla każdego wierzchołka podanego ważonego grafu nieskierowanego chcemy wyznaczyć koszt najtańszego drzewa rozpinającego, w którym ten wierzchołek jest liściem. Koszt drzewa definiujemy jednak trochę inaczej niż zwykle, bo interesuje nas maksymalna z wag jego krawędzi. Wierzchołki to oczywiście miasta, z których chcielibyśmy wybrać to, w którym zostaną zorganizowane kolejne igrzyska olimpijskie (rzecz jasna, bez żadnego referendum!). Po wybraniu miasta należy zmodernizować niektóre drogi tak, aby z każdego miasta dało się wygodnie dotrzeć na miejsce zawodów. Całą sprawę nieco utrudnia jednak to, że chcemy ulepszyć tylko jedną drogę bezpośrednio prowadzącą do wybranego miasta.

Opisany wyżej problem pojawił się jako zadanie D na 6 etapie rosyjskich zawodów XIV Open Cup. Oryginalną treść można zobaczyć tutaj. W tej oryginalnej treści warto zwrócić uwagę na limity, które jasno sugerują, że interesuje nas rozwiązanie o liniowym (lub prawie liniowym) czasie działania.

Już na samym początku naszą podejrzliwość powinna wzbudzić niecodzienna definicja minimalnego drzewa rozpinającego. Zamiast, tak jak zwykle, patrzeć na sumę kosztów krawędzi, interesuje nas ich maksimum. Można przypuszczać, że okaże się to kluczowe w uzyskaniu efektywnego rozwiązania. Lub że autor zadania był zwyczajnie złośliwy.

Dla każdego v chcemy wyznaczyć najtańsze drzewo rozpinające T_v, w którym wierzchołek v ma stopień 1. Naturalne wydaje się popatrzenie najpierw na najtańsze drzewo rozpinające T, w którym nie nakładamy żadnych warunków na stopnie wierzchołków. Mimo nieco niecodziennej definicji kosztu drzewa (bo, przypomnijmy, interesuje nas nie suma wag krawędzi, lecz ich maksimum), T można wyznaczyć dokładnie w taki sam sposób, co w standardowej wersji. Czyli, na przykład, sortując najpierw wszystkie krawędzie i rozważając je począwszy od najtańszej. Jeśli aktualnie rozważana krawędź łączy dwie różne składowe w skonstruowanym do tej pory lesie, dorzucamy ją do rozwiązania, w przeciwnym wypadku ignorujemy. Spójne składowe najprościej przechowywać w strukturze union-find, która umożliwia reprezentowanie dowolnej relacji równoważności tak, aby można było szybko dobrać się do nazwy klasy abstrakcji danego elementu, oraz skleić ze sobą dwie różne klasy abstrakcji. Obydwie operacje można zaimplementować bardzo efektywnie, o czym pewnie wiecie. Jeśli nie wiecie, wystarczy zajrzeć tutaj.

Po wyznaczeniu T można popatrzeć na jego liście. Jeśli v jest liściem w T, to T_v=T. Jeśli jednak tak nie jest, T_v może wyglądać zupełnie inaczej. Hmm, a może nie tak zupełnie inaczej?

Wyobraźmy sobie, że usuwamy z T wierzchołek v wraz ze wszystkimi przyległymi krawędziami. W rezultacie dostajemy jakiś las. Dość łatwo uwierzyć, że aby skonstruować T_v, wystarczy tylko dorzucić do tego lasu pewną liczbę krawędzi tak, aby stał się on spójny (pamiętając jednak o tym, że wolno dodać dokładnie jedną krawędź, której końcem jest v). Nie warto natomiast wyrzucać z niego jakichkolwiek krawędzi, czyli skonstruowanie całego T dało nam pewną wiedzę na temat tego, jak wyglądają poszczególne T_v. Ta wiedza nie wydaje się jeszcze, niestety, zbyt przydatna, gdyż składowych w lesie może być sporo, i nie widać jak sprytnie wybrać w optymalny sposób te dodatkowe krawędzie. Spróbujmy więc trochę inaczej.

Przypomnijmy, że interesuje nas nie tyle skonstruowanie całego T_v, co wyznaczenie jego kosztu. Być może warto więc zacząć od skonstruowania efektywnego sposobu na sprawdzenie, czy ten koszt jest co najwyżej C. Z tej sztuczki korzystaliśmy już kilka razy: zamiast wyliczać X wprost, możemy zastosować wyszukiwanie binarne, w którym potrzebna jest tylko szybka metoda, która pozwala na wykonanie testu postaci „czy X\leq C?”. W naszym przypadku wykonanie takiego testu sprowadza się do wyrzucenia z grafu wszystkich krawędzi, których koszty przekraczają C, a następnie sprawdzenia, czy korzystając z tych pozostałych można wybrać drzewo rozpinające, w którym v jest liściem, co okazuje się być dość proste.

Lemat. Drzewo rozpinające, w którym v jest liściem, istnieje wtedy i tylko wtedy gdy cały graf jest spójny i v nie jest punktem artykulacji.

Dowód. Jeśli graf nie jest spójny, nie istnieje żadne drzewo rozpinające. Jeśli zaś v jest punktem artykulacji, po jego usunięciu utworzymy przynajmniej dwie spójne składowe, czyli podpinając v do pozostałej części grafu jedną krawędzią nie uda nam się otrzymać jednej dużej spójnej składowej. Jeśli zaś graf jest spójny, a v nie jest punktem artykulacji, to po jego usunięciu graf dalej będzie spójny. Czyli możemy wybrać dowolne drzewo rozpinające w grafie powstałym przez usunięcie v z tego oryginalnego, a następnie podpiąć v dowolną z przyległych do niego krawędzi.

Otrzymaliśmy więc dość prosty sposób na sprawdzenie, dla których v koszt T_v nie przekracza C. Wystarczy tylko wyrzucić zbyt drogie krawędzie i wyznaczyć punkty artykulacji w pozostałej części grafu. Punkty artykulacji można wyznaczyć w czasie \mathcal{O}(n+m), czyli całkiem szybko, ale nie daje to jeszcze efektywnego rozwiązania całego zadania. Przypomnijmy bowiem, że dla każdego v chcemy znaleźć najmniejsze C, dla którego koszt T_v nie przekracza C. Kuszące wydaje się wybranie C, które leży mniej więcej w połowie (cokolwiek miałoby to znaczyć), wyznaczenie zbioru L = \{v : \text{koszt } T_v \text{ jest} \leq C \} oraz R = \{v : \text{koszt } T_v \text{ jest} > C \}, a następnie rekurencyjne wywołanie się dla tych dwóch zbiorów. Niestety wygląda na to, że w każdym wywołaniu jesteśmy zmuszeni płacić \mathcal{O}(n+m) niezależnie od tego, dla ilu v chcemy znaleźć koszt T_v. O ile można mieć nadzieję, że m będzie coraz mniejsze na kolejnych poziomach wywołań rekurencyjnych, o tyle n raczej zostaje takie samo. Chyba że zrobimy coś sprytnego… ale może lepiej spróbować trochę inaczej?

Zamiast szukać binarnie najmniejszego C, wyobraźmy sobie, że zaczynamy z pustym grafem, i dodajemy krawędzie jedną po drugiej począwszy od najtańszej. W pewnym momencie graf stanie się spójny, co pozwala nam wyznaczyć koszt T_v tych v, które nie są punktami artykulacji. Następnie kontynuujemy dodawanie krawędzi. Jeśli tuż po dodaniu krawędzi o koszcie C wierzchołek v przestanie być punktem artykulacji, koszt T_v to dokładnie C. Czyli tak naprawdę potrzebujemy zaimplementować strukturę danych, która pozwoli nam na dodawanie nowych krawędzi i sprawdzanie, które wierzchołki przestają być punktami artykulacji. Takie spojrzenie na problem jest o tyle fajne, że pozwala nam zapomnieć o kosztach, czyli w pewnym sensie zmniejszyć liczbę wymiarów problemu. Ale czy na pewno staje się on przez to prostszy?

Skoro chcemy zaimplementować strukturę danych, w której przechowujemy (w jakiś niekoniecznie jawny sposób) punkty artykulacji, pewnie trzeba by powiedzieć coś o ich własnościach. W tym wypadku wygodne okazuje się myślenie o dwuspójnych składowych jako o relacji równoważności na krawędziach. Mówimy, że krawędzie e i e' są w tej samej klasie abstrakcji, jeśli istnieje prosty cykl, na którym leży zarówno e jak i e'. Nie jest do końca oczywiste, że rzeczywiście jest to relacja równoważności, i że taka definicja jest zgodna z tą częściej spotykaną (w której dwuspójna składowa jest maksymalnych podgrafem, który pozostaje spójny po usunięciu dowolnego wierzchołka), ale chyba darujemy sobie dowód. Byłby nudny i pewnie bym się w nim pomylił. Teraz wierzchołek jest punktem artykulacji dokładnie wtedy, gdy dwie przyległe do niego krawędzie należą do różnych klas abstrakcji.

Teraz wyobraźmy sobie sytuację po dorzuceniu do grafu nowej krawędzi. Pewnie jest tak, że może to spowodować sklejenie pewnych klas abstrakcji. Ale których? Żeby szybko odpowiedzieć na to pytanie, potrzebna jest jeszcze jedna obserwacja. Przypomnijmy, że informacja o punktach artykulacji potrzebna jest nam dopiero wtedy, gdy cały graf staje się spójny. Można więc udawać, że zaczynamy nie z pustym grafem, lecz z najtańszym drzewem rozpinającym T, do którego dodajemy kolejne krawędzie (zarówno te, które dodaliśmy przed tym, gdy graf stał się spójny, jak i te, które dodaliśmy po). Nie zmieni to ostatecznego kosztu żadnego T_v o ile będziemy pamiętać, by wypisać maksimum z kosztu T_v i T. Zaczynamy więc z jakimś drzewem T, no i dorzucamy do niego kolejne krawędzie. Jak w takim wypadku wyglądają dwuspójne składowe? Są poddrzewami T! (poddrzewo oznacza tu spójny kawałek T)

Spróbujmy to udowodnić. Na samym początku każda krawędź jest singletonem. Załóżmy, że w danym momencie każda dwuspójna składowa jest poddrzewem T i zastanówmy się, jak zmienia sytuację dodanie nowej krawędzi e=(u,v). Zmienia pewnie tak, że umożliwia utworzenie nowego cyklu prostego, który składa się ze ścieżki łączącej u i v w drzewie oraz e, tak jak na poniższym rysunku, na którym poszczególne klasy abstrakcji są oznaczone różnymi kolorami.

olimpiada1

Czyli powinniśmy skleić ze sobą wszystkie klasy równoważności, do których należą krawędzie na ścieżce z u do v. Po chwili zastanowienia można uwierzyć, że nie trzeba sklejać niczego więcej. Skoro mówimy o klasach równoważności, to pewnie chcielibyśmy przechowywać je w strukturze union-find, czyli samo sklejanie jest proste. No, prawie: musimy wiedzieć co skleić! A to być może nie jest takie całkiem trywialne, bo przecież na pewno nie stać nas na przejrzenie całej ścieżki…

Na szczęście można nieco sprytniej. Wyobraźmy sobie, że całe drzewo jest ukorzenione. Można w dość prosty sposób zmodyfikować implementację struktury union-find tak, aby dla każdej klasy równoważności przechowywała ten z wierzchołków odpowiadającego jej poddrzewa, który znajduje się najbliżej korzenia. To zaś umożliwia przejrzenie tylko tej części ścieżki, na której dzieje się coś ciekawego, czyli mamy dwie kolejne krawędzie różnych kolorów. Zamiast bardziej precyzyjnego opisu jak wygenerować tę część, proponuję rysunek.

olimpiada2

Oczywiście dalej jest tak, że być może będziemy zmuszeni do przejrzenia całej ścieżki. Jednak jeśli każda przejrzana krawędź oznacza sklejenie dwóch klas abstrakcji (no, może poza tą ostatnią na każdej z dwóch „gałęzi”), czyli zamortyzowany koszt każdej aktualizacji to stała liczba operacji na strukturze union-find. Pozostaje jednak kwestia wykrywania, kiedy wierzchołek przestaje być punktem artykulacji. (Pozostaje też mniej interesująca kwestia sformalizowania procedury przedstawionej na rysunku, co wymaga uważnego rozpatrzenia wszystkich szczególnych przypadków. Darujemy sobie.)

Przypomnijmy, że wierzchołek jest punktem artykulacji dokładnie wtedy, gdy dwie z przyległych do niego krawędzi należą do różnych klas abstrakcji. Każda z aktualizacji sprowadza się do wykonania pewnej liczby operacji typu: sklej ze sobą klasy abstrakcji, do których należą dwie krawędzie o wspólnym końcu. Nasuwa to dość naturalne i wręcz trywialne rozwiązanie kwestii przechowywania punktów artykulacji. Dla każdego z nich przechowujemy licznik, który mówi nam, do ilu różnych klas abstrakcji należą przyległe do niego krawędzie. Każda z operacji powoduje zmniejszenie pewnego licznika o jeden. Gdy tylko zauważymy, że jakiś licznik spadł do 1, odpowiadający mu wierzchołek przestaje być punktem artykulacji.

To tyle. Uzyskaliśmy rozwiązanie, które sprowadza się do wykonania \mathcal{O}(m) operacji na strukturze union-find, czyli o czasie działania dość bliskim liniowemu. Można więc spokojnie pomyśleć nad wersją, w której koszt drzewa to suma kosztów jego krawędzi!

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s