Discrete Mathematics for Computer Science

352 CHAPTER 6 Graph Theory

joining them. List all the 3-cycles in each of the graphs (3-cycle a-b-c is counted

as being different from the 3-cycle a-c-b.)

Adjacency Matrix Adjacency Matrix

1 2 3 4 1 2 3 4 5 6

1 0 1 0 1 1 0 0 0 1 1 1

2 1 0 1 1 2 0 0 0 1 1 1

3 0 1 0 0 3 0 0 0 1 1 1

4 1 1 0 0 4 1 1 1 0 0 0

5 1 1 1 0 0 0

6 1 1 1 0 0 0

rnConnected Graphs

How do we characterize the obvious difference between graphs G and H shown in Figure

6.20?

x A V

B

G H

Figure 6.20 Two graphs.

This is an important question, because many algorithms that use graphs as models first

find the pieces of a graph, like A and B in H, and then solve the problem for each piece

separately. The notion we will use to resolve this question is based on the simple idea of

asking whether a pair of vertices can be the ends of a trail. Extensions of this simple idea

even play a role in efficient algorithms for numerical analysis involving large systems of

equations.

Section 6.8 also deals with the first problem of graph theory. The problem simply asks

whether you can stroll across the bridges over a river and return to your starting point

after having crossed each bridge exactly once. The result is interesting, because there is a

complete characterization of those graphs that model such a stroll.

6.71 The Relation CONN

The important building block for this section is the relation based on the idea of whether

two vertices can be the ends of a trail. This relation is an equivalence relation that allows

us to find the pieces of a graph, such as shown for H in Figure 6.20, in a unique way.