360
Relations, Functions, and Matrices
element must exist. To see this, let x belong to the set. If x is not minimal, then
there is a y in the set with y r x, y ∙ x. If y is not minimal, then there is a z in the
set with z r y, z ∙ y, and so on. Because the set is finite, this process cannot go on
indefinitely, so one such element must be minimal. A minimal element in a Hasse
diagram has no elements below it; a minimal element in a PERT chart has no elements to its left.
The accompanying pseudocode algorithm for topological sorting operates on
a partially ordered set (S, r). Minimal elements (picked at random if there is a
choice of minimal elements at any stage) are repeatedly removed from the ordered
set until the set is empty. Each removal of a minimal element leaves a finite partially ordered set, so that another minimal element may be found.
algoRIthm TopologicalSorT
TopSort(finite set S; partial ordering r on S )
//find a total ordering on S that is an extension of r
Local variable
integer i
//enumerates tasks in total ordering
i = 1
while S ∙ [
pick a minimal element x i from S;
S = S − 5x i 6
i = i + 1
end while
∙∙x 1 a x 2 a x 3 a c a x n is now a total ordering that extends r
write(x 1 , x 2 , x 3 , … , x n )
end function TopSort
The ordering x 1 a x 2 a x 3 a c a x n produced by this algorithm is a total
ordering. To see that it is an extension of r, suppose that x i r x j . Then x i precedes
x j and x i must be chosen as a minimal element and removed from the set before x j
can be chosen as a minimal element. Therefore i < j and x i a x j .
example 18
One topological sort of the partial ordering of Example 16 is
6, 1, 7, 2, 3, 5, 4, 8, 10, 9, 11, 12
In Figure 5.7, either 6 or 1 is minimal and may be chosen as the first element. If 6
is chosen and removed from the set, then, as shown in Figure 5.8, either 1 or 7 is
minimal. If 1 is then chosen and removed from the set (Figure 5.9), then 2, 3, 4, 5,
and 7 are all minimal and any one can be chosen next. The process continues until
all nodes have been chosen. If Ernie’s brothers all move to the city and he is left
to build rocking chairs alone, the topological sort gives an order in which he can
perform tasks sequentially.
Relations, Functions, and Matrices
element must exist. To see this, let x belong to the set. If x is not minimal, then
there is a y in the set with y r x, y ∙ x. If y is not minimal, then there is a z in the
set with z r y, z ∙ y, and so on. Because the set is finite, this process cannot go on
indefinitely, so one such element must be minimal. A minimal element in a Hasse
diagram has no elements below it; a minimal element in a PERT chart has no elements to its left.
The accompanying pseudocode algorithm for topological sorting operates on
a partially ordered set (S, r). Minimal elements (picked at random if there is a
choice of minimal elements at any stage) are repeatedly removed from the ordered
set until the set is empty. Each removal of a minimal element leaves a finite partially ordered set, so that another minimal element may be found.
algoRIthm TopologicalSorT
TopSort(finite set S; partial ordering r on S )
//find a total ordering on S that is an extension of r
Local variable
integer i
//enumerates tasks in total ordering
i = 1
while S ∙ [
pick a minimal element x i from S;
S = S − 5x i 6
i = i + 1
end while
∙∙x 1 a x 2 a x 3 a c a x n is now a total ordering that extends r
write(x 1 , x 2 , x 3 , … , x n )
end function TopSort
The ordering x 1 a x 2 a x 3 a c a x n produced by this algorithm is a total
ordering. To see that it is an extension of r, suppose that x i r x j . Then x i precedes
x j and x i must be chosen as a minimal element and removed from the set before x j
can be chosen as a minimal element. Therefore i < j and x i a x j .
example 18
One topological sort of the partial ordering of Example 16 is
6, 1, 7, 2, 3, 5, 4, 8, 10, 9, 11, 12
In Figure 5.7, either 6 or 1 is minimal and may be chosen as the first element. If 6
is chosen and removed from the set, then, as shown in Figure 5.8, either 1 or 7 is
minimal. If 1 is then chosen and removed from the set (Figure 5.9), then 2, 3, 4, 5,
and 7 are all minimal and any one can be chosen next. The process continues until
all nodes have been chosen. If Ernie’s brothers all move to the city and he is left
to build rocking chairs alone, the topological sort gives an order in which he can
perform tasks sequentially.