Graph isomorphism

The isomorphism of graphs (or permutation of the vertices ) is in graph theory, the property of two graphs to be structurally identical.

When studying graph theoretical problems usually occur only on the structure of the graph, but not on the name of its nodes. In most cases, the studied graph properties then invariant with respect to isomorphism ( gr ἴσος isos "equal" and μορφή morphé "form", "shape" ), which is defined in more detail below.

Definitions

Be and graphs of the same type. A bijection is called an isomorphism between and, if the following applies:

• Is edge of iff edge of being in undirected graphs without multiple edges,
• Is edge of iff edge of being in a directed graph without multiple edges,
• In undirected graphs with multiple edges, that is, any two vertices are connected with as many edges as their corners.
• In directed graphs with multiple edges,
• Is edge of iff edge of being in hypergraphs.

Two graphs are called isomorphic to each other if there is an isomorphism between them. The mapping is called an automorphism of or, if the following also applies.

Testing for isomorphism

For testing the isomorphism of two given graphs is no efficient algorithm is known. Moreover, the complexity of the best algorithm is not yet determined until today. In particular, the isomorphism of graphs one of the few known problems in NP for which it is not known whether they are contained in P, even if they are NP -complete.

Example

These two graphs are isomorphic, although they can be presented in different ways.

Software

• Http://cs.anu.edu.au/people/bdm/nauty/ - nauty, a program to calculate the automorphism groups and canonical labelings of graphs. Two graphs are isomorphic if their canonical labelings match.