Omówienie zadania Zdjęcia krasnali (II etap XXVIII OI)

Dany jest graf o \(n\) wierzchołkach (reprezentujących krasnale) oraz \(m\) krawędziach (reprezentujących pary przyjaciół). Wszystkie wierzchołki w tym grafie mają parzyste stopnie. Rozstrzygnij, czy da się tak wpisać liczby od \(1\) do \(n\) w wierzchołki tego grafu, aby spełniona była następująca zależność: jeśli \(v\) jest wierzchołkiem (różnym od \(1\) i \(2\)), to wpisana w niego liczba jest medianą liczb wpisanych w \(v\) oraz jego sąsiadów. Jeśli istnieje taki układ, wypisz go na wyjście.

Analiza zadania

Załóżmy, że istnieje rozwiązanie i wierzchołkowi \(v\) przypisaliśmy numer \(N(v)\). Każdą krawędź w grafie skierujmy w ten sposób, że krawędź między wierzchołkami \(u\) i \(v\) kierujemy \(u\to v\), gdy \(N(u) < N(v)\). Wtedy każdy wierzchołek \(v\) (różny od \(1\) i \(2\)) będzie miał taką samą liczbę krawędzi wchodzących jak wychodzących (\(indeg(v) = outdeg(v) = \frac{deg(v)}{2}\)), bo z warunku na medianę wynika, że wśród sąsiadów \(v\) musi być połowa liczb mniejszych niż \(N(v)\) i połowa większych niż \(N(v)\). Łatwo też widać, że to skierowanie jest acykliczne (wynikowy graf jest DAG-iem).

Okazuje się, że jeśli udałoby się nam znaleźć takie acykliczne skierowanie, w którym do każdego wierzchołka (poza \(1\) i \(2\)) połowa krawędzi będzie wchodziła, a połowa z niego wychodziła, to będziemy w stanie również przypisać numery wierzchołkom (wystarczy to zrobić w kolejności topologicznej DAG-u).

Znajdowanie skierowania grafu

Możemy się więc skupić na znalezieniu odpowiedniego skierowania. Załóżmy dla uproszczenia, że graf jest spójny (w szczególności nie ma w nim wierzchołków izolowanych).

Jeśli \(N(v)=1\), to żadna krawędź nie będzie wchodzić do \(v\), zatem nie będzie on spełniał warunku na medianę. Zatem \(v=1\) lub \(v=2\) (i z symetrii wystarczy rozważyć tylko jeden z tych przypadków).

Tak więc początkowo wszystkie krawędzie wychodzące z wierzchołka \(1\) są skierowane od \(1\) do jego sąsiadów.

Teraz będziemy analizowali pozostałe wierzchołki. Jeśli dzięki skierowaniom powstał jakiś wierzchołek \(v \neq 2\), do którego skierowane jest już połowa jego sąsiadów (tzn. \(indeg(v) = \frac{deg(v)}{2}\)), to automatycznie wymusza to na nas, że wszystkie pozostałe krawędzie muszą być skierowane od \(v\) (czyli \(outdeg(v) = \frac{deg(v)}{2}\)). Powtarzamy to tak długo, jak długo istnieją wierzchołki spełniające powyższy warunek.

Jakie mogą powstać problemy podczas tego algorytmu?

• Jeśli w którymkolwiek momencie okazałoby się że do jakiegoś wierzchołka (prócz \(2\)) skierowaliśmy więcej niż połowę krawędzi, to wypisujemy ,,nie” (wszystkie skierowania są wymuszeniami z poprzednich skierowań, więc nie mogliśmy tej sytuacji uniknąć w żaden sposób).

• Jeśli algorytm zatrzymał się i nie wszystkie krawędzie zostały skierowane, to również wypisujemy ,,nie”. Wyrzućmy bowiem z grafu wszystkie skierowane krawędzie oraz wszystkie wierzchołki, których wszystkie krawędzie zostały już skierowane. Dowiadujemy się, że w pozostałym grafie do każdego wierzchołka (włącznie z wierzchołkiem \(2\)) musi zostać skierowana przynajmniej jedna z pozostałych krawędzi. To jednak oznacza, że w pozostałym grafie powstanie cykl.

Jeżeli w momencie zakończenia algorytmu wszystkie krawędzie zostały skierowane, to odpowiadamy ,,tak” i przypisanie numerów ustalamy sortowaniem topologicznym.

Implementacja

Powyższy algorytm jest bardzo podobny do algorytmu sortowania topologicznego z kolejką. Dla każdego wierzchołka będziemy trzymać licznik krawędzi, które do niego wchodzą.

Na początek na kolejkę wierzchołków do rozpatrzenia wrzucamy wierzchołek 1. Następnie wyciągamy z kolejki wierzchołek \(v\) i kierujemy pozostałe jego krawędzie do jego sąsiadów. Kiedy kierujemy jakąś krawędź \(v\to u\), to zwiększamy licznik wierzchołka \(u\) i jeśli licznik jest równy \(\frac{deg(u)}{2}\), to wrzucamy \(u\) na kolejkę.

Zarówno sortowanie topologiczne, jak nasz algorytm można zrealizować w czasie \(O(n+m)\) i taka jest złożoność rozwiązania.

Przypadek niespójnego grafu

Jeżeli w grafie mamy jakieś wierzchołki izolowane (o zerowym stopniu), to można im przypisać dowolne numery (i nie zajmować się nimi więcej). Przy czym trzeba uwzględnić przypadki szczególne, w którym wierzchołek \(1\) lub wierzchołek \(2\) są izolowane – wtedy odpowiedź jest ,,nie”, chyba że wszystkie wierzchołki w naszym grafie są izolowane i wtedy odpowiedź brzmi ,,tak”.

W przypadku, gdy mamy co najmniej dwie spójne składowe, z których każda zawiera jakąś krawędź, to odpowiedź będzie ,,nie”, gdyż łatwo pokazać, że dla co najmniej jednej spójnej składowej nie będziemy w stanie znaleźć odpowiedniego skierowania.

Rozwiązania wolne

Sprawdzamy wszystkie permutacje przydzieleń numerów do wierzchołków. Złożoność czasowa \(O(n! (n + m))\). Przechodzi podzadanie 1.

Sprawdzamy wszystkie możliwe skierowania krawędzi i dla każdego z nich przydzielamy numery wierzchołkom w kolejności topologicznej. Złożoność czasowa \(O(2^m (n + m))\). Przechodzi podzadanie 2.