Przydatne drogi

W tym roku nie znalazłem wystarczająco ciekawego zadania o torcie urodzinowym, będzie więc takie o grafie skierowanym. Zadanie pochodzi z tegorocznej edycji NEERC Southern Subregional (co wróży raczej dobrze) i, w zależności od tego, czy zna się pewien trik, czy też nie, jest bardzo trudne lub zupełnie standardowe.

Treść można sobie zobaczyć tutaj. W skrócie: dostajemy graf skierowany na n wierzchołkach i m krawędziach. Dla każdej krawędzi u\rightarrow v interesuje nas, czy istnieje ścieżka prosta prowadząca z 1 do v kończąca się tą krawędzią, gdzie „ścieżka prosta” oznacza ścieżkę, na której każdy wierzchołek pojawia się co najwyżej raz. Limity podane w treści jasno sugerują, że należy celować w rozwiązanie działające w czasie bliskim liniowemu.

Zacznijmy od przeformułowania warunku nałożonego na interesujące nas krawędzie. Przed wszystkim, warto zacząć od usunięcia z grafu wszystkich wierzchołków, które nie są osiągalne z 1. (Od tego momentu będziemy myśleć, że nie ma takich wierzchołków.) Wtedy dla dowolnej krawędzi u\rightarrow v na pewno istnieje jakaś ścieżka łącząca z 1 do u. A więc taka krawędź nie jest dla nas interesująca dokładnie wtedy, gdy wszystkie ścieżki z 1 do u przechodzą przez v.

No i być może kiedyś widzieliście już takie warunek. Zwykle w takiej sytuacji mówi się, że v dominuje u. Mając daną jedną parę (u,v) możemy łatwo sprawdzić, czy u dominuje v w czasie \mathcal{O}(m): wystarczy bowiem przeszukać graf startując z 1 i za wszelką cenę unikając u… no ale raczej nie ma to szansy dać nam akcepta. Może więc lepiej byłoby najpierw wyznaczyć wszystkie takie pary, a dopiero później sprawdzić, dla każdej krawędzi u\rightarrow v, czy (v,u) należy do wyznaczonego zbioru?

Może i lepiej, ale od razu pojawia się drobny kłopot: przecież taki zbiór może być bardzo duży: wystarczy wyobrazić sobie długą ścieżkę. Czyli nawet jeśli potrafilibyśmy szybko wyznaczyć cały zbiór, nie jesteśmy w stanie go jawnie przechowywać. Okazuje się jednak, że istnieje lepszy sposób.

Lemat 1. Jeśli u i u' dominują v, to u dominuje u' lub u' dominuje u.

Dowód. Z założenia dowolna ścieżka z 1 do v przechodzi zarówno przed u jak i u'. Nie może być tak, że na niektórych takich ścieżkach u występuje przed u‚, a na niektórych na odwrót: można by wtedy skonstruować ścieżkę z 1 do v, która nie przechodzi przez u (a także taką, która nie przechodzi przez u'). Powiedzmy więc, że na każdej ścieżce z 1 do v wierzchołek u występuje przed u'. Wtedy musi być tak, że każda ścieżka z 1 do u' przechodzi przez u, bo w przeciwnym wypadku moglibyśmy skonstruować ścieżkę z 1 do v, która nie przechodzi przez u'. ∎

Z powyższego lematu (i tego, że relacja „u dominuje v” jest częściowym porządkiem) wynika, że dla każdego wierzchołka v istnieje jednoznacznie wyznaczony wierzchołek dominujący dom(v) o takiej własności, że wierzchołki dominujące v to dokładnie v, dom(v), dom(dom(v))), \ldots. Lub, mówiąc inaczej, całą sytuację możemy reprezentować przy pomocy drzewa ukorzenionego w 1, w którym ojcem v jest dom(v), a wierzchołki dominujące v to dokładnie jego przodkowie. Przykład takiego drzewa dominacji znajduje się poniżej.

przydatne1

Drzewo dominacji jest o tyle wygodne, że zajmuje tylko \mathcal{O}(n) pamięci (pomińmy na razie niewygodną kwestię jego konstrukcji). Mając drzewo, dla każdej krawędzi u\rightarrow v trzeba tylko sprawdzić, czy v jest przodkiem u w drzewie. W tym celu najwygodniej ponumerować wierzchołki drzewa przechodząc je w głąb i nadając każdemu wierzchołkowi v numer pre[v] i post[v] (bardziej formalnie: wchodząc do v ustawiamy pre[v]=t, gdzie t to aktualny czas, a wychodząc z v przypisujemy post[v]=t), a następnie sprawdzić, czy pre[v] \leq pre[u] < post[v] w czasie \mathcal{O}(1). Dla przykładu z powyższego rysunku dostaniemy wtedy, że jedyna nieinteresująca krawędź to 10 \rightarrow 5.

Ale jak skonstruować drzewo? Nie wydaje się to oczywiste. No i nie jest: ludzkości wykombinowanie efektywnego rozwiązania zajęło kilka lat (a niektórzy dalej uważają, że lepiej jest używać dobrze zoptymalizowanego \mathcal{O}(n^2), ale… nawet nie będę tego komentował). W roku 1979 Lengauer i Tarjan podali algorytm, który konstruuje drzewo dominacji w czasie \mathcal{O}(m\alpha(m,n)). Oryginalny opis jest na tyle jasny, że zaimplementowanie algorytmu nie powinno zająć doświadczonemu zawodnikowi wiele czasu. Być może jednak warto podać kilka intuicji.

Jasne jest, że dom(v) jest przodkiem v w drzewie przeszukiwania w głąb (bo, w szczególności, takie drzewo pozwala na dotarcie do v zaczynając 1). Drzewo przeszukiwania w głąb dla grafu z poprzedniego przykładu jest zaznaczone na czerwono na poniższej ilustracji.

przydatne2

W zasadzie moglibyśmy wybrać inne drzewo ukorzenione w 1 (na przykład drzewo przeszukiwania wszerz), i dalej byłoby to prawdą. Jak jednak okaże się już za chwilę, lepiej myśleć o drzewie przeszukiwania w głąb. Zamiast wyznaczać dla każdego wierzchołka v jego dom(v), wprowadźmy nową defnicję wierzchołka prawie-dominującego sdom(v). Jak wskazuje nazwa, jest to osłabiona wersja wierzchołka dominującego. Wyliczenie wszystkich sdom(v) okaże się prostsze niż myślenie o dom(v), a ponadto przy odrobinie wysiłku mając już wszystkie sdom(v) będziemy w stanie wyliczyć dom(v).

Mówimy, że u < v gdy u jest odwiedzony przed v w naszym przeszukiwaniu w głąb (lub, jak kto woli, pre[u] < pre[v]). Teraz sdom(v) jest zdefiniowany jako najmniejszy u (w sensie relacji <), dla którego istnieje ścieżka startująca w u i kończąca się w v, której wszystkie wierzchołki wewnętrzne są większe niż v. Mamy teraz taki nie do końca oczywisty fakt.

Lemat 2. sdom(v) jest przodkiem v w drzewie przeszukiwania w głąb.

Dowód. Na pewno sdom(v) < v, gdyż możemy wybrać ścieżkę złożoną z jednej krawędzi od ojca v. Załóżmy, że sdom(v) nie jest przodkiem v. Skoro sdom(v) < v, sytuacja wygląda tak jak na poniższej ilustracji.

przydatne4

u \neq sdom(v),v jest najniższym wspólnym przodkiem sdom(v) i v w drzewie (u \neq sdom(v) wynika z założenia, a u \neq v z tego, że sdom(v) < v), a u' jest pierwszym wierzchołkiem wewnętrznym na ścieżce z sdom(v) do u. Na pewno u' > v. Ale w takim razie u' powinien zostać odwiedzony po sdom(v), a jakby nie był, sprzeczność. ∎

Czyli sdom(v) jest jednym z przodków v w drzewie przeszukiwania w głąb, tak jak na poniższym rysunku. Rysunek jest bardzo podobny do tego przedstawiającego drzewo dominacji, ale niestety nie identyczny.

przydatne3

Okazuje się jednak, że mając drzewo prawie-dominacji można wyznaczyć drzewo dominacji. Można też efektywnie wyznaczyć drzewa prawie-dominacji. Obydwie części nie są jednak trywialne ani oczywiste, i w tym momencie warto zainteresować się oryginalnym artykułem.

Reklamy

5 myśli nt. „Przydatne drogi

  1. Dzięki za link do treści. Bez tego nie mogłem skumać o co chodzi w zdaniu „Dla każdej krawędzi u\rightarrow v interesuje nas, czy istnieje ścieżka prosta prowadząca z 1 do v” – proponuję dodać w tym zdaniu „zawierająca tę krawędź” 🙂

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