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: