Eulerian Cycle Test
That is isomorphism? Thursday, May 6, 2010
Welded Wire Stretchers
The property of a graph that shows that the graph can be obtained from other re label their vertices. Mathematically speaking
:
G = (V, E) and G '= (V', E ') are isomorphic $ G \\ cong G' $ if there exists a bijective f between their respective sets of vertices V and V ' preserving its surroundings:
$ $ \\ forall v, w \\ in V, v ~ w \\ leftrightarrow f (v) ~ f (w) $ $
The idea is simple, all the neighbors who belong to a vertex, must also belong to the vertex of another graph.
For example if the graph G (1, 5) has a vertex v whose neighbors are {a, b, c, d, e} and a graph M (1, 5) has a vertex x whose neighbors are also {a, b, c, d, e}, then the vertex v is the same as the vertex xy graphs G and M are the same except for its location in space. That is isomorphism, but is clearer with an example:
positions in the image of the vertices change as do some edges, but all the vertices remain the same neighbors, then both graphs are isomorphic.
Sources
http://mate.cucei.udg.mx/matdis/5gra/5gra6.htm Http://web.udl.es/usuaris/p4088280/teaching/terminologia.pdf
http://mathworld.wolfram.com/GraphIsomorphismComplete.html
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment