s
Section 5.2 Topological Sorting
361
2(4.0)
10(3.0)
3(6.0)
4(7.0)
8(2.0)
1(3.0)
9(2.0)
5(3.0)
7(2.0)
12(0.5)
11(5.0)
Figure 5.8
2(4.0)
10(3.0)
3(6.0)
4(7.0)
8(2.0)
9(2.0)
5(3.0)
7(2.0)
12(0.5)
11(5.0)
Figure 5.9
PRaCtiCe 20 Find a topological sort for the partial ordering of Practice 17.
PRaCtiCe 19 Find another topological sort for the partial ordering of Example 16.
The algorithm given here for topological sorting is still somewhat imprecise,
as we have not given a mechanical method for finding a minimal element. Another
algorithm will be described in Section 7.4.
S e c t I o n 5 . 2 Review
technIQueS
• Construct a PERT chart from a task table.
• Find the critical path in a PERT chart.
• Do a topological sort on a partially ordered set.
maIn IDeaS
• PERT charts are diagrams of partially ordered
sets representing tasks and prerequisites among
tasks.
• A topological sort extends a partial ordering on a
finite set to a total ordering.
W
W
■
■