Discrete Mathematics for Computer Science

404 CHAPTER 6 Graph Theory

6.18.2 Application: Designing One-Way Street Grids

To alleviate traffic problems on narrow, crowded streets, one strategy is to allow traffic to

flow in only one direction. One obvious condition for a system of one-way streets to satisfy

is that traffic can somehow get from any intersection to any other intersection. The first step

in designing a system of one-way streets with this property is to describe a suitable model.

For this purpose, define a graph with vertices representing street intersections and an edge

joining a pair of vertices if the intersections they represent are joined directly. This gives

a good model for the two-way street traffic pattern. To make this into a one-way street

pattern, place directions on the edges to represent the direction traffic may flow on that

one-way street.

Definition 2. Let G be an undirected graph. An orientation 0 for G is an assignment of

directions to the edges of G.

An orientation is simply a way to make an undirected graph into a directed graph.

Obviously, there are many ways to orient the same graph. Three different ways to orient

the same graph are shown in Figure 6.64.

d d

a b a b

CC

7A eAI

(a) (b)

d

a b

C

e f

(C)

Figure 6.64 Three orientations of a graph.

In Figure 6.64(a), the orientation does not permit any directed path starting at one of

a, b, or c to reach any of d, e, or f. In addition, no directed path from d can reach either e

or f. In Figure 6.64(b), directed paths beginning at d can reach e and f as well as a, b, and

c. The graph in Figure 6.64(c) has the property that for any two vertices v and w, there is a

directed path from v to w and a directed path from w to v where v, w E {a, b, c, d, e, f}.

The property of having directed paths joining each pair of vertices is just the property that

the directed graph is strongly connected. This property, as formally defined in Definition

3, is just the property needed in any grid of one way streets.