Droga długości 6

Po kolejnej długiej przerwie proponuję zadanie, które pojawiło się drugiego dnia na tegorocznym obozie w Petrozavodsku w zestawie autorstwa Xiaoxu Guo. W zadaniu dostajemy nieskierowanym graf i jesteśmy proszeni o policzenie dróg długości 6, które nie są cyklami prostymi.

Zacznijmy może od ustalenia terminologii. Przez drogę rozumiemy tutaj ciąg wierzchołków v_1,v_2,v_3,v_4,v_5,v_6 o takiej własności, że (v_1,v_2),(v_2,v_3),\ldots,(v_6,v_1) są krawędziami. Czyli tak naprawdę jest to zamknięta droga. Taka zamknięta droga jest cyklem prostym jeśli wszystkie wierzchołki v_1,v_2,v_3,v_4,v_5,v_6 są różne. Wspomnijmy jeszcze, że podany graf jest na co najwyżej n\leq 1000 wierzchołkach, co dość jasno sugeruje, że… no właśnie tak do końca nie wiadomo co, ale załóżmy, że chodzi o \mathcal{O}(n^3) z małą stałą.

Dobrze, więc jak zabrać się za zliczanie takich zamkniętych dróg? Skoro nie wszystkie spośród wierzchołków v_1,v_2,v_3,v_4,v_5,v_6 są różne, naturalne byłoby zgadnięcie które z nich są tymi powtarzającymi. Mówiąc bardziej precyzyjnie, dla każdego i możemy zgadnąć czy istnieje j< takie, że v_j=v_i (no i jeśli istnieje to zgadnąć takie j). Takie zgadnięcie można opisać słowem długości 6, w którym takie same litery oznaczają wystąpienie tego samego wierzchołka (a różne litery odpowiadają różnym wierzchołków). Takich słów nie ma zbyt wiele, szczególnie jeśli utożsamimy ze sobą te, które różnią się tylko nazwami liter. Jak mówi znane przysłowie, skoro możliwości jest skończenie wiele to przeanalizujmy je po kolei.

Hmmm.

Może i skończenie wiele, ale jednak więcej niż kilka. Zamiast zgadywać całe słowo zgadnijmy więc tylko liczbę różnych wierzchołków oraz zbiór łączących je krawędzi, po których przechodzimy podążając wzdłuż naszej zamkniętej drogi długości 6. Może się zdarzyć tak, że po tej samej krawędzi przejdziemy dwa (lub nawet więcej) razy, jednak nie jest to dla nas (jeszcze) interesujące. Teraz możliwości jest już tylko kilka, więc spróbujmy je po kolei przeanalizować.

Ponieważ w grafie nie ma pętli, musimy zgadnąć przynajmniej dwa wierzchołki. Pierwsza możliwość to dwa wierzchołki połączone krawędzią, czyli graf P_2. Jeśli mamy trzy różne wierzchołki to leżą one na ścieżce P_3 lub na cyklu C_3.

drogi1

Jeśli mamy cztery wierzchołki to możliwości jest trochę więcej. Wierzchołki mogą leżeć na ścieżce P_4 lub na cyklu C_4. Mogą też tworzyć gwiazdę K_{1,3} lub diament K_4-e. Co prawda istnieją jeszcze dwa inne spójne grafy na czterech wierzchołkach (C_3 z dołożonym wierzchołkiem przyległym do wszystkich pozostałych lub tylko do jednego z nich, jednak prosta analiza stopni wierzchołków pozwala na stwierdzenie, że nie odpowiadają one żadnemu zamkniętej drodze złożonej z sześciu krawędzi).

drogi2

Dla pięciu wierzchołków przeanalizowanie wszystkich możliwości jest nieco bardziej kłopotliwe. Patrząc na parzystości stopni wierzchołków i pamiętając o zamkniętej drodze złożonej z sześciu krawędzi możemy jednak otrzymać tylko dwa przypadki. Jeśli stopień każdego wierzchołka jest parzysty to stopień dokładnie jednego z nich jest równy 4, a stopnie wszystkich pozostałych to 2. Jednak wtedy nasz graf to na pewno motylek M. Jeśli zaś stopień jakiegoś wierzchołka jest nieparzysty to są dokładnie dwa takie wierzchołki, które w dodatku są swoimi sąsiadami. Jednak wtedy stopnie wierzchołków tworzą ciąg 1,3,2,2,2,2 i cały graf to flaga F.

drogi3

Uff. Ale właściwie co z tego? Załóżmy, że potrafimy wyznaczyć dla każdego z powyższych grafów liczbę jego wystąpień w tym wejściowym. (Przez wystąpienia rozumiemy tutaj jako podgraf, a nie jako podgraf indukowany!) Wtedy możemy wyznaczyć odpowiedź mnożąc liczbę wystąpień przez liczbę sposobów, na jakie można przejść graf zamkniętą drogą złożoną z sześciu krawędzi (odwiedzając przy tym każdą krawędź przynajmniej raz) i dodając tak otrzymane częściowe wyniki. Na przykład, patrząc na flagę widzimy, że krawędź łącząca wierzchołki nieparzystych stopni musi zostać odwiedzona dokładnie dwa razy, takich sposobów jest więc 6 (tutaj musimy odrobinę uważać i wziąć pod uwagę symetrie grafu: dwa przeciwległe wierzchołki stopnia 2 widzą resztę grafu w taki sam sposób, więc albo zaczynamy trasę w jednym z nich i mamy dwie możliwości jak kontynuować, albo zaczynamy trasę w tym trzecim wierzchołku stopnia 2 i mamy jedną możliwość, albo zaczynamy trasę w wierzchołku stopnia 1 i też mamy tylko jedną możliwość).

OK, czyli mamy jakiś pomysł na rozwiązanie zadanie. Odrobinę smutna wydaje się konieczność mechanicznego policzenia sposobów przejścia dla każdego z dziewięciu rozważanych grafów, jednak akurat ta część jest bardzo łatwa do zaprogramowania w kilku linijkach kodu (który generuje wszystkie istotnie różne słowa długości 6 i znajduje odpowiadający im graf). Trochę gorzej z automatyzacją zliczania wystąpień podgrafów: może ich być bardzo dużo, nie obędzie się więc bez chwili zastanowienia.

Niech d(u) oznacza stopień wierzchołka u. Liczba wystąpień P_2 to po prostu \sum_u d(u), a liczba wystąpień P_3 to \sum_u d(u) \cdot (d(u)-1).

Do dalszej części rozwiązania przyda nam się kilka oznaczeń. Niech t(u,v) będzie równe 1 gdy krawędź (u,v) należy do wejściowego grafu oraz 0 w przeciwnym przypadku, a s(u,v) oznacza liczbę ścieżek długości 2 łączących wierzchołki u \neq v. Wszystkie s(u,v) możemy wyznaczyć w czasie \mathcal{O}(n^3) (a może nawet szybciej korzystając z szybkiego mnożenia macierzy, ale miejmy na razie nadzieję, że nie okaże się to potrzebne).

Teraz liczba wystąpień C_3 to po prostu \sum_{u,v} t(u,v)\cdot s(u,v). Liczba wystąpień P_4 to z kolei \sum_{u,v} t(u,v)\cdot (d(u)-1)\cdot (d(v)-1) pomniejszone o liczbę wystąpień C_3.
Liczba wystąpień K_{1,3} jest równa \sum_u d(u) \cdot (d(u)-1) \cdot (d(u)-2).

…spokojnie, jesteśmy już w połowie drogi. Liczba wystąpień C_4 wyraża się przez \sum_{u,v} s(u,v) \cdot (s(u,v)-1), co odpowiada zgadnięciu jego przeciwległych wierzchołków. Aby zliczyć K_4-e wystarczy sumować tylko po u,v dla których t(u,v)=1. Podobnie, zliczenie wystąpień F sprowadza się do przesumowania s(u,v) \cdot (s(u,v)-1) przemnożonego przez d(v)-2-t(u,v) (aby uwzględnić, że dokładany wierzchołek nie może być taki sam jak jeden z wierzchołków już znajdujących się na utworzonym cyklu długości 4).

Pozostaje zliczyć wystąpienia M. Naturalne wydaje się zgadnięcie środkowego wierzchołka u. Potem musimy wybrać dwa rozłączne wierzchołkowo cykle długości 3 przechodzące przez u. To nie jest zbyt efektywne, lepiej więc wybrać dwa różne cykle długości 3 przechodzące przez u (na s(u,v)\cdot (s(u,v)-1) sposób), a następnie odjąć te wybory, dla których dwa cykle mają wspólny wierzchołek lub wspólne dwa wierzchołki. Tych pierwszych jest \sum_{v\neq u} s(u,v)\cdot (s(u,v)-1)\cdot 4, gdzie v jest tym powtarzającym się wierzchołkiem, a tych drugich po prostu s(u,v), gdyż (skoro cykle są różne) jeden musi być lustrzanym odbiciem drugiego.

Czyli potrafimy wyznaczyć liczbę wystąpień każdego z interesujących nas grafów. Zauważmy, że w każdym przypadku wymaga to tylko czasu \mathcal{O}(n^2) o ile dysponujemy wcześniej wyznaczonymi wartościami s(u,v), a więc czas całego algorytmu to \mathcal{O}(n^3). Wyznaczenie s(u,v) to po prostu podniesienie macierzy sąsiedztwa do kwadratu, teoretycznie można by więc próbować zastosować tutaj algorytm Strassena (lub lepszy). Na szczęście nie jest to jednak potrzebne do zaakceptowania zadania.

Advertisements

3 myśli nt. „Droga długości 6

  1. Moim skromnym zdaniem na tym Petro było trochę ciekawszych zadanek niż ta przypadkoza :P. Moje ulubione to mniej więcej C2, B4, A5, C5, H5, F7, C9, I9.

  2. Zgubiłeś mnie w akapicie na temat M. Czym jest v w pierwszym ze wzorów w tym akapicie: s(u,v)*(1-s(u,v)) i jak w zasadzie ten wzór ma się do opisu słownego „lepiej więc wybrać dwa różne cykle długości 3 przechodzące przez u”. Ja bym się spodziewał, że zobaczę tu raczej coś w stylu (sum over v of t(u,v)*s(u,v)) choose 2.

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