Izomorfizm grafów
Z Wikipedii
Izomorfizm grafów – Grafy G i F nazywamy izomorficznymi, jeżeli istnieje funkcja wzajemnie jednoznaczna odwzorowująca zbiór wierzchołków grafu G na zbiór wierzchołków grafu F, która zachowuje strukturę grafu (relację sąsiedztwa). Intuicyjnie grafy izomorficzne, to grafy o nierozróżnialnej, ze względu na analogiczne na nich operacje, strukturze ("identyczne", "równe").
Można też mówić o izomorfizmie grafów skierowanych. Należy jedynie pamiętać, że wtedy relacja sąsiedztwa nie jest symetryczna.
Problem rozstrzygania izomorficzności dwóch grafów jest problemem NP zupełnym.
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. Funkcja przekształcającą jeden graf w drugi to:
- f(a)=a
- f(b)=b
- f(c)=c
- 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ąc jeden graf w drugi jest już inna:
- f(b)=b
- f(e)=a
- f(c)=e
- f(a)=d
- f(d)=c
(tu ważne jest, że lewy graf przekształacamy w prawy)
[edytuj] Bibliografia
- Robin Wilson – Wprowadzenie do teorii grafów, PWN, 2004, ss. 21-22, ISBN 83-01-12641-8
[edytuj] Zobacz też
- homomorfizm grafów
- homeomorfizm grafów
