Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 19.6 Topological sorting

Sometimes we want to turn a partial order into a total order. What makes an order partial instead of total is the presence of pairs of incomparable elements. So to convert our partial order into a total order we just need to impose an order relation on those previously incomparable element pairs. However, for each pair of incomparable elements there is a choice to be made of which will become the smaller and which the larger in the new total order. And we cannot carry out these choices completely arbitrarily, because we risk contradicting the required properties of a partial order (see Example 19.6.1).
The following definitions apply to a partial order \(\mathord{\partorder}\) on a set \(A\text{.}\)
compatible total order
a total order \(\mathord{\le}\) on \(A\) such that if \(a_1 \partorder a_2\) then \(a_1 \le a_2\)
topological sorting
a process for determining a compatible total order

Example 19.6.1. A failed attempt at topological sorting.

The relation \(\mathord{\subseteq}\) on \(\powset{\N}\) is a partial order but not a total order. Consider what happens when we begin trying to build a total order on \(\powset{\N}\) out of \(\mathord{\subseteq}\) by choosing relations between previously incomparable elements arbitrarily.
  • Elements \(\{1\},\{2,3\}\) are \(\mathord{\subseteq}\)-incomparable; choose \(\{2,3\} \le \{1\}\text{.}\)
  • Elements \(\{1\},\{2\}\) are \(\mathord{\subseteq}\)-incomparable; choose \(\{1\} \le \{2\}\text{.}\)
  • …
Now, \(\{2\} \subseteq \{2,3\}\) is already true, so to be compatible we must set \(\{2\} \leq \{2,3\}\) in the new total order. But now \(\{1\} \leq \{2\} \leq \{2,3\}\) would dictate \(\{1\} \leq \{2,3\}\) to satisfy the transitive property, but this contradicts our first arbitrary choice above.

Note 19.6.2.

If \(A\) is countable, whether finite or countably infinite, then specifying a total order on \(A\) amounts to writing the elements of \(A\) in an ordered list. (See Example 19.4.6 and Remark 19.4.7.) In that case, topological sorting amounts to creating such an ordered list so that if \(a \partorder b\) then \(a\) appears before \(b\) in the list.

Note 19.6.4.

In Step 2 of the algorithm, if \(A_i\) contains a minimum element, then you must choose that element, since in that case no other minimal element can exist (see the Fact 19.5.13).

Worked Example 19.6.5.

Consider
\begin{equation*} A = \powset{\{0,1,2\}} = \bigl\{ \emptyset, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\} \bigr\}\text{.} \end{equation*}
Apply Algorithm 19.6.3 to determine a total order \(\mathord{\leq}\) on \(A\) that is compatible with \(\mathord{\subseteq}\text{.}\)
Solution 1. Algorithm solution
In \(A_0 = A\text{,}\) we must choose \(a_0 = \emptyset\text{,}\) since it is the minimum. Now remove \(a_0\) so that
\begin{equation*} A_1 = \bigl\{ \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\} \bigr\}. \end{equation*}
Choose a minimal element from \(A_1\text{:}\) let \(a_1 = \{2\}\text{.}\) Now remove \(a_1\text{;}\) set
\begin{equation*} A_2 = \bigl\{ \{0\}, \{1\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\} \bigr\}. \end{equation*}
Choose a minimal element from \(A_2\text{:}\) let \(a_2 = \{0\}\text{.}\) Now remove \(a_2\text{;}\) set
\begin{equation*} A_3 = \bigl\{ \{1\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\} \bigr\}. \end{equation*}
Choose a minimal element from \(A_3\text{:}\) let \(a_3 = \{0,2\}\text{.}\) Now remove \(a_3\text{;}\) set
\begin{equation*} A_4 = \bigl\{ \{1\}, \{0,1\}, \{1,2\}, \{0,1,2\} \bigr\}. \end{equation*}
We must choose \(a_4 = \{1\}\text{,}\) since it is the minimum in \(A_4\text{.}\) Now remove \(a_4\text{;}\) set
\begin{equation*} A_5 = \bigl\{ \{0,1\}, \{1,2\}, \{0,1,2\} \bigr\}. \end{equation*}
Choose a minimal element from \(A_5\text{:}\) let \(a_5 = \{1,2\}\text{.}\) Now remove \(a_5\text{;}\) set \(A_6 = \bigl\{ \{0,1\}, \{0,1,2\} \bigr\}\text{.}\) We must choose \(a_6 = \{0,1\}\text{,}\) since it is the minimum in \(A_6\text{.}\) There is only one element left; set \(A_7 = \bigl\{ \{0,1,2\} \bigr\}\) and choose \(a_7 = \{0,1,2\}\text{.}\) So we have
\begin{equation*} \emptyset \leq \{2\} \leq \{0\} \leq \{0,2\} \leq \{1\} \leq \{1,2\} \leq \{0,1\} \leq \{0,1,2\}. \end{equation*}
Notice that the maximum element of \(A\) ended up at the “top” of the total order and the minimum element was forced to the “bottom.”
Solution 2. Graphical solution
We can perform the algorithm of topological sorting graphically; at each step, choose a vertex that has no adjacent vertices below it in the graph, then cross that vertex and any adjacent edges out of the graph. (See Figure 19.6.6.)
Our end result is a list of our choices, in order:
\begin{equation*} \emptyset \leq \{2\} \leq \{0\} \leq \{0,2\} \leq \{1\} \leq \{1,2\} \leq \{0,1\} \leq \{0,1,2\}. \end{equation*}
Notice that the maximum element of \(A\) ended up at the “top” of the total order and the minimum element was forced to the “bottom”.
First step in a graphical approach to topological sorting.
(a) Choose \(a_0 = \emptyset\text{.}\)
Second step in a graphical approach to topological sorting.
(b) Choose \(a_1 = \{2\}\text{.}\)
Third step in a graphical approach to topological sorting.
(c) Choose \(a_2 = \{0\}\text{.}\)
Fourth step in a graphical approach to topological sorting.
(d) Choose \(a_3 = \{0,2\}\text{.}\)
Fifth step in a graphical approach to topological sorting.
(e) Choose \(a_4 = \{1\}\text{.}\)
Sixth step in a graphical approach to topological sorting.
(f) Choose \(a_5 = \{1,2\}\text{.}\)
Seventh step in a graphical approach to topological sorting.
(g) Choose \(a_6 = \{0,1\}\text{.}\)
Eighth step in a graphical approach to topological sorting.
(h) Choose \(a_7 = \{0,1,2\}\text{.}\)
Figure 19.6.6. Example of a graphical approach to topological sorting.

Note 19.6.7.

Compatible total orders are not unique: in the previous worked example, the order in which the elements of \(A\) were originally written represents another compatible total order:
\begin{equation*} \emptyset \leq \{0\} \leq \{1\} \leq \{2\} \leq \{0,1\} \leq \{0,2\} \leq \{1,2\} \leq \{0,1,2\} \text{.} \end{equation*}
<Prev^TopNext>