Dzisiaj będziemy rozwiązywać zadanie Drzewa Czerwono-Czarne z Potyczek Algorytmicznych 2021. Zadanie wprawdzie z dywizji C ale było ciekawe i przyniosło mi bardzo dużo radości. W zadaniu mieliśmy dane drzewo, którego wierzchołki zostały pomalowane na czarno i czerwono. Możemy wykonać ruch polegający na wzięciu krawędzi łączącej dwa wierzchołki różnego koloru i przemalowaniu jednego z tych wierzchołków na “przeciwny” kolor. W zadaniu pytamy się czy istnieje ciąg ruchów który doprowadzi do przemalowania drzewa na podany wzór.
Zacznijmy od prostych przypadków. Jeśli drzewo jest już pomalowane na podany wzór, to odpowiedzią jest TAK. Jeśli nie jest, a drzewo na początku jest pomalowane na jeden kolor… to odpowiedzią jest NIE. Wiem, wiem. Ameryki nie odkryłem. Ale te spostrzeżenia są ważne i jeszcze do nich wrócimy.
Spróbujmy rozwiązać prostszy przypadek. Co jeśli podane drzewo jest listą? Taki przypadek jest prosty do rozwiązania jeśli się go rozrysuje. Możemy podzielić listę na jednokolorowe segmenty. Możemy zauważyć, że po każdym ruchu, liczba segmentów się nie zwiększy. Może się zmniejszyć. Ponadto popatrzmy na pierwszy i ostatni segment zarówno drzewa, jak i wzoru. Jeśli analogiczne sobie segmenty na drzewie i na wzorze są przeciwnych kolorów, to te z drzewa muszą zniknąć. Usuńmy je zatem. Jeśli po usunięciu ilość segmentów na drzewie jest mniejsza niż ilość segmentów we wzorze, to przemalować drzewa się nie da. Jeśli nie to się da.
Przejdźmy teraz do rozwiązania zadania właściwego. Popatrzmy na wzór do którego mamy dojść. Jeśli wzór definiuje dwudzielność drzewa, to nie da się do niego dojść. Jeśli nie, to da się. Już tłumaczę. Sprawdzamy czy istnieje we wzorze krawędź która łączy wierzchołki tego samego koloru. Jeśli istnieje to drzewo da się przemalować. Jeśli nie istnieje to nie da się. Po wielu nieudanych próbach ugryzienia tego problemu od strony programowania dynamicznego, byłem niezwykle zachwycony prostotą i elegancją tego rozwiązania.
Po tym co napisałem powinniśmy być w stanie zaimplementować rozwiązanie, które działa w czasie liniowym. Jednak dla frajdy, udowodnijmy jego poprawność. Zacznijmy od pokazania, że jeśli wzór nie definiuje dwudzielności, to da się go uzyskać.
Wiemy, że istnieje wierzchołek, który ma co najmniej trzech sąsiadów (gdyby nie istniał, to drzewo tworzyłoby listę, a listę rozważaliśmy osobno). Oznaczmy go jako R. Popatrzmy na jego sąsiadów i na poddrzewa zaczepione w tych sąsiadach. Chcielibyśmy w pierwszym kroku doprowadzić do sytuacji w której istnieją dwaj sąsiedzi o odmiennych kolorach. Jeśli już istnieją, to świetnie. Jeśli wszyscy mają ten sam kolor, to szukamy wierzchołka, który ma inny kolor (wiemy, że istnieje, bo inaczej całe drzewo miałoby jeden kolor, a taką sytuację rozważyliśmy osobno). Jeśli jest to wierzchołek R, to po prostu przemalowujemy któregoś z sąsiadów. Jeśli nie, to wierzchołek taki musi być w którymś poddrzewie. Lokalizujemy go i idziemy z nim do korzenia, przemalowując całą ścieżkę.
Mamy zatem wierzchołek R, jego trzech (lub więcej) sąsiadów i istnieje wśród nich taka para, która ma odmienne kolory. Popatrzmy zatem na trzecie drzewo, nie należące do tej pary. Spróbujemy je całe przemalować, prócz być może korzenia. Wybierzmy dowolny liść w tym drzewie. Powiedzmy, że ma zostać on być pomalowany na czerwono. Weźmy z naszej pary ten wierzchołek który ma czerwony kolor i stwórzmy ścieżkę od niego do tego liścia. Usuńmy na chwilę ten liść z drzewa i powtarzajmy całość dopóki mamy jeszcze wierzchołki w tym drzewie. Mamy pomalowane drzewo. Nie przejmujmy się korzeniem tego drzewa. Go będziemy jeszcze przemalowywać w czasie trwania naszego dowodu.
Co możemy zrobić teraz to możemy tak przemalować wierzchołek R i jego sąsiadów, aby teraz inna para sąsiadów miała różne kolory. Dzięki temu teraz inne drzewo będzie mogło zostać pomalowane. Powtarzamy dopóki wszystkie drzewa nie są pomalowane zgodnie z wzorem.
Na końcu zostaje nam wierzchołek R wraz z jego sąsiadami. Zazwyczaj łatwo można go przemalować (polecam popróbować na kartce papieru). Wyjątkiem stanowi sytuacja w której wierzchołek R ma zostać przemalowany na kolor inny niż wszyscy jego sąsiedzi. Dla ustalenia uwagi powiedzmy, że R ma być czerwony, a jego sąsiedzi czarni. W takiej sytuacji jeśli chcemy doprowadzić do happy endu, musimy popatrzeć ponownie na resztę grafu i być może coś w niej przemalować. Mamy szczęście jeśli któryś z sąsiadów ma syna, który jest czarny. Wtedy znów jest łatwo. Jeśli jednak tak nie jest to znajdźmy krawędź we wzorze, która miała łączyć wierzchołki tych samych kolorów. Wiemy że nie jest to krawędź łącząca R z jego sąsiadami, ani sąsiadów R z ich dziećmi. Zatem krawędź ta musi być zakopana gdzieś głęboko w jednym z poddrzew sąsiadów. Popatrzmy na ścieżkę od tego sąsiada do tej krawędzi. Powinna ona wyglądać mniej więcej tak:
B R B R B R B R RGdzie z lewej strony to sąsiad, który by chciał zostać pomalowany na czarno, a z prawej strony to znaleziona krawędź. Możemy przesunąć wszystkie kolory o jeden w prawo:
B B R B R B R B RTeraz możemy pomalować wierzchołek R wraz z jego sąsiadami w taki sposób, aby R oraz sąsiad, w którego drzewie znaleźliśmy tę krawędź, byli pomalowani na czerwono, a reszta sąsiadów na czarno. Teraz aby pomalować również tego sąsiada na czarno, wystarczy ścieżkę znowu przesunąć. Tym razem na lewo:
B R B R B R B R R Uff… Co kończy dowód.
Zatem udowodniliśmy, że jeśli we wzorze istnieje krawędź łącząca wierzchołki różnych kolorów, to można wzór uzyskać. Potrzebny nam jest jeszcze dowód że jeśli takiej krawędzi nie ma, to wzoru uzyskać się nie da. Nie uciekajcie! Dowód będzie tym razem krótki. Ponieważ po wykonaniu ruchu na krawędzi (u, v) wierzchołek u oraz wierzchołek v mają ten sam kolor oraz ponieważ musimy wykonać przynajmniej jeden ruch bo wzór jest różny od pierwotnego kolorowania grafu (ha! mówiłem, że jeszcze do tego założenia wrócimy!) to jedyne wzory do jakich możemy dojść, muszą mieć przynajmniej jedną krawędź łączącą wierzchołki pokolorowane na jednakowy kolor.
