Added to Favorites

Popular Searches

Definitions

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
## Example

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

## Motivation

The formal notion of "isomorphism", e.g., of "graph isomorphism", captures the informal notion that some objects have "the same structure" if one ignores individual distinctions of "atomic" components of objects in question, see the example above. Whenever individuality of "atomic" components (vertices and edges, for graphs) is important for correct representation of whatever is modeled by graphs, the model is refined by imposing additional restrictions on the structure, and other mathematical objects are used: digraphs, labeled graphs, colored graphs, rooted trees and so on. The isomorphism relation may also be defined for all these generalizations of graphs: the isomorphism bijection must preserve the elements of structure which define the object type in question: arcs, labels, vertex/edge colors, the root of the rooted tree, etc.## Results

## The graph isomorphism problem

## Solved special cases

A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:### Rooted trees

## Complexity class GI

Since the graph isomorphism problem is neither known to be NP-complete nor to be tractable, researchers have sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem. If in fact the graph isomorphism problem is solvable in polynomial time, GI would equal P.## GI-Complete problems

### Isomorphism of other objects

There are a number of classes of mathematical objects for which the problem of isomorphism is a GI-complete problem. A number of them are graphs endowed with additional properties or restrictions: ### GI-complete classes of graphs

A class of graphs is called GI-complete if recognition of isomorphism for graphs from this subclass is a GI-complete problem. The following classes are GI-complete:### Other

There are other nontrivial GI-complete problems in addition to isomorphism problems.## Applications

The graph isomorphism problem has a number of practical applications. ## See also

## Notes

## References

- $f\; colon\; V(G)\; to\; V(H)\; ,!$

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

- $sum\_\{v\; in\; V(G)\}\; vcdottext\{deg\; \}v$

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: K_{3}, the complete graph on three vertices, and the complete bipartite graph K_{1,3}, which are not isomorphic but both have K_{3} 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.

A generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete.

- Trees.
- Planar graphs.
- Interval graphs.
- Permutation graphs.
- Partial k-trees.
- Bounded-parameter graphs
- Graphs of bounded genus (Note: planar graphs are graphs of genus 0)
- Graphs of bounded degree.
- Graphs with bounded eigenvalue multiplicity.

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 ZPP^{NP}. 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.

- digraphs
- labelled graphs, with the proviso that an isomorphism is not required to preserve the labels, but only the equivalence relation consisting of pairs of vertices with the same label
- polarized graphs (made of a complete graph K
_{m}and an empty graph K_{n}plus some edges connecting the two; their isomorphism must preserve the partition) - 2-colored graphs
- explicitly given finite structures
- multigraphs
- hypergraphs
- finite automata
- commutative class 3 nilpotent (i.e., xyz = 0 for every elements x, y, z) semigroups
- finite rank associative algebras over a fixed algebraically closed field with zero squared radical and commutative factor over the radical
- context-free grammars
- balanced incomplete block designs

- connected graphs
- graphs of diameter 2 and radius 1
- directed acyclic graphs
- regular graphs.
- bipartite graphs without non-trivial strongly regular subgraphs
- bipartite Eulerian graphs
- bipartite regular graphs
- line graphs
- chordal graphs
- regular self-complementary graphs
- graphs of general, simple, and simplicial polytopes in arbitrary dimensions

Many classes of digraphs are also GI-complete.

- The recognition of self-complementarity of a graph or digraph
- A clique problem for a class of so-called M-graphs. It is shown that finding of an isomorphism for n-vertex graphs is equivalent to finding an n-clique in an M-graph of size n
^{2}. This fact is interesting because the problem of finding an n-ε-clique in a M-graph of size n^{2}is NP-complete for arbitrarily small positive ε.

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.

- .
- .
- .
- I. S. Filotti , Jack N. Mayer (1980), A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236-243
- .
- .
- .
- .
- .
### Surveys

- Ronald Read and Derek Corneil. "The graph isomorphism disease". Journal of Graph Theory 1977, 1, 339-363
- Gati, G. "Further annotated bibliography on the isomorphism disease." – Journal of Graph Theory 1979, 3, 95-109

- Zemlyachenko, V. N.; Korneenko, N. M. and Tyshkevich, R. I. (1985). "Graph isomorphism problem".
*Journal of Mathematical Sciences*29 (4): pp. 1426–1481. (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118, pp. 83–158, 1982.)

- .

- .

- .

- .

- .

- .

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 17:47:52 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 17:47:52 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.