Problem izomorfizmu grafów

Spójrzmy na dwa grafy na poniższym rysunku. Wyglądają zupełnie inaczej, prawda?

A jednak to tylko złudzenie. Tak naprawdę to jest ten sam graf, ale inaczej narysowany. Istotnie, poniżej ponumerowaliśmy wierzchołki obu grafów od 0 do 9 i łatwo można sprawdzić, że w obu przypadkach wierzchołek o danym numerze ma takie same numery sąsiadów.

Izomorfizm grafów $=(VG,EG) |G$ i $=(VH,EH) H$ to dowolna bijekcja $| f VG VH ,$ taka że dowolne dwa wierzchołki $|u,v ∈VG$ sąsiadują w $G$ wtedy i tylko wtedy, gdy $f (u)$ i $f(v)$ sąsiadują w $. H$ Gdy izomorfizm z $|G$ do $H$ istnieje, mówimy, że grafy $|G$ i $H$ są izomorficzne. Przykład izomorfizmu grafów widzimy na rysunku powyżej.

Informatyk od razu zapyta o algorytm rozstrzygający, czy dane dwa grafy są izomorficzne. Oznaczmy $|n = VG = VH$ (gdy ostatnia równość nie zachodzi, problem jest banalny). Algorytm wynikający wprost z definicji sprawdza wszystkie $|n!$ bijekcji i działa w czasie $(n!⋅n2). O$ Ale czy istnieje algorytm wielomianowy? To niewinne pytanie jest jednym z największych problemów otwartych współczesnej informatyki.

Oczytany Czytelnik zapewne zna wiele innych problemów grafowych, dla których algorytm wielomianowy nie jest znany: problem kliki, problem cyklu Hamiltona, problem kolorowania. Są to problemy NP-zupełne, a rozwiązanie jednego z nich w czasie wielomianowym od razu implikuje takie rozwiązanie dla pozostałych (oraz tysięcy innych nazwanych problemów z klasy NP). Co ciekawe, nie wiemy, czy problem izomorfizmu grafów jest NP-zupełny! Mamy nawet istotne powody, aby podejrzewać, że tak nie jest (przeczyłoby to kilku znanym hipotezom). Gdy autor tego artykułu był studentem, znany był jeszcze jeden problem o podobnym statusie: testowanie pierwszości liczb, w 2002 roku został on jednak rozwiązany w czasie wielomianowym. Czy ten sam los czeka izomorfizm grafów? Aktualny rekord świata, który ustanowił Laszlo Babai dwa lata temu, to algorytm działający w czasie $O logn c n ,$ dla pewnej stałej $|c.$

Zanim porwiemy się na trudny problem, warto zrozumieć jego szczególne, być może prostsze, przypadki. Jedną z najprostszych klas grafów są drzewa (grafy spójne bez cykli). Jak sprawdzić, czy dwa drzewa, $T1$ i $T2,$ są izomorficzne? Niech $|v$ będzie dowolnym wierzchołkiem $T1.$ Rozpatrzmy wszystkie $|n$ możliwości ustalenia $|w$ Możemy ukorzenić $|T 1$ w $|v,$ tzn. uznać, że $|v$ jest korzeniem, a dla dowolnego innego wierzchołka $u$ sąsiad $u$ na (jedynej) ścieżce do $v$ jest ojcem $u.$ Podobnie ukorzeniamy $T2$ w $w.$ Naszym celem będzie przypisanie każdemu ukorzenionemu drzewu identyfikatora (wyrażenia nawiasowego) tak, aby drzewa były izomorficzne wtedy i tylko wtedy, gdy mają te same identyfikatory. Wówczas wystarczy porównać identyfikatory $T1 |$ i $|T2.$ Drzewo składające się z pojedynczego wierzchołka dostaje identyfikator ().

Identyfikator drzewa powstaje przez a) posortowanie identyfikatorów poddrzew korzenia, b) sklejanie ich w uzyskanej w kolejności w jedno słowo, c) dodanie symbolu ( na początku i symbolu ) na końcu. Czytelnik Pracowity na pewno z łatwością wykaże przez indukcję, że istotnie tylko izomorficzne drzewa dają ten sam identyfikator dla pewnej wartości $w$ Tak uzyskany algorytm jest wielomianowy, a kosztem dodatkowego wysiłku można tę złożoność zmniejszyć nawet do liniowej.

Istnieją znacznie bardziej złożone klasy grafów niż drzewa, dla których problem izomorfizmu grafów ma wielomianowe rozwiązanie. Jedną z nich są grafy planarne, tzn. takie, które można narysować na płaszczyźnie bez przecięć krawędzi. Algorytm opiera się na twierdzeniu Whitneya, mówiącemu, że jeśli graf planarny jest 3-spójny (nie da się usunąć dwóch wierzchołków tak, aby uzyskać graf, który nie jest spójny), to można go narysować na sferze w jeden tylko sposób. Dokładniej, każdy rysunek można przekształcić w inny za pomocą ciągłego odwzorowania sfery w sferę. Takie odwzorowania nie zmieniają np. cyklicznej kolejności sąsiadów wierzchołka, a więc gdy mamy już na sferze narysowane dwa grafy i zgadniemy, jak izomorfizm odwzorowuje wierzchołki dowolnej wybranej krawędzi $|uv,$ to pozostałe wartości izomorfizmu są wyznaczone jednoznacznie (najpierw wyznaczymy obrazy sąsiadów $v,$ potem sąsiadów sąsiadów $v,$ itd.). Graf ma rysunek na sferze wtedy i tylko wtedy, gdy jest planarny, a przejście od 3-spójnych grafów planarnych do dowolnych planarnych nie jest trudne. Inny słynny wynik to grafy o stopniu ograniczonym przez stałą $d$ : w 1983 roku Babai i Luks podali algorytm działający w czasie $nO d ,$ korzystając z zaawansowanych narzędzi teorii grup.

Na szczęście w praktyce jest dużo lepiej niż w teorii. Rozważmy następujący algorytm. Na początku wszystkie wierzchołki $G$ i $H$ otrzymują ten sam kolor. Niech $c(v)$ oznacza kolor $|v.$ Następnie dla każdego wierzchołka $v$ tworzymy multizbiór (tj. zbiór z powtórzeniami) kolorów jego sąsiadów $|S(v)$ i zapamiętujemy parę $(c(v),S(v)).$ Pokolorujemy teraz graf na nowo w ten sposób, by dwa wierzchołki miały ten sam kolor tylko wtedy, gdy utworzyły wcześniej tę samą parę $|(c(v),s(v)).$ Postępujemy w ten sposób tak długo, dopóki zwiększa się liczba kolorów. Jeśli multizbiory kolorów wierzchołków $G$ i $H$ są inne, mamy pewność, że $|G$ i $H$ nie są izomorficzne (dlaczego?). Zauważmy, że już po pierwszym kroku algorytm ten rozróżni grafy o innych posortowanych ciągach stopni wierzchołków. Łatwo wykazać, że poprawnie rozróżnia on drzewa. Z drugiej strony, nie rozróżnia grafów regularnych. Okazuje się jednak, że można ten pomysł uogólnić, kolorując wszystkie ciągi $k$ wierzchołków. Jest to algorytm Weisfeilera-Lehmana wymiaru $k$ i świetnie sprawdza się w praktyce. Już wymiar $k = 3$ wystarcza, aby rozróżnić grafy planarne. Niestety, okazuje się, że aby rozróżnić dowolne grafy w pesymistycznym przypadku potrzeba wymiaru co najmniej liniowego od $n,$ a więc nie tędy droga do rozwiązania naszego problemu otwartego. Na szczęście pesymistyczne przypadki zdarzają się niezwykle rzadko w rzeczywistych danych.