Calculus

Set Theory

Set Theory Logo

Topological Sorting

Solved Problems

Example 1.

The set \(A = \left\{ {2,3,4,6,8,9,12,18} \right\}\) is ordered by the divisibility relation "|". Determine a topological sort of the poset.

Solution.

The Hasse diagram of the partially ordered set \(\left( {A, \mid} \right)\) looks like this:

Hasse diagram of a partially ordered set ordered by divisibility relation.
Figure 14.

For topological sorting we can use the usual "less than or equal" relation \(\le\). This relation preserves the ordering defined by divisibility, so if \(a\mid b\) for numbers \(a\) and \(b,\) then \(a \le b.\) As a result, we obtain a topological sort of the poset \(\left( {A, \mid} \right)\) in the form of an ascending number sequence:

\[{2 \le 3 \le 4 \le 6 \le 8 \le 9 \le 12 \le 18.}\]

We can also build another topological sort for the poset. Using Kahn's method, we identify two minimal elements - \(2\) and \(3.\) Starting, for example, from \(3,\) we remove the elements in the following order: \(3, 9, 2, 6, 18, 4, 12, 8.\) This sequence forms a total order of kind

\[3 \preccurlyeq 9 \preccurlyeq 2 \preccurlyeq 6 \preccurlyeq 18 \preccurlyeq 4 \preccurlyeq 12 \preccurlyeq 8.\]

We can easily make sure that this total order preserves the divisibility ordering in the original set and, hence, is a topological sort of \(\left( {A, \mid} \right):\)

Alternative topological sort of a poset with the divide relation.
Figure 15.

Example 2.

The set of geometric shapes is partially ordered by area. Find a topological sort of the shapes.

Solution.

Set of geometric shapes partially ordered by area.
Figure 16.

We assume that the area of a shape \(A\) is less than the area of a shape \(B\) and denote is as \(A \preccurlyeq B,\) if the shape \(A\) is inscribed in shape \(B.\)

We identify the following relations between the given shapes:

\[2 \preccurlyeq 1,\;3 \preccurlyeq 2,\;4 \preccurlyeq 2,\;5 \preccurlyeq 4,\;6 \preccurlyeq 1,\;7 \preccurlyeq 6,\;8 \preccurlyeq 7,\;9 \preccurlyeq 6.\]

Draw the Hasse diagram for the partially ordered set:

Hasse diagram of the poset with geometric shapes.
Figure 17.

A possible topological sort (it can be easily built using Kahn's algorithm) has the following form:

\[8 \preccurlyeq 5 \preccurlyeq 9 \preccurlyeq 7 \preccurlyeq 4 \preccurlyeq 3 \preccurlyeq 6 \preccurlyeq 2 \preccurlyeq 1.\]

Example 3.

General relativity requires a knowledge of mathematics and physics, which is illustrated by the diagram in Figure \(18.\) Determine an order in which these courses can be taken.

Solution.

Prerequisites of math and physics courses for learning general relativity.
Figure 18.

First we note that the relation defined by the digraph is antisymmetric and transitive. Assuming, for simplicity, that it is also reflexive, we get a partially ordered set, which can be topologically sorted.

There are two vertices that have no incoming edges - Calculus and Linear Algebra. By applying Kahn's algorithm, we select Calculus and remove it from the digraph. This will be the first course in the sorted output list (aren't we lucky?). Then we repeat the process by successively removing Linear Algebra, ODE, and so on.

One of the possible topological sorts looks like this:

\[\text{Calculus} \preccurlyeq \text{Linear Algebra} \preccurlyeq \text{ODE} \preccurlyeq \text{PDE} \preccurlyeq \text{Classical Mechanics} \preccurlyeq \text{Electromagnetism} \preccurlyeq \text{Real Analysis} \preccurlyeq \text{Differential Geometry} \preccurlyeq \text{General Relativity}.\]
Teaching general relativity.
Figure 19.

Example 4.

A partially ordered set is given by the digraph shown in Figure \(20.\) Find a topological sort of the graph using \(DFS\) algorithm.

Solution.

PDigraph of a partially ordered set to be topologically sorted.
Figure 20.

We identify \(4\) nodes that have no incoming edges: \(1,2,3\) and \(4.\) For each of these elements, we determine the list of adjacent vertices:

\[\text{Vertex }1 : 1, 5, 8, 6, 9, 10, 11\]
\[\text{Vertex }2 : 2, 5, 9, 11\]
\[\text{Vertex }3 : 3, 5, 8, 6, 9, 10, 11, 7\]
\[\text{Vertex }4 : 4, 6\]

Filter out coinciding elements:

\[\require{cancel}\text{Vertex }2 : 2, \cancel{5}, \cancel{9}, \cancel{11}\]
\[\text{Vertex }3 : 3, \cancel{5}, \cancel{8}, \cancel{6}, \cancel{9}, \cancel{10}, \cancel{11}, 7\]
\[\text{Vertex }4 : 4, \cancel{6}\]

Combine the blocks to get a topological sort:

\[\underbrace {4}_{4} \preccurlyeq \underbrace{3 \preccurlyeq 7}_{3} \preccurlyeq \underbrace {2}_ {2} \preccurlyeq \underbrace{1 \preccurlyeq 5 \preccurlyeq 8 \preccurlyeq 6 \preccurlyeq 9 \preccurlyeq 10 \preccurlyeq 11}_{1}\]
Page 1 Page 2