Izomorfizm grafów: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Pogrubienie "Prawdopodobnie nie" zamieniłem na poprawne pogrubienie "Prawdopodobnie nie jest" |
m robot poprawia: ar:تشاكل المخططات; zmiany kosmetyczne |
||
Linia 1:
{{Teoria grafów}}
'''Izomorfizm grafów''' – [[graf (matematyka)|Grafy]] G i F nazywamy [[izomorfizm|izomorficznymi]], jeżeli istnieje [[bijekcja]] zbioru wierzchołków grafu G na
== Przykład ==
[[Grafika:Graphs for isomorphism explanation.svg|left|thumb|250px|Grafy 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.
*f(a)=a
*f(b)=d
Linia 18:
*f(d)=c
== Rozstrzyganie izomorficzności ==
Problem rozstrzygania izomorficzności dwóch grafów należy do klasy [[Problem NP|NP]] ale '''prawdopodobnie 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]].
Linia 32:
== Bibliografia ==
* [[Robin Wilson]]
== Zobacz też ==
Linia 41:
== Linki zewnętrzne ==
*[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ść).
[[Kategoria:Teoria grafów]]
[[Kategoria:Morfizmy]]
[[ar:
[[ca:Isomorfisme de grafs]]
[[de:Isomorphie von Graphen]]
| |||