Izomorfizm grafów
W tym artykule poruszony zostanie temat Izomorfizm grafów, koncepcji, która w ostatnich latach zyskała na znaczeniu ze względu na jej wpływ na różne aspekty życia codziennego. Od momentu pojawienia się Izomorfizm grafów przyciąga uwagę ekspertów i opinii publicznej, wywołując debaty, badania i różne interpretacje. Z biegiem czasu Izomorfizm grafów stał się tematem zainteresowania zarówno w środowisku akademickim, jak i w codziennych rozmowach, a jego wpływ rozprzestrzenił się na wiele obszarów, stając się podstawowym punktem odniesienia dla zrozumienia bieżących zjawisk. W tym przeglądzie zbadane zostaną różne perspektywy Izomorfizm grafów, aby zapewnić szeroką i wzbogacającą wizję jego znaczenia i wpływu na współczesne społeczeństwo.
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
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ż
Przypisy
- ↑ 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
- Materiały naukowe, Wydział MiNI Politechnika Warszawska
- Robin Wilson – Wprowadzenie do teorii grafów, PWN, 2004, s. 21–22, ISBN 83-01-12641-8.
Linki zewnętrzne
- Izomorfizm grafów
- Eric W. Weisstein, Graph Isomorphism, MathWorld, Wolfram Research (ang.).
- Nauty – szybki program autorstwa Brendana D. McKay do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność).
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
