Isomorphism of graphs

The isomorphism of graphs (or graph isomorphism ) is in graph theory the property of two graphs to be structurally the same.

When examining problems of graph theory, the structure of the graph is usually the only important factor, not the designation of its nodes. In the vast majority of cases, the examined graph properties are then invariant with regard to isomorphism ( Greek ἴσος ísos “equal” and μορφή morphé “form”, “shape”), which is defined in more detail below.

Definitions

Let and graph be of the same type . A bijective mapping is called isomorphism between and , if the following applies: ${\ displaystyle G_ {1} = \ left (V_ {1}, E_ {1} \ right)}$ ${\ displaystyle G_ {2} = \ left (V_ {2}, E_ {2} \ right)}$ ${\ displaystyle p \ colon V_ {1} \ to V_ {2}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {2}}$

${\ displaystyle \ left \ {v, w \ right \}}$ is edge of if and only if edge of is in undirected graphs without multiple edges . ${\ displaystyle G_ {1}}$ ${\ displaystyle \ left \ {p (v), p (w) \ right \}}$ ${\ displaystyle G_ {2}}$

${\ displaystyle \ left (v, w \ right)}$ is edge of if and only if edge of is in directed graphs without multiple edges. ${\ displaystyle G_ {1}}$ ${\ displaystyle \ left (p \ left (v \ right), p \ left (w \ right) \ right)}$ ${\ displaystyle G_ {2}}$

{\ displaystyle E_ {1} \ left (\ left \ {v, w \ right \} \ right) = E_ {2} \ left (\ left \ {p \ left (v \ right), p \ left (w \ right) \ right \} \ right)}

in undirected graphs with multiple edges , d. That is, every two corners are connected with as many edges as their image corners.

{\ displaystyle E_ {1} \ left (\ left (v, w \ right) \ right) = E_ {2} \ left (\ left (p \ left (v \ right), p \ left (w \ right) \ right) \ right)}

in directed graphs with multiple edges.

${\ displaystyle \ left \ {v_ {1}, \ dotsc, v_ {k} \ right \}}$ is edge of if and only if edge of is in hypergraph . ${\ displaystyle G_ {1}}$ ${\ displaystyle \ left \ {p \ left (v_ {1} \ right), \ dotsc, p \ left (v_ {k} \ right) \ right \}}$ ${\ displaystyle G_ {2}}$

Two graphs are called isomorphic to one another if there is an isomorphism between them. The mapping is called the automorphism of or , if additionally applies. ${\ displaystyle p}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {1} = G_ {2}}$

Check for isomorphism and graph isomorphism problem

No efficient (polynomial-time) algorithm is known for checking the isomorphism of two given graphs. What is more, the complexity of the best possible algorithm has not yet been determined. In particular, the isomorphism of graphs is one of the few known problems in NP for which it is not known whether they are contained in P or whether they are NP-complete . The question of whether the graph isomorphic problem is in P (or whether it is NP-complete) is one of the great open problems in computer science. It is the last of the 12 problems in the book Computers and Intractability (1979) by Michael Garey and David S. Johnson , of which it is not known which of the complexity classes NP-complete or P they belong (or do not belong). That is why it has already been defined as a separate complexity class GI and it was investigated whether other problems are GI-difficult or GI-complete, the definitions being made in the same way as for NP-difficult and NP-complete.

László Babai announced in December 2015 that he had found an algorithm that is quasi-polynomial, that is, with which the problem can be solved in time (with the number of nodes in the graph). The behavior is called quasi- polynomial because it does not happen as quickly as in polynomial time, but it comes close to it. The previously best estimate came from Babai and Eugene Luks 1983, who specified the limit . ${\ displaystyle e ^ {{(\ log {n})} ^ {O (1)}}}$ ${\ displaystyle n}$ ${\ displaystyle e ^ {O ({\ sqrt {(n \ cdot \ log {n})}})}}$

example

These two graphs are isomorphic, although their representations differ significantly.

${\ displaystyle G_ {1} = (V_ {1}, E_ {1})}$	${\ displaystyle G_ {2} = (V_ {2}, E_ {2})}$	${\ displaystyle p \ colon V_ {1} \ to V_ {2}}$
		${\ displaystyle p (a) = 1}$ ${\ displaystyle p (b) = 6}$ ${\ displaystyle p (c) = 8}$ ${\ displaystyle p (d) = 3}$ ${\ displaystyle p (g) = 5}$ ${\ displaystyle p (h) = 2}$ ${\ displaystyle p (i) = 4}$ ${\ displaystyle p (j) = 7}$

software

nauty. A program to compute automorphism groups and canonical labeling of graphs. Two graphs are isomorphic if and only if their canonical labels match.
NetworkX . A free Python - Library

Individual evidence

↑ Babai: Graph Isomorphism in Quasipolynomial Time. Arxiv 2015. On his homepage he stated in January 2017 that a mistake found by Harald Helfgott could be corrected.
↑ Babai, Luks: Canonical labeling of graphs. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), 1983, pp. 171-183.
^ Algorithms - Isomorphism. In: NetworkX 2.2 documentation. Retrieved October 25, 2018 .

[1] Babai: Graph Isomorphism in Quasipolynomial Time. Arxiv 2015. On his homepage he stated in January 2017 that a mistake found by Harald Helfgott could be corrected.

[2] Babai, Luks: Canonical labeling of graphs. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), 1983, pp. 171-183.

[3] Algorithms - Isomorphism. In: NetworkX 2.2 documentation. Retrieved October 25, 2018 .