Wielka Przesmycka Reloaded 2011 - omówienie zadań

22.11.2011

D Mrówki

To zadanie okazało się być trudniejsze niż się spodziewaliśmy. Co prawda poprawne rozwiązanie wersji professional faktycznie wymaga kilku nietrywialnych spostrzeżeń, ale wersji basic wydawała nam się możliwa do rozwiązania przez zgadnięcie (dość prostego) warunku na istnienie rozwiązania.

W zadaniu jesteśmy proszenie o sprawdzenie, czy krawędzie danego grafu nieskierowanego można zorientować w ten sposób, że otrzymany graf skierowany jest acykliczny, a w dodatku dla każdego wierzchołka $ v $ spełnione są dwa warunki:

  • krawędź $ u\rightarrow v $ istnieje dla jakiegoś $ v $ wtedy i tylko wtedy gdy $ v\neq 1 $,
  • krawędź $ v\rightarrow u $ istnieje dla jakiegoś $ v $ wtedy i tylko wtedy gdy $ v \neq n $.

Lub inaczej ujmując kwestię, $ 1 $ jest jedynym źródłem, a $ n $ jedynym ujściem. Takie zorientowanie będziemy nazywali interesującym. W wersji professional musimy nie tylko sprawdzić, czy takie uporządkowanie istnieje, ale także je podać.

Zacznijmy od banalnej obserwacji: niespójne grafy na pewno nie mają interesującego uporządkowania. Dlaczego? Przede wszystkim skoro otrzymany graf skierowany ma być acykliczny, można go posortować topologicznie. Jeśli popatrzymy się następnie na dowolną spójną składową, ten z jej wierzchołków, który jest pierwszy (ostatni) topologicznie, nie ma żadnych wchodzących (wychodzących) krawędzi. Czyli jeśli jest więcej niż jedna składowa, muszą pojawić się przynajmniej dwa źródła i ujścia.

Powyższa obserwacja jest dość jasną (co nie znaczy, że poprawną) wskazówką, że spójność grafu odgrywa kluczową rolę jeśli chodzi o istnienie interesującej orientacji. Skoro niespójne grafy nie posiadają takiej orientacji, to może powinniśmy przyjrzeć się takim, które są tylko odrobinę spójne? Czyli na przykład takim, w których istnieje most (krawędź, której usunięcie rozspaja graf). Niestety samo istnienie mostu jeszcze o niczym nie świadczy. Jeśli jednak wyobrazimy sobie sytuację podobną do tej z rysunku 6, dość łatwo przekonać się, że oznacza ona brak interesującej orientacji.

Rysunek 6: Obecnosc krawędzi $ e $ uniemożliwia interesujaca orientację.

Dlaczego? Cóż, jeśli w grafie niezależnie od ustalenia kierunków wszystkich krawędzi w składowej "po drugiej stronie" $ e $ na pewno jeden wierzchołek będzie źródłem lub ujściem (a dokładniej, jest to oczywiste jeśli składowa składa się z tylko jednego wierzchołka, a w przeciwnym wypadku jeśli rozważymy samą składową bez $ e $, to będzie można w niej znaleźć źródło i ujście, dołożenie $ e $ umożliwia pozbycie nam pozbycie się co najwyżej jednego z nich). Podobne rozumowanie można przeprowadzić w bardziej ogólnej sytuacji gdy w grafie istnieje wierzchołek rozspajający. Inaczej mówiąc, jeśli po dołożeniu krawędzi $ 1-n $ cały graf nie jest dwuspójny, interesująca orientacją nie jest możliwa.

Mamy więc pierwszy pomysł na rozwiązanie. Dokładamy krawędź $ 1-n $ i sprawdzamy dwuspójność. Okazuje się, że taki algorytm jest już poprawny. Aby rozwiązać wersję basic nie trzeba było tego udowodniać, ale oczywiście zwykła ludzka podejrzliwość nie pozwala nam na przyjęcie tak śmiałego twierdzenia na wiarę. Dość łatwo je udowodnić korzystając z następującego (znanego) faktu: każdy dwuspójny graf ma dekompozycję na uszy. O co w tym chodzi? O dość prostą rzecz: każdy dwuspójny graf można skontruować zaczynając od cyklu prostego i następnie dokładając do tego co już mamy "uszy", czyli ścieżki, które są wewnętrznie rozłączne z tym co już mamy (o różnych końcach!). Co więcej, ten początkowy cykl można wybrać tak, aby przechodził przez ustaloną krawędź, powiedzmy $ 1-n $. A skoro tak, to na podstawie takiej dekompozycji możemy łatwo skonstruować orientację. Cały czas przechowujemy liniowy porządek na dotychczas skonstruowanym grafie. Krawędzie na cyklu początkowym orientujemy od $ 1 $ do $ n $. Dla każdego ucha ustawiamy jego krawędzie w jedyny możliwy sposób, który będzie zgodny z dotychczasowym porządkiem na końcach (i uzupełniamy ten porządek wstawiając wszystkie nowe wierzchołki wewnętrzne). Bardzo łatwo przerobić ten szkic dowodu na rozwiązanie działające w czasie $ \mathcal{O}(n^{2}+m) $, ale... ale jak właściwie znaleźć rozkład na uszy?

Okazuje się, że nie jest to takie trudne, ale niestety trzeba dobrze rozumieć jak działa przeszukiwanie w głąb w grafach nieskierowanych. Wiadomo, że używając go możemy podzielić wszystkie krawędzie na drzewowe i wsteczne. Każda (poza jedną użytą do skonstruowania początkowego cyklu prostego) krawędź wstecz definiuje nowe ucho (być może trywialne). Czytelnikowi pozostawiamy przyjemność dopowiedzenia szczegółów tego pomysłu (wymaga to tylko porządnego zrozumienia algorytmu sprawdzania dwuspójności).

Niestety powyższy pomysł nie prowadzi jeszcze bezpośrednio do akceptowalnego rozwiązania. Co prawda dekompozycję na uszy można nie tak trudno skonstruować w czasie liniowym, ale konieczność przechowywania aktualnego liniowego porządku na wierzchołkach, a konkretnie jego aktualizacji, istotnie zwiększa złożoność. W takiej najbardziej naiwnej implementacji do $ \mathcal{O}(n^{2}+m) $, przy użyciu jakichś drzew zrównoważonych do $ \mathcal{O}(m\log n) $. Okazuje się, że istnieje jednak dość proste (gdy już się je zna) rozwiązanie liniowe. Wystarczy trochę uważniej przyjrzeć się jak dokładnie uaktualniamy porządek na wierzchołkach...

Przyzwoitość wypada zdradzić, że takie orientowanie krawędzi grafu wcale nie jest tak bezużyteczne jak mogłoby się wydawać. Korzysta się z niego na przykład podczas sprawdzania planarności grafu.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com