Izomorfizm grafów

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Izomorfizm grafów – graf G jest izomorficzny z grafem H, jeśli istnieje bijekcja ("przeetykietowanie") wierzchołków grafu H wierzchołkom grafu G, takie że jeśli jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź.

Izomorfizm grafów zachowuje właściwie wszystkie interesujące własności, na przykład: liczbę wierzchołków, liczbę krawędzi, stopnie wierzchołków, spójność, planarność. Dlatego grafy izomorficzne zwykle utożsamia się.

Rozstrzyganie izomorficzności

Problem rozstrzygania izomorficzności dwóch grafów należy do klasy NP, ale dotąd nie pokazano, aby był problemem NP-zupełnym. Z drugiej strony nie są znane wielomianowe algorytmy deterministyczne, probabilistyczne ani kwantowe rozwiązujące ten problem. Nie wiadomo też czy problem należy do klasy co-NP.

Efektywne wielomianowe rozwiązania tego problemu znaleziono dla szczególnych klas grafów, między innymi:

• drzew (złożoność liniowa)
• grafów planarnych
• grafów o ograniczonym stopniu
• grafów przedziałowych
• grafów permutacji
• grafów wypukłych

Uogólnieniem tego problemu jest problem izomorfizmu podgrafu, o którym wiadomo że jest problemem NP-zupełnym.

Zobacz też

• homeomorfizm grafów

Bibliografia

• Materiały naukowe, Wydział MiNI Politechnika Warszawska
• Robin Wilson – Wprowadzenie do teorii grafów, PWN, 2004, ss. 21-22, ISBN 83-01-12641-8

Linki zewnętrzne

• Izomorfizm grafów
• Eric W.E.W. Weisstein Eric W.E.W., Graph Isomorphism, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).
• Nauty - szybki program autorstwa Brendana D. McKay do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność).