Wikipedia

Izomorfizm grafów: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Poprawki merytoryczne i uzupełnienia
Linia 1:
'''Izomorfizm grafów''' – [[Grafgraf (matematyka)|Grafy]] G i F nazywamy [[izomorfizm|izomorficznymi]], jeżeli istnieje [[funkcja wzajemnie jednoznacznabijekcja]] [[homomorfizm grafów|odwzorowująca]] [[zbiór]]zbioru wierzchołków grafu G [[surjekcja|na]] zbiór [[wierzchołek|wierzchołków]] grafu F, która zachowuje strukturę grafu (relację sąsiedztwakrawędzie). Intuicyjnie grafyoznacza izomorficzne,to toże grafy oG nierozróżnialnej,i zeF względusą natym analogicznesamym nagrafem, nichjedynie operacje,poddanym strukturzejakiejś ("identyczne",[[permutacja|permutacji]] "równe")wierzchołków.
 
Można też mówić o izomorfizmie [[graf skierowany|grafów skierowanych]]. Należy jedynie pamiętać, że wtedy [[relacja]] sąsiedztwa nie jest [[relacja symetryczna|symetryczna]].
 
Problem rozstrzygania izomorficzności dwóch grafów jest problemem [[Problem NP zupełny|NP zupełnym]].
 
== Przykład ==
[[Grafika:Graphs for isomorphism explanation.svg|thumb|250px|grafyGrafy 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<sub>5</sub>, a wszystkie cykle nieskierowane o tej samej liczbie wierzchołków są względem siebie izomorficzne. Funkcja przekształcającą jeden graf w drugi to:
*f(a)=a
Linia 13 ⟶ 9:
*f(d)=d
*f(e)=e
Dla grafów dolnych należy zwrócić uwagę, że są to ścieżki o tej samej liczbie wierzchołków, ale funkcja przekształacającprzekształcając jeden graf w drugi jest już inna:
*f(b)=b
*f(e)=a
Linia 19 ⟶ 15:
*f(a)=d
*f(d)=c
(tu ważne jest, że lewy graf przekształacamyprzekształcamy w prawy)
 
==Rozstrzyganie izomorficzności==
 
Problem rozstrzygania izomorficzności dwóch grafów należy do klasy [[Problem NP|NP]] ale '''nie''' jest problemem [[Problem NP zupełny|NP zupełnym]]. Z drugiej strony nie są znane wielomianowe algorytmy deterministyczne, [[algorytm probabilistyczny|probabilistyczne]] ani [[komputer kwantowy|kwantowe]] rozwiązujący ten problem. Nie wiadomo też czy problem należy do klasy [[klasa Co-NP|co-NP]].
 
Efektywne wielomianowe rozwiązania tego problemu znaleziono dla szczególnych klas grafów, między innymi:
* [[graf planarny|grafów planarnych]]
* grafów o ograniczonym [[stopień grafu|stopniu]]
* [[graf przedziałowy|grafów przedziałowych]]
* [[graf permutacji|grafów permutacji]]
* [[graf wypukły|grafów wypukłych]]
 
Uogólnieniem tego problemu jest [[problem izomorfizmu podgrafów]], o którym wiadomo że jest problemem [[Problem NP zupełny|NP zupełnym]].
 
== Bibliografia ==
Linia 25 ⟶ 34:
 
== Zobacz też ==
*[[homomorfizm grafów]]
*[[homeomorfizm grafów]]
 
Źródło: „https://pl.wikipedia.org/wiki/Izomorfizm_grafów”