Description
Problem 1 (6.2 from text)
Describe a mathematical model for the following scheduling problem. Given tasks T1, T2, . . . , Tn, which require times t1, t2, . . . , tn to
complete, and a set of constraints, each of the form “Ti must be completed prior to the start of Tj,” find the minimum time necessary to complete all tasks.
Problem 2 (6.8 from text)
Assuming the order of the vertices is a, b , . . . , f in Fig. 6.38, construct a depth-first spanning forest; indicate the tree, forward, back and cross arcs,
and indicate the depth-first numbering of the vertices.
Problem 3 (6.10 from text)
A root of a dag is a vertex r such that every vertex of the dag can be reached by a directed path from r. Write a program to determine whether a dag is rooted.
Problem 4 (6.14 from text)
Write a program to find the longest path in a dag. What is the time complexity of your program?
Problem 5 (6.15 from text)
Find the strong components of Fig. 6.38.
Solution
Strongly connected components:
- a
- e
- b,c,d,f
Problem 6 (6.20 from text)
Write a program that takes as input a digraph and two of its vertices. The program is to print all simple paths from one vertex to the other. What is the time complexity of your program?
Problem 7 (7.3c from text)
Consider the graph of Fig. 7.20.
- Find a depth-first spanning tree starting at a and at d.
