Discrete Mathematics for Computer Science

354 CHAPTER 6 Graph Theory

to show that CONN is transitive let v, w and x be vertices of G such that v CONN w and

w CONN x. Since v CONN w and w CONN x, there are trails in G from v to w and from

w to x. By following the trail from v to w and then following the trail from w to x, a trail

from v to x is formed in G provided no edge occurs in both trails. If an edge occurs in

both trails, it is easy to modify this sequence of vertices and edges to make it into a trail

from v to x. This shows that v CONN x. Therefore, the relation CONN is transitive. Since

CONN has been shown to be reflexive, symmetric, and transitive, CONN is an equivalence

relation. U

Since CONN is an equivalence relation, the vertex set of any graph is uniquely parti-

tioned into equivalence classes by means of the relation (see Theorem (^2) in Section 3.6.1).
For a graph G = (V, E), let C C V such that C is an equivalence class of V determined
by CONN. The induced subgraph contains all the edges of G that have both their
ends in C. The subgraph is a connected component of G. Similarly, the subgraphs
induced by the other distinct equivalence classes of G relative to CONN determine all the
other connected components of G. Figure 6.21 shows an example of how CONN is used to
find the connected components of a graph.
G = (11, 2, 3, 4, 5, 6, 7, 8, 9, 101, [(1, 2), (2, 4), (2, 6), (1, 4),
(5, 6), (3, 5), (3, 4), (7, 8), (8, 9) (8, 10), (10, 7)])
Equivalence Classes of CONN
(1, 2, 3, 4, 5, 61 17, 8, 9, 10]
Components
1 7

6 /

10 8

5

3

4 9

<[1, 2, 3, 4, 5, 6]> <(7, 8, 9, 10]>

Figure 6.21 Connected components.

If a graph is connected, it contains a single equivalence class with respect to the re-

lation CONN. In any case, each vertex of a graph is contained in exactly one connected

component of a graph.

In solving problems such as finding the connected components of a graph, we need an

efficient method for examining all the vertices and edges of a graph. Two methods that are

very efficient are depth first search and breadth first search.

6.7.2 Depth First Search

A depth first search of a connected graph G = (V, E) is a recursive algorithm to examine

the vertices and the edges of a graph. To begin a depth first search, choose an adjacency

list representation for G. Different adjacency list structures will give rise to examining the