Design and Analysis of Algorithms

518 Design and Analysis of Algorithms

Fig. 18.4 Directed graph G

D

(part). The cross paths between the nodes of the same edge are not shown

Part 1 Assume that vertices v

1

, v

2

, . . ., v

k

cover all the edges of G. Consider the cycle From a

1

to

[v

1

e

v

1

1

0], to [v

1

e

v

1

1

1] … and then to a

2

, then to edge lists of v

2

, v

3

and so on, and fi nally back to a

1

. This

cycle will go through every node of G

D

, except for those nodes corresponding to vertices other than v

1

, v

2

, . .

. , v

k

. For these nodes, we can expand the cycle by replacing path from [v

i

e 0] to [v

i

e 1] by the path [v

i

e 0]

[v

j

e 0] to [v

j

e 1] [v

i

e 1], where j is a vertex not included in ...