|
|
The graph isomorphism problem is to determine whether or not
two graphs, G=<V,E> and G'=<V',E'>, are isomorphic.
That is, does there exist a function f:V→V',
that is 1-1 and onto, and
such that <f(u),f(v)> is in E' (is an edge of G')
exactly when <u,v> is in E.
The computational complexity of graph isomorphism is open in that
it is clearly in NP but is not known to be in P or in NPC [as of 2010].
The more general
subgraph isomorphism
problem is known to be NP-complete (NPC).
One approach to graph isomorphism is to find
canonical labellings,
canon(G) of G, and canon(G') of G',
G and G' being isomorphic iff canon(G)=canon(G').
(The computational complexity of the canonical labelling problem is
therefore also open.)
Reading
Search for [isomorphism maths graph] in
the computing bibliography.
|
|