Graph isomorphism
From Free net encyclopedia
A graph isomorphism is a bijection, i.e., a one-to-one mapping, between the vertices of two graphs <math>G</math> and <math>H</math>:
- <math> f: V(G) \rightarrow V(H)</math>
with the property that any two vertices <math>u</math> and <math>v</math> from <math>G</math> are adjacent if and only if <math>f(u)</math> and <math>f(v)</math> are adjacent in <math>H</math>.
If an isomorphism can be constructed between two graphs, then we say those graphs are isomorphic.
Determining whether two graphs are isomorphic is the graph isomorphism problem.
[edit]
Example
Consider these two graphs:
Although these graphs look very different, they are isomorphic; one isomorphism between them is
- <math> f(a) = 1</math>
- <math> f(b) = 6</math>
- <math> f(c) = 8</math>
- <math> f(d) = 3</math>
- <math> f(g) = 5</math>
- <math> f(h) = 2</math>
- <math> f(i) = 4</math>
- <math> f(j) = 7</math>
[edit]
See also
Template:Planetmathde:Isomorphie von Graphen pl:Izomorfizm grafów vi:Phép đẳng cấu đồ thị