If an isomorphism exists between two graphs, then the graphs are called isomorphic. 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.
The graph isomorphism is an equivalence relation on graphs and as such it partitions the set of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs.
|Graph G||Graph H|| An isomorphism|
between G and H
|ƒ(a) = 1|
ƒ(b) = 6
ƒ(c) = 8
ƒ(d) = 3
ƒ(g) = 5
ƒ(h) = 2
ƒ(i) = 4
ƒ(j) = 7
The notion of "graph isomorphism" allows us to distinguish graph properties inherent to the structures of graphs themselves from properties associated with graph representations: graph drawings, data structures for graphs, graph labelings, etc. For example, if a graph has exactly one cycle, then all graphs in its isomorphism class also have exactly one cycle. On the other hand, in the common case when the vertices of a graph are (represented by) the integers 1, 2,... N, then the expression
The Whitney graph isomorphism theorem, shown by H. Whitney, states that two connected graphs are isomorphic if and only if their line graphs are isomorphic, with a single exception: K3, the complete graph on three vertices, and the complete bipartite graph K1,3, which are not isomorphic but both have K3 as their line graph. The Whitney graph theorem can be extended to hypergraphs.
The computational problem of determining whether two finite graphs are isomorphic is referred to as the graph isomorphism problem.
Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.
There is a particularly simple algorithm for determining if two rooted trees T and T' are isomorphic. First, assume that T and T' have the same number of vertices and the same height (otherwise they are not isomorphic). The vertices can be grouped into levels, sets of vertices that are the same distance from the root; since distance from the root is preserved by isomorphism, vertices in T must correspond to vertices in T' at the same level. We process the tree beginning with the bottom level and moving upwards, systematically assigning a label to each vertex such that two vertices have the same label if and only if the subtrees rooted at those two vertices are isomorphic.
Suppose v is an unlabelled vertex. Since the algorithm processes the tree bottom-up, all its children already have labels; assign v a temporary long label by sorting and concatenating the labels of its children. Next, sort all vertices at the current level by their long labels; then, assign fresh short labels to each vertex by numbering them from zero and giving identically-labelled vertices the same number. If at any level the final sorted set of short labels is different in T and T', then they are not isomorphic; otherwise the two roots will be assigned the same label and they are isomorphic.
Sorting the labels with a simple comparison sort, this algorithm requires Θ(n log n) time, where n is the number of vertices; it can be made to operate in O(n) time by careful use of bucket sort and radix sort.
This algorithm can be used to find isomorphism of general trees by noting that an isomorphism must map the center of T to the center of T'; the center of a tree has at most two vertices, so there are at most two ways of selecting the root nodes.
Some problems are complete for GI, meaning that there is a polynomial-time Turing reduction from any problem in GI to that problem; these problems are called GI-complete, and a polynomial-time solution to any one of these would yield a polynomial-time solution to the graph ismorphism problem (and so all problems in GI).
The graph isomorphism problem is contained in both NP and co-AM. GI is contained in and low for Parity P, as well as contained in the potentially much smaller class SPP That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial-time nondeterministic Turing machine has an even or odd number of accepting paths. GI is also contained in and low for ZPPNP. This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.
Many classes of digraphs are also GI-complete.
In cheminformatics and in mathematical chemistry, graph isomorphism and other graph matching techniques are used to identify a chemical compound within a chemical database. Also, in organic mathematical chemistry graph isomorphism testing is useful for generation of molecular graphs and for computer synthesis.
Since the molecular graphs have bounded degree (as the valence of any atom is at most 8), their isomorphism is testable in polynomial time. Also, the majority of chemical structures are planar graphs. So, for many practical wide-distributed tasks (chemical database support etc.) special notations (for example, SMILES) or fast isomorphism testing for planar molecular graphs may be sufficient.
Regular graphs are very difficult for isomorphism testing and many of them are very important for chemistry (for example, Cyclohexane, Benzene, Cuneane, Dodecahedrane etc.), but their part among chemical compounds is small, and decreases with increasing of number of vertices.
In electronic design automation graph isomorphism is the basis of the Layout Versus Schematic (LVS) circuit design step, which is a verification whether the electric circuits represented by a circuit schematic and an integrated circuit layout are the same.