Izomorfizm grafów

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

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka 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 Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

Izomorfizm grafów – Grafy G i F nazywamy izomorficznymi, jeżeli istnieje bijekcja zbioru wierzchołków grafu G na zbiór wierzchołków grafu F, która zachowuje strukturę grafu (krawędzie). Intuicyjnie oznacza to, że grafy G i F są tym samym grafem, jedynie poddanym jakiejś permutacji wierzchołków.

[edytuj] Przykład

Grafy występujące obok siebie na tym rysunku są izomorficzne.

Grafy znajdujÄ…ce siÄ™ na górze sÄ… izomorficzne wzglÄ™dem siebie, bo sÄ… to cykle C₅, a wszystkie cykle nieskierowane o tej samej liczbie wierzchoÅ‚ków sÄ… wzglÄ™dem siebie izomorficzne. Izomorfizmem przeksztaÅ‚cajÄ…cym lewy graf na prawy jest funkcja dana przez:

• f(a)=a
• f(b)=d
• f(c)=b
• f(d)=e
• f(e)=c

Dla grafów dolnych należy zwrócić uwagę, że są to ścieżki o tej samej liczbie wierzchołków, ale funkcja przekształcająca izomorficznie lewy graf na prawy jest już inna:

• f(b)=b
• f(e)=a
• f(c)=e
• f(a)=d
• f(d)=c

[edytuj] Rozstrzyganie izomorficzności

Problem rozstrzygania izomorficzności dwóch grafów należy do klasy NP ale prawdopodobnie nie jest problemem NP zupełnym. Z drugiej strony nie są znane wielomianowe algorytmy deterministyczne, probabilistyczne ani kwantowe rozwiązujący 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:

• 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.

[edytuj] Bibliografia

• Robin Wilson – Wprowadzenie do teorii grafów, PWN, 2004, ss. 21-22, ISBN 83-01-12641-8

[edytuj] Zobacz też

• homeomorfizm grafów
• izomorfizm
• izomorfizm kryształów.

[edytuj] Linki zewnętrzne

• Izomorfizm grafów - MathWorld
• Nauty - szybki program autorstwa Brendana D. McKay do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność).