Discrete Mathematics for Computer Science

394 CHAPTER 6 Graph Theory

6.14.2 Directed Trails, Paths, Circuits, and Cycles

The definitions for a directed trail, a directed path, and a directed cycle in a directed graph

are straightforward generalizations of the corresponding notions for undirected graphs.

Definition 3. Let D = (V, E) be a directed graph. A directed trail in D is a sequence

of not necessarily distinct vertices vl, v), v2. V Vk such that (vi, vi+]) E E for 1 < i <

k - 1 and the edges are distinct. If all the vertices in a directed trail are distinct, then the

directed trail is a directed path. A directed trail for which vi = Vk is a directed circuit.

A directed trail for which all the vertices V1, V2, ... , Vk-1 are distinct and vi = Vk is a

directed cycle. The length of a directed trail is the number of edges it contains.

Figure 6.54 gives examples of these notions.

1 2 3 6 5 4 3 1 6

S1 2 Directed 00 2 ~pe: 3 Trail 5 4

Directed Path

1 6 5 1 4 3 1

Directed Circuit

(^4 1 2 3 5 1)
D Directed Cycle
Figure 6.54 Directed trail, path, circuit, and cycle in D.

6.14.3 Directed Graph Isomorphism

The generalization of the notion of an isomorphism to the case of directed graphs gives a

formal definition of what it means to say that two directed graphs are isomorphic regardless

of how the vertices and edges are labeled.

Definition 4. Let DI = (V 1 , E 1 ) and D 2 = (V 2 , E 2 ) be directed graphs. D 1 and D 2 are

the isomorphic directed graphs if and only if there is a bijection F : V -* V 2 such that

(a, b) E EI if and only if (F(a), F(b)) E E 2.

Remember that in a directed graph, the edge directed from a to b and denoted (a, b)

is not the same as the edge denoted (b, a).

Application: Scheduling a Meeting Facility

A small meeting facility consists of three scheduleable resources: a meeting room for large

groups, a lobby area for small-group meetings, and a slide projector for use in either room.

Two organizations are planning to use the facility on the same afternoon, so a schedule

for the resources is needed. The first organization would like to start in the lobby for a

slide presentation for its program committee, then move into the large meeting room for

a slide presentation to its full membership. The second organization is planning a slide

presentation to its full membership in the large meeting room. The second organization