Exodus superbohaterów

Na kolejny nieciekawy grudniowy wieczór proponuję ciekawe zadanie o superbohaterach z ostatnich Mistrzostw Wielkopolski w Programowaniu Zespołowym, w którym jesteśmy proszeni o pokolorowanie wierzchołków dość specyficznie skonstruowanego grafu. Ponieważ całe zadanie jest o superbohaterach, kolorowanie także nie będzie takie całkiem zwyczajne!

Oryginalną treść można zobaczyć tutaj. Dostajemy graf skierowany na n \leq 10^{5} wierzchołkach oraz m \leq 2n-3 krawędziach. Każdemu wierzchołkowi musimy przyporządkować jeden z siedmiu kolorów, dla wygody oznaczmy kolor wierzchołka u przez c(u). Tak jak w standardowym kolorowaniu, wierzchołki połączone ze sobą krawędzią muszą otrzymać różne kolory (nie jest tutaj istotny kierunek tej krawędzi). Ponieważ jednak graf jest skierowany (a zadanie o superbohaterach), mamy jeszcze jeden warunek: nie może zdarzyć się tak, że w grafie istnieją dwie krawędzie u_1 \rightarrow v_1 oraz u_2 \rightarrow v_2 takie, że c(u_1)=c(v_2) oraz c(u_2)=c(v_1). Zapomnijmy jednak na chwilę o tym dość egzotycznym warunku. Samo pokolorowanie danego grafu siedmioma kolorami nie brzmi zbyt prosto! Na szczęście autorzy obiecują, że podany graf powstał następujący sposób: zaczynając od pojedynczej krawędzi wykonujemy n-2 kroków, w których dokładamy nowy wierzchołek połączony z dwoma już istniejącymi sąsiednimi wierzchołkami. Po zakończeniu całego procesu wymazujemy niektóre (być może żadne) z utworzonych krawędzi. Widać, że stąd bierze się ograniczenie 2n-3 na liczbę krawędzi.

Zapomnijmy na chwilę o tym, że nasz graf jest skierowany. Czy potrafilibyśmy znaleźć poprawne (w tradycyjnym sensie) kolorowanie wiedząc, że graf został utworzony poprzez dokładanie nowych wierzchołków w opisany wyżej sposób, lecz nie znając kolejności, w jakiej były one dokładane? Być może wystarczy znaleźć i usunąć wierzchołek stopnia co najwyżej dwa, rekurencyjnie pokolorować nowy mniejszy graf, a potem wybrać kolor usuniętego wierzchołka tak, aby był różny od kolorów jego (co najwyżej dwóch) sąsiadów. Widać, że taka procedura nigdy nie użyje więcej niż trzech kolorów, ale czy na pewno jest poprawna? Wiemy, że w oryginalnym grafie na pewno istnieje wierzchołek stopnia co najwyżej dwa. Jeśli mamy do czynienia z pierwotnym grafem, z którego usunęliśmy niektóre wierzchołki, wciąż na pewno istnieje w nim wierzchołek stopnia co najwyżej dwa: jest to na przykład ten jeszcze nieusunięty wierzchołek, który został dodany najpóźniej (w procesie konstrukcji). Czyli procedura jest poprawna, ale jak uogólnić ją na grafy skierowane?

Przypomnijmy, że po przejściu do grafu skierowanego musimy zadbać nie tylko o to, żeby wierzchołki połączone krawędzią były pomalowane na różne kolory, ale mamy także dodatkowy warunek, który wygodnie sformułować w odrobinę inny sposób: dla każdej pary kolorów 1 \leq i < j \leq 7 musimy zdecydować, czy dopuszczamy krawędzie z wierzchołka o kolorze i do wierzchołka o kolorze j czy też na odwrót (nazwijmy to ustaleniem kolejności kolorów). Po ustaleniu kolejności kolorów naturalne wydaje się zmodyfikowanie procedury opartej na usuwaniu wierzchołków stopni co najwyżej dwa. Teraz musimy jednak staranniej wybrać kolor usuniętego wierzchołka w zależności od kierunków krawędzi łączących go z już pokolorowanymi sąsiadami. Nie jest jasne, czy zawsze jest to możliwe i pewnie jakoś zależy od wybranej kolejności kolorów. Nawet ignorując ten problem pojawia się inna trudność: być może usunięty wierzchołek ma stopień dwa, obydwaj z jego sąsiadów zostali pomalowani na ten sam kolor, ale prowadzące do nich krawędzie mają różne kierunki. W takiej sytuacji raczej przegraliśmy.

Powiedzmy jednak, że mieliśmy szczęście i żadne krawędzie nie zostały wymazane, to znaczy m=2n-3. Zauważmy, że usuwając z takiego grafu wierzchołki stopnia dokładnie dwa niekoniecznie odtworzymy pierwotną konstrukcję, jednak obaj sąsiedzi usuwanego wierzchołka na pewno będą połączeni krawędzią. A to oznacza, że w tej uproszczonej wersji zadania druga ze wspomnianych wyżej trudności nie istnieje. Jak jednak wybierać kolory usuwanych wierzchołków?

Kuszącą hipotezą wydaje się założenie, że istnieje "uniwersalna" kolejność kolorów, dla której zawsze można dobrać kolor usuniętego wierzchołka tak, żeby było dobrze. Co to właściwie znaczy? Kolejność kolorów to tak naprawdę turniej na 7 wierzchołków (czyli graf skierowany, w którym każda para wierzchołków jest połączona dokładnie jedną krawędzią). Przydałby nam się turniej o następującej własności: dla dowolnych dwóch z jego wierzchołków u,v istnieją wierzchołki x_1,x_2,x_3,x_4 takie, że w turnieju istnieją następujące krawędzie:

  1. x_1 \rightarrow u, x_1 \rightarrow v,
  2. x_2 \rightarrow u, x_2 \leftarrow v,
  3. x_3 \leftarrow u, x_3 \rightarrow v,
  4. x_4 \leftarrow u, x_4 \leftarrow v.

Wtedy niezależnie od kierunków krawędzi łączących usuwany wierzchołek z sąsiadami bylibyśmy w stanie dobrać jego kolor. Ale czy taki turniej istnieje?

Okazuje się, że istnieje. Wszystkich turniejów na 7 wierzchołkach jest tylko 2^{21}, łatwo więc przejrzeć wszystkie z nich i stwierdzić, że rzeczywiście niektóre z nich spełniają powyższy warunek. Po wyliczeniu można na sztywno zaszyć go w kodzie.

exodus3

Czyli uporaliśmy się z pierwszą trudnością. Ale jak poradzić sobie z ogólną wersją zadania, w której niektóre krawędzie mogły zostać wymazane? Wtedy sąsiedzi usuniętego wierzchołka niekoniecznie muszą być połączeni krawędzią, a co za tym idzie nie mamy gwarancji, że zostaną im przydzielone różne kolory (a to, jeśli krawędzie prowadzące do usuniętego wierzchołka mają różne kierunki, może sprawić, że przegramy). To może po prostu dorzućmy taką krawędź (ustalając dowolnie jej kierunek)? Na pewno zagwarantuje to nam, że sąsiadom usuniętego wierzchołka zostaną przydzielone różne kolory, nie jest jednak jasne czy procedura dalej jest poprawna.

Zapomnijmy na chwilę o kierunkach krawędzi. Rozważamy procedurę polegającą na powtarzaniu następującej operacji: wybierz i usuń wierzchołek stopnia co najwyżej dwa, jeśli ma dokładnie dwóch sąsiadów to połącz ich krawędzią. Chcielibyśmy pokazać, że dla dowolnego grafu utworzonego w sposób zdefiniowany w zadaniu koniec końców spowoduje to usunięcie wszystkich wierzchołków. Tym razem będzie to nieco bardziej skomplikowane.

Załóżmy, że wykonanie pewnej liczby kroków doprowadziło do sytuacji, w której wszystkie wierzchołki mają stopień przynajmniej 3 (czyli, że utknęliśmy). Zauważmy, że każda krawędź w aktualnym grafie odpowiada ścieżce w tym oryginalnym. Naszym celem będzie pokazanie, że istnienie takiego grafu oznacza, że można wskazać w oryginalnym grafie pewną strukturę, która nijak nie może powstać w wyniku wykonania ciągu operacji opisanych w treści zadania. Przyda nam się tutaj pojęcie minorów. Mówimy, że graf H jest minorem grafu G, gdy można przejść z G do H za pomocą ciągu następujących operacji:

  1. usunięcie wierzchołka,
  2. usunięcie krawędzi,
  3. ściągniecie krawędzi, to znaczy utożsamienie ze sobą jej końców.

Teraz możemy sformułować i udowodnić następujący lemat:

Lemat. Jeśli każdy wierzchołek grafu prostego (bez pętli i krawędzi wielokrotnych) ma stopień przynajmniej 3, to klika na 4 wierzchołkach jest jego minorem.

Dowód. Dowodzimy indukcyjne ze względu na liczbę krawędzi. Jeśli w grafie wszystkie wierzchołki mają stopień przynajmniej 4, możemy usunąć dowolną krawędź i skorzystać z założenia indukcyjnego. Wybierzmy więc wierzchołek u o stopniu 3. Jeśli wszyscy jego sąsiedzi mają stopień przynajmniej 4, możemy usunąć u i skorzystać z założenia indukcyjnego. Niech więc v będzie sąsiadem u o stopniu 3. Jeśli u i v nie mają wspólnego sąsiada o stopniu 3, to możemy ściągnąć krawędź (u,v) i skorzystać z założenia indukcyjnego. Niech więc x będzie ich wspólnym sąsiadem o stopniu 3. Zauważmy, że każdy z wierzchołków u,v,x ma jednego sąsiada spoza \{u,v,x\}, oznaczmy go, odpowiednio, u',v',x'. Jeśli u'=v'=x', to znaleźliśmy klikę na 4 wierzchołkach. Jeśli wszystkie u',v',x' są różne, to możemy ściągnać u,v,x do jednego wierzchołka i skorzystać z założenia indukcyjnego. Możemy więc bez straty ogólności założyć, że u'=v' \neq x'. Oznaczmy y=u'=v'. Jeśli po usunięciu u oraz v z grafu dalej istnieje w nim ścieżka pomiędzy y a x, to ściągając tę ścieżkę do jednej krawędzi znów otrzymamy klikę na 4 wierzchołkach. Możemy więc założyć, że x' nie jest sąsiadem y. Jeśli y ma stopień 3, czyli jego sąsiedzi to u,v,y', to odpowiednio ściągając krawędzie możemy doprowadzić do usunięcia wierzchołków u,v,x,y z grafu i dorzucenia krawędzi (x',y'), a następnie skorzystać z założenia indukcyjnego. Jeśli zaś stopień y to przynajmniej 4, możemy ściągnąć wierzchołki \{u,v,x,y\} w jeden i także skorzystać z założenia indukcyjnego.

Czyli wiemy, że jeśli proces usuwania wierzchołków zawiódł nasze oczekiwania, to klika na 4 wierzchołkach jest minorem danego grafu. Pojęcie minoru (jakkolwiek generalnie przydatne) być może nie jest bardzo wygodne w tym konkretnym przypadku, zauważmy więc, że tak naprawdę oznacza to, że istnieją w grafie wierzchołki a,b,c,d o takiej własności, że można wskazać rozłączne wierzchołkowo (poza końcami) ścieżki łączące każde dwa z nich (jest to tak zwany minor topologiczny; w ogólności nie jest prawdą, że istnienie minora implikuje istnienie minora topologicznego). Intuicja potrzebna w dowodzie tej implikacji znajduje się na poniższym rysunku.

exodus2

Dorzućmy do naszego grafu wszystkie usunięte krawędzie. Na pewno nie popsuje to naszych ścieżek. Teraz odwróćmy proces opisany w treści zadania i usuwajmy kolejne wierzchołki z dokładnie dwoma sąsiadami połączonymi ze sobą krawędzią. Łatwo zauważyć, że jeśli usuwany wierzchołek nie jest jednym z \{a,b,c,d\}, znów nie popsuje to naszych ścieżek. Ale przecież ten usuwany wierzchołek nie może być jednym z nich, mają one bowiem stopień przynajmniej 3. Czyli tak naprawdę nigdy nie będziemy w stanie zniszczyć całego grafu! Co oznacza, że klika na 4 wierzchołkach nie może być minorem grafu utworzonego w taki sposób, więc naszej procedurze zawsze uda się usunąć wszystkie wierzchołki.

Cały algorytm jest więc dość prosty. Usuwamy wierzchołek stopnia co najwyżej dwa, łączymy jego sąsiadów krawędzią o dowolnie wybranym kierunku (chyba, że była już taka krawędź), rekurencyjnie kolorujemy pozostałą część grafu, a następnie dobieramy kolor usuniętego wierzchołka korzystając z magicznego turnieju na 7 wierzchołkach. Przy ostrożnej implementacji całe rozwiązanie działa w czasie liniowym.

Reklamy

5 myśli nt. „Exodus superbohaterów

  1. „Jeśli w grafie istnieje krawędź (u,v) taka, że stopień u lub v jest przynajmniej 4, to po jej ściągnięciu i usunięciu krawędzi wielokrotnych otrzymamy mniejszy graf spełniający warunek z lematu.” – a co w przypadku, w którym u i v mają wspólnego sąsiada o stopniu 3? Wtedy po ściągnięciu (u, v) będzie on miał stopień 2.

      • Teraz wygląda dobrze :). Smu coś takiego klepał na zawodach, ale dostawał WA, zapewne jakieś bugi :<.
        Wspomnę jeszcze, że ten turniej da się wyprodukować łatwym wzorem, mianowicie k wygrywa z k+1, k+2 oraz k+4 mod 7.
        Swoją drogą urzekło mnie jak organizator na omówieniu stwierdził, że najpierw opowie treść zadania i przedstawił ją jednym zdaniem jako "W tym zadaniu mamy dany graf skierowany i trzeba go pokolorować." :D.
        Śmieszne są te trudne zadania grafowe z MWPZ (2 lata temu "Mapa", która chwilę później była na 3. rundzie FBHC, rok temu "Na skróty" i "Międzygalaktyczne podróże", a w tym roku to). Dość trudno je zrobić na conteście, ale mi się one podobają :).

  2. Chwilę próbowałem znaleźć wzór, ale wymiękłem 🙂 Zadanie jest według mnie fajnie, jedyny minus to treść — miałem spory problem ze zrozumieniem o co chodzi.

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