Saturday, April 21, 2012

Graph Isomorphism


Two graphs G=(V,E) and H=(W,F) are isomorphic if there is a bijective function f: V ® W such that for all v, w Î V:
{v,w} Î E Û {f(v),f(w)} Î F

Variant for labeled graphs
Let G = (V,E), H=(W,F) be graphs with vertex labelings l: V ® L, l’ ® L.
G and H are isomorphic labeled graphs, if there is a bijective function f: V ® W such that
For all v, w Î V: {v,w} Î E Û {f(v),f(w)} Î F
For all v Î V: l(v) = l’(f(v)).
Application: organic chemistry:
determining if two molecules are identical.

Complexity of graph isomorphism
Problem is in NP, but
No NP-completeness proof is known
No polynomial time algorithm is known


Problems are isomorphism-
complete, if they are `equally 
hard’ as graph isomorphism
Isomorphism of bipartite graphs

Isomorphism of labeled graphs

Automorphism of graphs

Given: a graph G=(V,E)

Question: is there a non-trivial 
automorphism, i.e., a bijective

 function f: V ® V, not the identity,
 with for all v,wÎV:

{v,w} Î E, if and only if 
{f(v),f(w)} Î E.




No comments:

Post a Comment