Definitions

Graph_isomorphism

Graph isomorphism

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
f colon V(G) to V(H) ,!
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 commonly 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. 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.

Example

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

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

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.

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
may be different for two isomorphic graphs.

Results

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 graph isomorphism problem

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.

Solved special cases

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

Rooted trees

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.

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.

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.

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:

Many classes of digraphs are also GI-complete.

Other

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

  • 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 n2. This fact is interesting because the problem of finding an n-ε-clique in a M-graph of size n2 is NP-complete for arbitrarily small positive ε.

Applications

The graph isomorphism problem has a number of practical applications.

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.

See also

Notes

References

  • .

    • .

      • .

        • 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

Search another word or see Graph_isomorphismon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature