Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders356

(b)Prove that if the procedure terminates with a digraph,H, thenH is a line
graph with the same vertices asG.

Hint:Show that ifHisnota line graph, then some operation must be applicable.

(c)Prove that being a DAG is a preserved invariant of the procedure.

(d)Prove that ifGis a DAG and the procedure terminates, then the walk relation
of the final line graph is a topological sort ofG.

Hint:Verify that the predicate

P.u;v/WWDthere is a directed path fromutov

is a preserved invariant of the procedure, for any two verticesu;vof a DAG.

(e)Prove that ifGis finite, then the procedure terminates.

Hint:Letsbe the number of cycles,ebe the number of edges, andpbe the number
of pairs of vertices with a directed path (in either direction) between them. Note
thatpn^2 wherenis the number of vertices ofG. Find coefficientsa;b;csuch
thatasCbpCeCcis nonnegative integer valued and decreases at each transition.

Problem 9.19.
Letbe a strict partial order on a set,A, and let

AkWWDfajdepth.a/Dkg

wherek 2 N.

(a)Prove thatA 0 ;A 1 ;:::is a parallel schedule foraccording to Definition 9.5.7.

(b)Prove thatAkis an antichain.

Problem 9.20.
We want to schedulentasks with prerequisite constraints among the tasks defined
by a DAG.

(a)Explain why any schedule that requires onlypprocessors must take time at
leastdn=pe.

(b)LetDn;tbe the DAG withnelements that consists of a chain oft 1 elements,
with the bottom element in the chain being a prerequisite of all the remaining ele-
ments as in the following figure: