Izomorfizm grafów
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ź[1].
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
[edytuj | edytuj kod]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)[2]
- 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ż
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 3. ISBN 0-387-95014-1.
- ↑ Alfred V. Aho, John Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974, s. 84-86.
Bibliografia
[edytuj | edytuj kod]- 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
[edytuj | edytuj kod]- Izomorfizm grafów
- Eric W. Weisstein , Graph Isomorphism, [w:] MathWorld, 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ść).