Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders274

1. Delete an edge that is in a cycle.


2. Delete edgehu!viif there is a path from vertexuto vertexvthat does not
   includehu!vi.


3. Add edgehu!viif there is no path in either direction between vertexuand
   vertexv.

Repeat these operations until none of them are applicable.
This procedure can be modeled as a state machine. The start state isG, and the
states are all possible digraphs with the same vertices asG.

(a)LetGbe the graph with verticesf1;2;3;4gand edges

fh 1! 2 i;h 2! 3 i;h 3! 4 i;h 3! 2 i;h 1! 4 ig

What are the possible final states reachable fromG?

Aline graphis a graph whose edges are all on one path. All the final graphs in
part (a) are line graphs.

(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 path 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.