Izomorfizm grafów: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
m robot poprawia: ar:تشاكل المخططات; zmiany kosmetyczne |
|||
Linia 42: | Linia 42: | ||
*[http://mathworld.wolfram.com/GraphIsomorphism.html Izomorfizm grafów - MathWorld] |
*[http://mathworld.wolfram.com/GraphIsomorphism.html Izomorfizm grafów - MathWorld] |
||
*[http://cs.anu.edu.au/~bdm/nauty/ Nauty] - szybki program autorstwa [[Brendan McKay|Brendana D. McKay]] do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność). |
*[http://cs.anu.edu.au/~bdm/nauty/ Nauty] - szybki program autorstwa [[Brendan McKay|Brendana D. McKay]] do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność). |
||
*[http://www.scribd.com/doc/512105/A-polynomial-time-algorithm-for-graph-isomorphism Sprawdzanie izomorficzności grafów w czasie wielomianowym] |
|||
[[Kategoria:Teoria grafów]] |
[[Kategoria:Teoria grafów]] |
Wersja z 20:34, 12 mar 2008
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.
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
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ący 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.
Bibliografia
- Robin Wilson – Wprowadzenie do teorii grafów, PWN, 2004, ss. 21-22, ISBN 83-01-12641-8
Zobacz też
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ść).
- Sprawdzanie izomorficzności grafów w czasie wielomianowym