Discrete Mathematics

198

DISCRETE

MATHEMATICS

________________________

_

Note that, on a directed graph, the depth-ftrst search partitions edges into four classes:

I.

A tree edge (

u,

v ) is in the depth-ftrst spanning forest.

2. A

back edge (

u,

v ) is not in the spanning forest and v is an ancestor

of

u.

3.

A forward edge (u,v) is not in the spanning forest and u is an ancestor

of

v.

4. A cross edge is an edge (

u,

v ) such that neither is an ancestor

of

the other.

In an undirected graph, there are only two kinds

of

edges: tree edges and back edges.

To

see this, note

that

if

the edge (

u,

v ) is traversed when v has not yet been visited, then (

u,

v ) is a ...