Artykuł

Zadania z teorii liczb przedstawione w poprzednim odcinku chyba nie wzbudziły Waszego entuzjazmu, spróbujmy więc czegoś z teorii grafów. Tematyka o tyle lepsza, że aż prosi się o rysunki, a rysunki – wiadomo – są fajne. Trochę mniej fajnie, że twierdzenia z tej działki często wymagają dość żmudnego rozważenia kilku(nastu) przypadków, ale spokojnie, nie zawsze jest aż tak tragicznie. Jako przykład proponuję zadanie A z NEERC Western Subregional Contest 2012. Dostajemy w nim dość specyficzny graf nieskierowany, w którym podgraf indukowany przez sąsiadów dowolnego wierzchołka jest spójny, a ponadto nie ma tam (ciągle mówimy o podgrafie indukowanym przez sąsiadów dowolnego wierzchołka) antytrójkątów. Chcemy skonstruować jak najdłuższy cykl przechodzący przez wierzchołek numer 1. Warunki nałożone na graf ewidentnie sugerują, że… hmm?

W sumie ciężko powiedzieć, co sugerują te warunki. Są one jednak na tyle dziwaczne, że można na przykład podejrzewać taki graf o bycie hamiltonowskim (no, lub bycie niespójnym, ale przecież każdy szanujący się graf jest spójny), czyli o to, że zawsze można znaleźć w nim cykl przechodzący przez każdy wierzchołek dokładnie raz. Okazuje się, że faktycznie tak jest! Jednak zanim zabierzemy się za skonstruowanie (konstruktywnego!) dowodu tego podejrzenia, zastanówmy się przez chwilę nad czymś zupełnie innym. No, może nie zupełnie, ale trochę.

Powiedzmy, że mamy dany graf (znów nieskierowany) na n \geq 3 wierzchołkach, w którym stopień każdego wierzchołka to przynajmniej \frac{n}{2}. Okazuje się, że taki warunek wystarcza, żeby można było efektywnie skonstruować cykl, który przechodzi przez każdy wierzchołek dokładnie raz. Pewnie można to udowodnić na kilka różnych sposobów, ale taki najbardziej standardowy polega na stopniowym konstruowaniu coraz dłuższych cykli prostych (czyli takich, na których wierzchołki i krawędzie nie powtarzają się). Na dobry początek możemy wybrać dowolny cykl prosty. Jeśli takiego nie ma, to nasz graf jest drzewem, czyli jest w nim przynajmniej jeden wierzchołek stopnia 1 < \frac{n}{2}, czyli sprzeczność. Następnie spróbujmy pokazać, że dysponując cyklem prostym v_1 - v_2 - \ldots - v_\ell - v_1 o długości \ell<n umiemy (szybko) skonstruować cykl prosty o długości \ell+1 (lub więcej).

Najpierw spróbujmy jednak (też szybko) skonstruować ścieżkę prostą o takiej długości. W najprostszy możliwy sposób: próbujemy znaleźć x, który nie leży na cyklu, ale jest sąsiadem jakiegoś v_i, wtedy ścieżka to po prosty x - v_i - v_{i+1} \ldots - v_{i-1}. Jeśli takiego x nie ma, to cały cykl stanowi jedną spójną składową, czyli jest jeszcze jakaś inna spójna składowa, czyli jedna z nich ma rozmiar \leq \frac{n}{2}. Ale wtedy wierzchołki w niej nie mogą być stopnia przynajmniej \frac{n}{2}!

Teraz mając ścieżkę prostą v_1 - v_{2} \ldots - v_\ell - v_{\ell+1} długości \ell+1 spróbujmy skonstruować cykl prosty o przynajmniej takiej samej długości. Jeśli v_1 i v_{\ell+1} są sąsiadami, nasza ścieżka jest tak naprawdę cyklem, załóżmy więc przeciwnie. Jeśli v_1 lub v_{\ell+1} mają sąsiada poza ścieżką, można wydłużyć ścieżkę o jeden wierzchołek i powtórzyć rozumowanie, załóżmy więc, że tak nie jest. Wtedy wszyscy sąsiedzi v_1 i v_{\ell+1} należą do \{v_2,v_3,\ldots,v_\ell\}. Ale skoro każdy z nich ma przynajmniej \frac{n}{2} sąsiadów, istnieje i\in\{2,3,\ldots,\ell-1\} dla którego v_i jest sąsiadem v_{\ell+1}, a v_{i+1} jest sąsiadem v_{1}. Wtedy zaś szukanym cyklem jest:

v_1 - v_{i+1} - v_{i+2} - \ldots v_{\ell} - v_{\ell+1} - v_{i} - v_{i-1} - \ldots - v_2 - v_1

Przy odrobinie ostrożności całą procedurę można zaimplementować w czasie \mathcal{O}(n) na każde rozszerzenie o jeden.

Z braku lepszych pomysłów możemy spróbować zastosować opisaną wyżej metodę stopniowego rozszerzania cyklu do naszego zadania. Niestety po drodze napotkamy pewne trudności, ale to nawet lepiej. Przynajmniej będzie ciekawie.

Mamy dany spójny graf nieskierowany na n wierzchołkach, w którym podgraf indukowany przez sąsiadów dowolnego wierzchołka jest spójny, a ponadto nie ma tam antytrójkątów. Chcemy pokazać, że mając w takim grafie cykl prosty długości \ell<n, jesteśmy w stanie (szybko) skonstruowac cykl prosty długości \ell+1. Jest to dość ambitnie zamierzenie, więc może zacznijmy od skromnej obserwacji: jeśli n\geq 3, graf na pewno zawiera jakiś cykl prosty (prosty oznacza tutaj tyle, że zarówno wierzchołki jak i krawędzie nie mogą się powtarzać; w szczególności, pojedyncza krawędź nie jest cyklem prostym). Załóżmy, że jest przeciwnie, czyli graf jest drzewem. Ale wtedy istnieje w nim wierzchołek v stopnia przynajmniej 2. Wybierzmy dwóch jego sąsiadów i nazwijmy ich x i y. Z założenia o spójności podgrafu indukowanego przez sąsiadów v otrzymujemy, że istnieje ścieżka łącząca x z y, która omija v. Dorzucając do tej ścieżki v otrzymamy żądany cykl prosty.

Załóżmy, że mamy już cykl prosty długości \ell<n. Naszym celem będzie wydłużenie go, przy czym w przeciwieństwie do prostszej wersji opisanej powyżej, niekoniecznie tylko dodając wierzchołek. Również w przeciwieństwie do prostszej wersji, rzeczone wydłużenie będzie wymagało odrobiny zastanowienia. Zacznijmy od prostej obserwacji: skoro \ell<n, na pewno przynajmniej jeden z wierzchołków na cyklu v_1 - v_2 - \ldots - v_\ell - v_1 ma sąsiada poza cyklem. Dla ustalenia uwagi powiedzmy, że v_1 ma sąsiada x, który nie leży na cyklu. No, może i nie leży on na cyklu, ale skoro podobnie jak v_\ell jest sąsiadem v_1, to na pewno istnieje ścieżka łącząca x i v_\ell, tak jak na poniższej ilustracji, która w dodatku przechodzi tylko przez sąsiadów v_1.

artykul1

Wybierzmy sobie najkrótszą z takich ścieżek. Jest to dość częsty trik w tego typu dowodach: zamiast patrzeć na dowolne rozwiązanie, o którym ciężko cokolwiek powiedzieć, patrzymy na (w jakimś sensie) najmniejsze, którego struktura nie może być już tak zupełnie dowolna. Okazuje się, że ta najkrótsza ścieżka nie może zawierać trzech wierzchołków wewnętrznych (wewnętrznych, czyli tych ściśle między x a v_\ell). Załóżmy bowiem, że są takie trzy wierzchołki. Wszystkie z nich są sąsiadami v_1, czyli nie może być tak, że tworzą one antytrójkąt. Ale wobec tego jedna z wykropkowanych (poniżej) krawędzi musi faktycznie być krawędzią, no a to oznacza, że możemy jej użyć do skrócenia ścieżki.

artykul2

No i pięknie. Mamy więc dwa przypadki: ścieżka zawiera dokładnie jeden wierzchołek wewnętrzny lub dokładnie dwa wierzchołki wewnętrzne. No, pewnie może być też i tak, że ścieżka składa się tylko z x i v_\ell, ale w takim wypadku możemy od razu wydłużyć cykl. Podobnie możemy postąpić mając krawędź x - v_\ell lub x - v_2, czyli bez straty ogólności możemy założyć, że takich krawędzi nie ma. A to oznacza, z założenia o braku antytrójkątów wśród sąsiadów v_1, że mamy krawędź v_2 - v_\ell. Ten trik warto dokładnie prześledzić, bowiem przyda się nam jeszcze nie raz, nie dwa, lecz aż trzy razy. Nie mniej i nie więcej.

Zacznijmy od przypadku, w którym ścieżka zawiera dokładnie jeden wierzchołek wewnętrzny. Pewnie okaże się on prostszy niż ten drugi, choć.. kto wie. Na pewno możemy jednak założyc, że ten unikalny wierzchołek wewnętrzny tak naprawdę jest jednym z v_i, w przeciwnym wypadku moglibyśmy bowiem od razu wydłużyć cykl.

artykul3

Popatrzmy na v_{i+1} i v_{i} (dla spokoju sumienia zauważmy, że żaden z nich nie jest wierzchołkiem v_1). Są to, podobnie jak x, sąsiedzi v_i, więc znów możemy skorzystać z założenia o braku antytrójkątów. W zamian dostajemy przynajmniej jedną z krawędzi x - v_{i+1}, x - v_{i-1} i v_{i-1} - v_{i+1}. Teraz jest już łatwo: mając krawędź x - v_{i+1} lub x - v_{i-1} oraz x - v_i możemy łatwo rozszerzyć cykl. Czyli pozostaje tylko poradzić sobie w sytuacji, gdy mamy tylko krawędź v_{i-1} - v_{i+1}. Okazuje się to jednak być dość łatwe, jak widać poniżej.

artykul4

OK, to nie było takie trudne. No to zajmijmy się bardziej skomplikowanym przypadkiem, w którym ścieżka zawiera dokładnie dwa wierzchołki wewnętrzne. Podobnie jak wcześniej, przynajmniej jeden z tych dwóch wierzchołków musi tak naprawdę być jednym z v_i. Niestety nie do końca wiadomo, czy dotyczy to tego pierwszego, tego drugiego, czy też może obydwu. Rozważmy sobie najpierw ten ostatni przypadek.

artykul5

Powyższa ilustracja jest odrobinę tendencyjna: wcale nie mamy gwarancji, że v_i i v_j występują właśnie w takiej kolejności na cyklu. Ale nic to. Powtarzając rozumowanie o braku antytrójkątów dla x, v_{i+1} i v_{i-1}, które wszystkie są sąsiadami v_i, otrzymamy, że albo możemy łatwo rozszerzyć cykl o x, albo mamy krawędź v_{i-1} - v_{i+1}. A to oznacza, że możemy usunąć v_i z naszego cyklu i zredukować sytuację do przypadku, gdy ścieżka najpierw przechodzi przez wierzchołek spoza cyklu, a następnie przez v_i. No, prawie: trzeba będzie tylko zadbać o to, żeby nasze rozszerzanie przypadkiem nie skończyło się na dorzuceniu do cyklu tylko jednego wierzchołka. Byłoby to dość, hm, bezużyteczne. Trzeba również ponownie zadbać o sprawdzenie, czy v_2 - v_\ell jest krawędzią, mogło się bowiem zdarzyć, że v_2 lub v_\ell był wierzchołkiem, który usuwamy z cyklu. Patrząc na sytuację w trochę bardziej optymistyczny sposób, w żadnym miejscu nie skorzystaliśmy z założenia, że drugi wewnętrzny wierzchołek to jakiś v_j, czyli tak naprawdę załatwiliśmy dwa z trzech możliwych przypadków. Został nam już tylko jeden!

artykul6

Załóżmy teraz, że ścieżka najpierw przechodzi przez wierzchołek y, który nie leży na cyklu, a następnie przez v_i. Po raz kolejny powtarzając rozumowanie o braku antytrójkątów dla y, v_{i+1} i v_{i-1}, które wszystkie są sąsiadami v_i dostaniemy przynajmniej jedną z krawędzi v_{i+1} - y, v_{i-1} - y, v_{i+1} - v_{i-1}. Mając jedną z tych dwóch pierwszych krawędzi i przypominając sobie, że v_i (jako wierzchołek na ścieżce) musi być sąsiadem v_1, możemy dość łatwo rozszerzyć cykl, jak widać poniżej.

artykul7

Przyjmijmy więc, że dysponujemy tylko v_{i+1} - v_{i-1}. Wtedy jest jednak równie łatwo! (Uważny Czytelnik pewnie od razu zauważy, że mamy wtedy w zasadzie taką samą sytuację jak ta dla ścieżki składającej się z tylko jednego wierzchołka wewnętrznego; mam jednak nadzieję, że wybaczy mi ten recykling obrazków)

artykul8

I.. i koniec. Rozważyliśmy wszystkie możliwe sytuacje, w każdej z nich udało nam się rozszerzyć cykl. Czynność należy powtórzyć, i prędzej lub później napawać się widokiem cyklu hamiltona. Trzeba by się tylko chwilę zastanowić nad kosztem całego przedsięwzięcia. Rozszerzenie cyklu wymaga tylko stałej liczby operacji, o ile mamy w ręce najkrótszą ścieżkę łączącą x i v_\ell w podgrafie indukowanym przez sąsiadów v_1. Taką ścieżkę pewnie łatwo znaleźć używając choćby przeszukiwania wszerz, i dostać sumaryczną złożoność \mathcal{O}(nm). Ale może da się lepiej?

Czasami pewnie się da. Graf z treści zadania jest dość rzadki (n\leq 1000, ale m\leq 10000), pewnie warto by więc spróbować uzyskać złożoność, która jest lepsza niż \mathcal{O}(nm) dla m \ll n^2. Równie naturalne wydaje się próba zbicia złożoności dla grafów gęstych, czyli dla m \approx n^2. Wrócimy do tego tematu w jednym z kolejnych odcinków.

Advertisements

2 myśli nt. „Artykuł

  1. Dowód w 3 akapicie jest chyba trochę blefem.
    Weźmy graniastosłup o podstawie trójkąta (oczywiście spełnia on założenie o stopniach wierzchołków), a jako aktualny cykl wierzchołki jednej z jego podstaw. Nie da się zwiększyć naszego cyklu o jeden wierzchołek.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s