Graph Isomorphism
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].
- AKA: Edge Preserving Bijection.
- Context:
- It can be created by a Graph Isomorphism Creation Task.
- If the graphs are Directed Graphs ...
- If the graphs are Labeled Graphs ...
- See: Graph Isomorphic Relation, Isomorphism, Graph Isomorphism Task.
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.
- 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.
| 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 |
