Graph isomorphism: Difference between revisions
→Algorithmic approach: reference to Schöning |
not disjoint - one is a subset of the other - but distinct |
||
Line 56: | Line 56: | ||
Its practical applications include primarily [[cheminformatics]], [[mathematical chemistry]] (identification of chemical compounds), and [[electronic design automation]] (verification of equivalence of various representations of the design of an [[electronic circuit]]). |
Its practical applications include primarily [[cheminformatics]], [[mathematical chemistry]] (identification of chemical compounds), and [[electronic design automation]] (verification of equivalence of various representations of the design of an [[electronic circuit]]). |
||
Curiously, it is also one of only a few problems in [[computational complexity theory]] belonging to [[NP (complexity)|NP]], but not known to belong to either of its well-known (and, if [[P versus NP problem|P ≠ NP]], |
Curiously, it is also one of only a few problems in [[computational complexity theory]] belonging to [[NP (complexity)|NP]], but not known to belong to either of its well-known (and, if [[P versus NP problem|P ≠ NP]], distinct) subsets: [[P (complexity)|P]] and [[NP-complete]]. It is one of only two, out of 12 total, problems listed in {{harvtxt|Garey|Johnson|1979}} whose complexity remains unresolved.<ref>The latest one resolved was [[minimum-weight triangulation]], proved to be NP-complete in 2008. {{citation|first1=Wolfgang|last1=Mulzer|first2=Günter|last2=Rote|title=Minimum-weight triangulation is NP-hard|journal=Journal of the ACM|volume=55|issue=2|doi=10.1145/1346330.1346336|arxiv=cs.CG/0601002 |year=2008|pages=1}}.</ref> That is, it has not been proven to be included in, nor excluded from, P or NP-complete. It is however known that the if the problem is NP-complete then the polynomial hierarchy collapses to a finite level.<ref>{{cite journal | title=Graph isomorphism is in the low hierarchy | first=Uwe | last=Schöning | journal=Journal of Computer and System Sciences | volume=37 | year=1988 | pages=312-323 }} </ref> |
||
Its generalization, the [[subgraph isomorphism problem]], is known to be NP-complete. |
Its generalization, the [[subgraph isomorphism problem]], is known to be NP-complete. |
||
Revision as of 19:28, 23 December 2011
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and 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.
In the above definition, graphs are understood to be undirected non-labeled non-weighted graphs. However, the notion of isomorphism may be applied to all other variants of the notion of graph, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception. When spoken about graph labeling with unique labels, commonly taken from the integer range 1,...,n, where n is the number of the vertices of the graph, two labeled graphs are said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic.
If an isomorphism exists between two graphs, then the graphs are called isomorphic and we write . 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 class 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
may be different for two isomorphic graphs.
Recognition of graph isomorphism
Whitney theorem
The Whitney graph isomorphism theorem,[1] 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.[2]
Algorithmic approach
While graph isomorphism may be studied in a classical mathematical way, as exemplified by the Whitney theorem, it is recognized that it is a problem to be tackled with an algorithmic approach. The computational problem of determining whether two finite graphs are isomorphic is called the graph isomorphism problem.
Its practical applications include primarily cheminformatics, mathematical chemistry (identification of chemical compounds), and electronic design automation (verification of equivalence of various representations of the design of an electronic circuit).
Curiously, it is also one of only a few problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known (and, if P ≠ NP, distinct) subsets: P and NP-complete. It is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved.[3] That is, it has not been proven to be included in, nor excluded from, P or NP-complete. It is however known that the if the problem is NP-complete then the polynomial hierarchy collapses to a finite level.[4] Its generalization, the subgraph isomorphism problem, is known to be NP-complete.
The main areas of research for the problem is design of fast algorithms, both for the general problem and for special classes of graphs, and theoretical investigations of its computational complexity.
See also
References
- ^ H. Whitney, "Congruent graphs and the connectivity of graphs", Am. J. Math., 54(1932) pp. 160–168.
- ^ Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.
- ^ The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2008. Mulzer, Wolfgang; Rote, Günter (2008), "Minimum-weight triangulation is NP-hard", Journal of the ACM, 55 (2): 1, arXiv:cs.CG/0601002, doi:10.1145/1346330.1346336.
- ^ Schöning, Uwe (1988). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37: 312–323.
- Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676.