Discrete Mathematics for Computer Science

346 CHAPTER 6 Graph Theory

a 1

b 6 2

e: c 5 3

d 4

G H

Figure 6.17 Two nonisomorphic graphs.

One way to prove that these two graphs are not isomorphic is to show that they do not

share a property, called an invariant, that is preserved by an isomorphism. For example,

two isomorphic graphs will have the same number of even vertices. A triangle in a graph G

must be mapped to a triangle in any graph to which G is isomorphic. Since the graph G in

Figure 6.17 contains a triangle but the graph H in Figure 6.17 has no triangle, the graphs

are not isomorphic.

The exercises in Section 6.6 include problems about determining properties that are

preserved by an isomorphism. These results will be useful when you face the problem of

deciding whether two graphs are the same. Chemists use graph isomorphism to determine

if two graphical representations of a chemical are, in fact, the same chemical. Graph algo-

rithms, especially those dealing with coloring problems, often need to distinguish among

a set of graphs to determine appropriate processing steps. An algorithm must be able to

determine exactly which graph, up to isomorphism, is to be processed at a particular step

of the algorithm.

rnRepresentation of Graphs

Two methods commonly are used for representing graphs (other than drawing a picture

or just listing the vertices and edges). Both of these methods lead to widely used com-

puter representations of a graph. In some applications, the order of the complexity of the

algorithm will even depend on which representation is used.

6.5.1 Adjacency Matrix

For positive integers n and m, a matrix A of size it x m is a rectangular array of val-

ues organized as n rows, each with m entries called columns. The value at a location

row i and column j is denoted as A(i, j). Let G = (V, E) be a graph with n vertices

named 1, 2, ... ., n. An n x n matrix A is an adjacency matrix for G if and only if for

1 < i, j <n,

Ai h)11 A0 for for (i, (i, j)eEj) g E