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ą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:
- 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ść).
| ONZ: Izrael najpierw ewakuował Palestyńczyków, a potem ich ostrzelał |
|
Przynajmniej 30 Palestyńczyków zginęło w Strefie Gazy w ostrzale domu, do którego zostali wcześniej ewakuowani przez izraelskich żołnierzy - wynika z raportu ONZ.
|
| "Nie myślałem, że minister się tak prostytuuje" |
|
Posłanka PiS Grażyna Gęsicka, wzywając rząd do odpowiedzialności za niewykorzystanie funduszy unijnych manipuluje opinią publiczną - ocenił w TVN24 poseł PO Janusz Palikot.
|
| Wypadek na drodze Wrocław-Legnica |
|
Jedna osoba została ranna w wyniku wypadku, do którego doszło w piątek wieczorem niedaleko miejscowości Mazurowice (Dolnośląskie). Droga krajowa nr 94 Wrocław - Legnica została całkowicie zablokowana.
|
| Omar Faris: Niech Izrael opuści nasze ziemie |
|
- Niech Izrael opuści nasze ziemie, a gwarantujemy, że ani jedna rakieta nie spadnie na ich ziemie - mówił przewodniczący Palestyńskiej Koalicji na rzecz Prawa do Powrotu Omar Faris, gość CZATerii w INTERIA.PL.
|
| Juszczenko: Konflikt gazowy był zaplanowany |
|
Ukraina pozwoli rosyjskim obserwatorom na wjazd na jej terytorium w celu nadzorowania tranzytu rosyjskiego gazu do Europy - poinformował prezydent Ukrainy Wiktor Juszczenko po spotkaniu z czeskim premierem Mirkiem Topolankiem w Kijowie.
|