Zliczamy skojarzenia (II). O planarności i algorytmie FKT

W pierwszej części tego artykułu pokazaliśmy, że dla szczególnej klasy grafów (kraty i ich podgrafy), istnieje działający w czasie wielomianowym algorytm, który wyznacza liczbę doskonałych skojarzeń dla dowolnego grafu z tej klasy. Ten wynik można uogólnić na szerszą klasę grafów - a konkretnie na grafy planarne, czyli takie, które można narysować na płaszczyźnie tak, by żadne z ich krawędzi się nie przecinały.

Mając dowolny nieskierowany graf planarny $|G,$ zawierający $N |$ wierzchołków $|v1,...,vN ,$ rozważymy jego (symetryczną) macierz sąsiedztwa $|A= (ai, j)$ rozmiaru $|N× N,$ w której $ai, j = 1,$ jeśli wierzchołki $|v i$ oraz $|v j$ są połączone krawędzią. Przykładowo, poniższy graf o ośmiu wierzchołkach, mający cztery doskonałe skojarzenia (dwa zawierające krawędź $|v3v4$ i dwa jej niezawierające), ma następującą macierz sąsiedztwa.

Rys. 1 Skierowane pokrycia cyklowe (wyróżnione strzałkami) w grafie $G$ odpowiadające permutacjom $π 1$ i $|π. 2$

Podobnie jak w pierwszej części, naszym głównym narzędziem będzie obliczenie permanentu pewnej macierzy związanej z grafem, przy użyciu algorytmu liczenia wyznacznika jeszcze innej macierzy. Zarówno permanent, jak i wyznacznik, będą sumami iloczynów odpowiadających każdej permutacji wierzchołków grafu. Na początek zastanówmy się zatem, jakiemu obiektowi w grafie $G$ odpowiada permutacja wierzchołków $, π$ dla której iloczyn $| a L i,π i$ jest równy 1. Dla każdego czynnika $a = 1 i,π i$ wyróżnijmy w grafie skierowaną krawędź z wierzchołka $vi$ do wierzchołka $vπ i .$ Ponieważ $|π$ jest permutacją, więc każdy z wierzchołków będzie miał wyróżnioną dokładnie jedną krawędź wychodzącą i dokładnie jedną wchodzącą. Zatem wyróżnione krawędzie będą tworzyły skierowane pokrycie cyklowe (Rys. 1). Innymi słowy, permanent macierzy $A$ będzie oznaczał ich liczbę:

liczba skierowanych pokry ćcyklowych = perm(A).

I w tym momencie to właśnie te pokrycia będą nas najbardziej interesowały (a dlaczego, to wyjaśni się pod koniec artykułu). W szczególności, pokażemy teraz ciekawą konstrukcję, która pozwoli nam policzyć te skierowane pokrycia cyklowe, które zawierają jedynie cykle długości parzystej.

Zamiast symetrycznej macierzy $A$ do reprezentowania grafu $G$ możemy równie dobrze użyć antysymetrycznej macierzy $′A,$ w której $|ai, j = ±1,$ jeśli wierzchołki $|vi$ oraz $|v j$ są połączone krawędzią, oraz $|ai, j = −a j,i$ (dla ustalenia uwagi przyjmijmy, że $ai, j = 1$ dla $i < j$ ). Innymi słowy, każdej krawędzi $viv j$ przypisujemy etykietę 1 lub $−1,$ którą będziemy "odczytywać", przechodząc tą krawędzią z $v i$ do $|v j$ (a przechodząc ją w odwrotnym kierunku, odczytamy etykietę przeciwną). Obchodząc dowolny cykl w grafie $|G,$ będziemy mnożyć etykiety jego krawędzi, uzyskując wkład, jaki daje ten cykl do iloczynu $L | ai,π i .$ Oczywiście, jeśli przejdziemy taki cykl w odwrotnym kierunku, to jego wkład przemnoży się przez $s |(−1),$ gdzie $|s$ jest długością cyklu, w szczególności zmieni znak dla cyklu nieparzystej długości. Dla skierowanego pokrycia cyklowego odpowiadającego permutacji $π,$ przez wkład pokrycia rozumiemy iloczyn wkładów wszystkich cykli, czyli po prostu $|L a . i,π i$

Pokażemy teraz, że można połączyć skierowane pokrycia cyklowe, które zawierają jakikolwiek cykl nieparzysty, w takie pary, że wkłady pokryć należących do każdej pary będą miały różne znaki. W tym celu ustawmy wszystkie skierowane cykle długości nieparzystej z grafu $G$ w ciąg $|c1,cR1 ,c2,cR2,...$ (gdzie $cR$ oznacza ten sam cykl co $c,$ tylko przeciwnie skierowany). Jeśli w pokryciu cyklowym $c$ jest najmniejszym cyklem z ciągu, to sparujemy je z pokryciem cyklowym, w którym ten cykl zamienimy na $cR.$ Zauważmy, że parowanie jest poprawne oraz iloczyny $|L ai,π i$ dla pokryć z każdej pary mają przeciwne znaki. Z tego wynika, że jeśli przesumujemy teraz te iloczyny dla wszystkich skierowanych pokryć cyklowych, które zawierają jakikolwiek cykl nieparzysty, to suma ta wyniesie 0. Tak więc w przypadku macierzy antysymetrycznej $A′,$ zarówno wartości $|perm(A′),$ jak i $det(A′)$ nie zmienią się, jeśli w sumowaniu opuścimy wszystkie permutacje zawierające jakikolwiek cykl nieparzysty.

Z cyklami parzystymi jest kłopot - choć wkład z odwróconego cyklu jest taki sam, jak dla oryginalnego, to istotnie zależy on od konkretnych etykiet. Dla skierowanego cyklu $|c$ oznaczmy przez $p(c)$ parzystość liczby krawędzi, dla których odczytujemy etykietę $|−1$ (zatem wkład z tego cyklu jest równy 1, jeśli $p(c)$ jest parzyste i $−1,$ jeśli jest nieparzyste). Okazuje się, że w przypadku grafów planarnych jesteśmy w stanie w sposób wystarczający kontrolować liczbę $p(c).$

Rys. 2 Wierzchołki grafu dualnego grafu $|G$ oraz krawędzie jego drzewa rozpinającego $T$ (wyróżnione kolorem) oraz krawędzie tnące grafu $G$ (pogrubione).

Graf planarny $G$ możemy narysować na płaszczyźnie tak, że żadne krawędzie nie będą się przecinały. Każda część płaszczyzny otoczona krawędziami to ściana grafu $G. |$ Z grafem tym możemy związać graf dualny, w którym mamy wierzchołek dla każdej ściany grafu $G, |$ oraz krawędź, jeśli dwie ściany mają wspólną krawędź w $G. |$ W grafie dualnym wyróżnimy też dowolne ukorzenione drzewo rozpinające $T |$ (Rys. 2), a w grafie $|G$ zbiór krawędzi, które przecinają $T |$ (nazwiemy je krawędziami tnącymi). Będziemy teraz zmieniać etykietowanie niektórych z krawędzi tnących. Zauważmy, że dowolna ściana grafu $G, |$ odpowiadająca pewnemu liściowi $v$ drzewa $T ,$ ma dokładnie jedną krawędź tnącą. Zmieniając (albo nie) etykietowanie tej krawędzi, możemy wymusić dowolną parzystość wartości $p(c)$ dla cyklu $c$ otaczającego tę ścianę. Następnie usuwamy liść $v$ z drzewa $T$ i postępujemy rekurencyjnie, aż rozważymy wszystkie ściany. Powyższy algorytm (znany pod nazwą FKT od nazwisk jego twórców - Fisher, Kasteleyn i Temperley), pozwala nam wymusić dowolną parzystość $p(c)$ krawędzi dla każdego cyklu $|c$ odpowiadającego ścianie grafu (Rys. 3).

A jak to wpływa na parzystości pozostałych cykli? Łatwo wykazać, że jeśli mamy cykle $c1$ i $|c2$ odpowiadające sąsiadującym ścianom grafu, to parzystość cyklu, który otacza obie te ściany, wynosi $|(p(c1)+ p(c2)+ k) mod 2,$ gdzie $|k$ jest liczbą krawędzi wspólnych dla obu tych ścian. Indukcyjnie można zatem wykazać, że cykl $c$ otaczający ściany cyklów $c1,c2,...,cs$ ma parzystość $(p(c1)+ p(c2) +...+ p(cs) +k) mod 2,$ gdzie $k$ to liczba krawędzi leżących "wewnątrz" cyklu $c.$ Wzór ten ma ciekawe konsekwencje, jeśli ustalimy parzystość każdej ze ścian na $p(ci) = 1.$ Wtedy parzystość cyklu $c$ to $(s+ k) mod 2.$ Ale, używając wzoru Eulera, można wykazać, że liczba wierzchołków leżących "wewnątrz" cyklu $c$ to $|k+ 1− s.$ W szczególności $p(c) = 1$ wtedy, gdy liczba tych wierzchołków jest parzysta.

Cała ta karkołomna konstrukcja znajdzie zaraz swoje uzasadnienie. Zacznijmy od macierzy $A′,$ a następnie wykonajmy algorytm FKT tak, by parzystość cyklu każdej ściany wyniosła 1. Zdefiniujmy już ostatnią macierz antysymetryczną $′′ A.$ Dla $|i < j$ i wierzchołków $vi, v j$ połączonych krawędzią kładziemy $ai, j = −1,$ jeśli etykietowanie krawędzi zostało zmienione przez algorytm FKT, oraz $ai, j = 1,$ jeśli nie zostało (oczywiście $|a = −a j,i i, j$ ). Rozważmy teraz dowolny cykl $c$ należący do pewnego pokrycia cyklowego cyklami parzystymi. Wszystkie wierzchołki leżące wewnątrz tego cyklu muszą być również pokryte pełnymi cyklami, zatem ich liczba musi być parzysta, więc $p(c) = 1.$ Innymi słowy, iloczyn etykiet krawędzi z tego cyklu wynosi $|−1,$ niezależnie od wyboru tego cyklu. Tak więc znowu (tak jak w pierwszej części artykułu) udało nam się sprawić, że iloczyn $L ai,π i$ wszystkich cykli jest równy znakowi permutacji, więc możemy użyć algorytmu liczenia wyznacznika. Zatem

liczba skierowanych pokryć cyklowych cyklami parzystymi = det(A′′ ).

Pora na ostatnią sztuczkę. Rozważmy parę doskonałych skojarzeń w grafie i zaznaczmy naraz ich krawędzie. Ponieważ każdy wierzchołek będzie miał zaznaczone dokładnie dwie krawędzie, więc taki rysunek odpowiadać będzie pewnemu pokryciu cyklowemu cyklami parzystymi. Co więcej, każdy cykl długości większej niż 2 możemy skierować - powiedzmy, że kierujemy go w prawo dokładnie wtedy, gdy najmniejsza leksykograficznie krawędź pochodzi z pierwszego skojarzenia (Rys. 4). Nietrudno się przekonać, że w ten sposób dostaniemy bijekcję między zbiorem uporządkowanych par doskonałych skojarzeń a zbiorem skierowanych pokryć cyklowych cyklami parzystymi (aby uzyskać z pokrycia parę skojarzeń, należy brać co drugą krawędź z każdego cyklu). Porównując liczności tych zbiorów, dostajemy ostateczny wzór na liczbę doskonałych skojarzeń w grafie planarnym:

√ -------- liczba doskona łych skojarzeń = det(A′′ ) .