Izomorfizm grafów
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
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.
Spis treści |
[edytuj] Przykład
Grafy znajdujące się na górze są izomorficzne względem siebie, bo są to cykle C5, 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ż
[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ść).