Graph Isomorphism

From GM-RKB
(Redirected from Graph isomorphism)
Jump to navigation Jump to search

A graph isomorphism is a bijective function on two graphs (with graph edges [math]\displaystyle{ E_1, E_2 }[/math]) such that if [math]\displaystyle{ \{e_i,e_j\}\in E_1 }[/math] then also [math]\displaystyle{ \{e_i,e_j\}\in E_2 }[/math].



References

2015

  • (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/graph_isomorphism Retrieved:2015-11-16.
    • In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H : [math]\displaystyle{ f \colon V(G) \to V(H) \,\! }[/math] such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is generally called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.

      If an isomorphism exists between two graphs, then the graphs are called isomorphic and we write [math]\displaystyle{ G\simeq H }[/math] . In the case when the bijection is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the bijection is called an automorphism of G.

      A graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs.

      The two graphs shown below are isomorphic, despite their different looking drawings.

Graph G Graph H An isomorphism
between G and H
File:Graph isomorphism a.svg File:Graph isomorphism b.svg f(a) = 1

f(b) = 6

f(c) = 8

f(d) = 3

f(g) = 5

f(h) = 2

f(i) = 4

f(j) = 7