Skojarzenia w grafach kubicznych

Skojarzenia to bardzo popularny temat. Pojawiają się w różnych miejscach zarówno w informatyce, jak i w matematyce dyskretnej.

Definicja. W grafie nieskierowanym $\text{[math]}$ zbiór krawędzi $\text{[math]}$ nazywamy skojarzeniem, jeśli żadne dwie krawędzie z $\text{[math]}$ nie mają wspólnego końca.

W tym artykule zajmiemy się skojarzeniami w grafach kubicznych. Graf $\text{[math]}$ nazwiemy kubicznym, jeśli każdy wierzchołek $\text{[math]}$ ma stopień dokładnie $\text{[math]}$

Mając dany graf $\text{[math]}$ przez $\text{[math]}$ i $\text{[math]}$ będziemy oznaczać odpowiednio zbiór wierzchołków i krawędzi $\text{[math]}$ Ponadto oznaczmy $\text{[math]}$ Dla wierzchołka $\text{[math]}$ przez $\text{[math]}$ będziemy oznaczać zbiór sąsiadów $\text{[math]}$ ; tę notację rozszerzymy na podzbiory wierzchołków: $\text{[math]}$ Skojarzenie $\text{[math]}$ w grafie $\text{[math]}$ nazwiemy doskonałym, jeśli ma ono rozmiar dokładnie $\text{[math]}$ czyli każdy wierzchołek $\text{[math]}$ jest końcem jakiejś krawędzi skojarzenia. Na rysunku pokazane są dwa grafy kubiczne: pierwszy z nich ma doskonałe skojarzenie, a drugi nie ma. Czy łatwo jest odróżnić grafy kubiczne z doskonałym skojarzeniem od tych, które takiego nie mają?

By odpowiedzieć na to pytanie, przypomnijmy sobie wpierw twierdzenie Halla. Mamy graf dwudzielny $\text{[math]}$ – dwudzielny, to znaczy, że zbiór wierzchołków $\text{[math]}$ można podzielić na takie dwie części $\text{[math]}$ i $\text{[math]}$ że wszystkie krawędzie $\text{[math]}$ łączą $\text{[math]}$ z $\text{[math]}$ Interesuje nas to, czy w tym grafie istnieje skojarzenie rozmiaru $\text{[math]}$ czyli takie, że wszystkie wierzchołki ze zbioru $\text{[math]}$ są skojarzone (każdy jest końcem pewnej krawędzi skojarzenia). Jeśli istnieje taki zbiór $\text{[math]}$ że $\text{[math]}$ to ewidentnie takie skojarzenie nie istnieje: wierzchołki z $\text{[math]}$ mają za mało sąsiadów, by wszystkie były skojarzone. Twierdzenie Halla orzeka, że powyższy warunek jest decydujący: jeśli dla każdego $\text{[math]}$ mamy $\text{[math]}$ to w $\text{[math]}$ istnieje skojarzenie rozmiaru $\text{[math]}$

Twierdzenie Halla mówi o istnieniu dużych – kojarzących wszystkie wierzchołki jednej części grafu – skojarzeń w grafach dwudzielnych. A jak to jest dla dowolnych grafów? O tym mówi twierdzenie Tutte. Obierzmy dowolny graf $\text{[math]}$ i zastanówmy się, co może przeszkadzać w tym, by $\text{[math]}$ miał doskonałe skojarzenie. Weźmy dowolny zbiór wierzchołków $\text{[math]}$ i wyrzućmy go z grafu, otrzymując graf $\text{[math]}$ Spójrzmy na pewną spójną składową $\text{[math]}$ : jeśli ma ona nieparzyście wiele wierzchołków, to w doskonałym skojarzeniu musiałaby istnieć krawędź łącząca wierzchołek z tej spójnej składowej z wierzchołkiem z $\text{[math]}$ Wobec tego nieparzystych spójnych składowych $\text{[math]}$ nie może być więcej niż $\text{[math]}$ Twierdzenie Tutte mówi, że powyższy warunek jest wystarczający: jeśli dla każdego zbioru wierzchołków $\text{[math]}$ po wyrzuceniu $\text{[math]}$ w $\text{[math]}$ pozostaje nie więcej niż $\text{[math]}$ nieparzystych spójnych składowych, to w $\text{[math]}$ istnieje doskonałe skojarzenie.

Wróćmy teraz do grafów kubicznych. Okazuje się, że tym, co może przeszkadzać, by w grafie kubicznym istniało doskonałe skojarzenie, są mosty (patrz np. dolny graf na rysunku). Krawędź $\text{[math]}$ jest mostem, jeśli nie leży w żadnym cyklu, tj. po wyrzuceniu krawędzi $\text{[math]}$ końce $\text{[math]}$ leżą w różnych spójnych składowych. Spróbujemy wykorzystać twierdzenie Tutte, by wykazać następujący:

Lemat. Jeśli graf kubiczny $\text{[math]}$ nie ma mostów, to ma doskonałe skojarzenie.

Dowód. Chcemy użyć twierdzenia Tutte, weźmy więc dowolny podzbiór wierzchołków $\text{[math]}$ i zastanówmy się, ile może być spójnych składowych o nieparzystej liczbie wierzchołków w $\text{[math]}$ Weźmy taką spójną składową $\text{[math]}$ Zauważmy, iż łączny stopień wierzchołków $\text{[math]}$ to $\text{[math]}$ : jest to liczba nieparzysta, czyli, na mocy lematu o uściskach dłoni, nieparzyście wiele krawędzi łączy $\text{[math]}$ z resztą grafu. Jeśliby łączyła $\text{[math]}$ z resztą grafu tylko jedna krawędź, to byłaby mostem: wobec tego istnieją co najmniej trzy krawędzie łączące $\text{[math]}$ z resztą grafu. Skoro $\text{[math]}$ było spójną składową $\text{[math]}$ to te trzy krawędzie łączą $\text{[math]}$ z $\text{[math]}$ Z drugiej strony, łączny stopień wierzchołków z $\text{[math]}$ wynosi $\text{[math]}$ w $\text{[math]}$ może być zatem co najwyżej $\text{[math]}$ spójnych składowych o nieparzystej liczbie wierzchołków, co kończy dowód lematu.

Wiemy już, że jeśli graf kubiczny nie ma mostów, to ma doskonałe skojarzenie. Ale ile ma tych skojarzeń? Otóż do końca nie wiadomo. W latach 70. ubiegłego wieku László Lovász i Michael Plummer postawili hipotezę, że jest ich wykładniczo wiele: istnieje taka stała $\text{[math]}$ że każdy graf kubiczny bez mostów ma co najmniej $\text{[math]}$ doskonałych skojarzeń. Hipotezę tę dość szybko udowodnił Marc Voorhoeve dla grafów kubicznych dwudzielnych. Bardzo niedawno Maria Chudnovsky oraz Paul Seymour udowodnili hipotezę dla grafów planarnych: pokazali oni, że graf kubiczny planarny bez mostów ma co najmniej $\text{[math]}$ doskonałych skojarzeń. Z drugiej strony, Esperet, Král, Škoda i Škrekovski pokazali, że w dowolnym grafie kubicznym bez mostów mamy co najmniej $\text{[math]}$ doskonałych skojarzeń i jest nadzieja na to, że niedługo powstanie dowód, że istnieje ich co najmniej $\text{[math]}$ dla pewnej stałej $\text{[math]}$ Jak widać, jeszcze długa droga pozostała do rozstrzygnięcia hipotezy Lovásza–Plummera.