Discrete Mathematics for Computer Science

Graph Isomorphism 345

W Graph Isomorphism

For two graphs given abstractly as vertex and edge sets, we need to be able to determine

whether they are the same or different. Even when representations of two graphs are drawn,

it is not always clear whether the graphs are the same. The next definition details precisely

what we mean when we say that two graphs are the same.

Definition 7. Two graphs G 1 = (VI, El) and G 2 = (V2, E 2 ) are the same, or iso-

morphic, if there is a bijection F from VI to V2 such that (u, v) E E 1 if and only if

(F(u), F(v)) E E 2 .F is referred to as an isomorphism.

Figure 6.15 shows two graphs and displays an isomorphism between them.

1 2 3 a b

6 5 4 d c

G H

F: V(G) -*V(1) E(G) -E(H)

1 - a (1, 2) -* (F(l), F(2)) = (a, b)

2 -- b (2, 3) - (F(2), F(3)) = (b, f)

3. f (3, 4) - (F(3), F(4)) = (f, e)

4 - e (4, 5) - (F(4), F(5)) = (e, c)

5 - c (5, 6)- (F(5), F(6)) = (c, d)

6 - d (6, 1)--(F(6),F(1))=(d,a)

(2, 5) -(F(2), F(5)) =(b, c)

(1, 4) -- (F(1), F(4)) = (a, e)

(3, 6) -. (F(3), F(6)) = (f, d)

Figure 6.15 Graph isomorphism.

An interesting class of graphs are those that are isomorphic to their complement. A

graph that is isomorphic to its complement is called a self-complementary graph. Ex-

amples of self-complementary graphs on four and five vertices are shown in Figure 6.16.

Exercises 38 and 39 in Section 6.6 explore this class of graphs.

1 1

2 3 2 3

/ 5 2 --- _2

/ /" \ N/

1 4 1 4 4 3 4 3

G G H

Figure 6.16 Two self-complementary graphs.

As important as it may be to show that two graphs are the same, it is often just as

important to show that two graphs are not. Many algorithms for graphs need to distinguish

among graphs to complete the processing both correctly and efficiently. The two graphs

shown in Figure 6.17 are not isomorphic; can you prove it?