Graph Isomorphism Article Index for
Graph
Articles about
Graph Isomorphism
Website Links For
Graph
 

Information About

Graph Isomorphism




: f: V(G) ightarrow V(H)

with the property that any two vertices u and v from G are adjacent if and only if f(u) and f(v) are adjacent in H.

If an Isomorphism can be constructed between two graphs, then we say those graphs are isomorphic.

Determining whether two graphs are isomorphic is the Graph Isomorphism Problem .


EXAMPLE


Consider these two graphs:

Although these graphs look very different, they are isomorphic; one isomorphism between them is

:: f(a) = 1

:: f(b) = 6

:: f(c) = 8

:: f(d) = 3

:: f(g) = 5

:: f(h) = 2

:: f(i) = 4

:: f(j) = 7


SEE ALSO