TAOCP 2.2.3 Exercise 14

Section 2.2.3: Linked Allocation

Exercise 14. [M21] A linear ordering of a set $S$, also called a total ordering, is a partial ordering that satisfies the additional "comparability" condition

$$ \text{(iv)} \qquad \text{For any two objects } x,\ y \text{ in } S,\ \text{either } x \preceq y \text{ or } y \preceq x. $$

Prove directly from the definitions given that a topological sort can result in only one possible output if and only if the relation $\preceq$ is a linear ordering. (You may assume that the set $S$ is finite.)

Verified: yes
Solve time: 33s

---

Solution

Assume first that $\preceq$ is a linear ordering on the finite set $S$.

Let the elements of $S$ be arranged in topological order as

$$ x_1,x_2,\ldots,x_n. $$

Since $\preceq$ is a linear ordering, any two distinct elements are comparable. For each $k<n$, either $x_k\preceq x_{k+1}$ or $x_{k+1}\preceq x_k$.

The second alternative is impossible. If $x_{k+1}\preceq x_k$, then the definition of topological order requires $x_{k+1}$ to appear before $x_k$, contrary to the arrangement above. Hence

$$ x_k\preceq x_{k+1} \qquad (1\le k<n). $$

By transitivity,

$$ x_i\preceq x_j \qquad (1\le i<j\le n). $$

Suppose that

$$ y_1,y_2,\ldots,y_n $$

is another topological ordering. We prove that $y_i=x_i$ for every $i$.

The element $x_1$ satisfies

$$ x_1\preceq z $$

for every $z\in S$. Indeed, for any $z\ne x_1$, comparability gives either $x_1\preceq z$ or $z\preceq x_1$; the second possibility would force $z$ to precede $x_1$ in the topological order $x_1,\ldots,x_n$, which is impossible. Thus no element can precede $x_1$ in any topological ordering, so $y_1=x_1$.

Remove $x_1$ from consideration. The same argument applied to the remaining elements shows that $x_2$ must be second in every topological ordering. Continuing inductively yields

$$ y_i=x_i \qquad (1\le i\le n). $$

Therefore there is exactly one topological ordering.

Conversely, assume that a topological sort can result in only one possible output. We show that $\preceq$ is a linear ordering.

Suppose, to the contrary, that $\preceq$ is not linear. Then there exist distinct elements $a,b\in S$ such that neither

$$ a\preceq b $$

nor

$$ b\preceq a. $$

Consider any topological ordering of $S$. Since $a$ and $b$ are incomparable, the definition of topological order imposes no restriction on their relative positions.

Let

$$ x_1,x_2,\ldots,x_n $$

be a topological ordering. If $a$ precedes $b$, interchange the positions of $a$ and $b$; if $b$ precedes $a$, interchange them in the opposite direction. No condition of topological order is violated, because there is no relation $a\preceq b$ and no relation $b\preceq a$.

The resulting arrangement is a different topological ordering. Hence at least two topological orderings exist, contradicting the assumption that the output is unique.

Therefore no two distinct elements can be incomparable. For every $x,y\in S$, either

$$ x\preceq y $$

or

$$ y\preceq x. $$

Since $\preceq$ already satisfies the axioms of a partial ordering, condition (iv) is now satisfied, and $\preceq$ is a linear ordering.

Thus a topological sort has a unique possible output if and only if $\preceq$ is a linear ordering.

This completes the proof.

∎