Chapter 25

Partial Orders, Total Orders, and Topological Sorting

In Example 13.2, we were introduced to a special type of binary relation on a set A—namely, the notion of the partial order. Furthermore, when the set A is finite, we found that a partial order on A could be studied by means of its Hasse diagram.

Let us recall these ideas for the set A of all (positive integer) divisors of 12. Hence A = {1, 2, 3, 4, 6, 12} and here the relation img is defined on A by img (that is, x is related to y) when x divides y. (Recall that we may also write img in place of img.) The Hasse diagram for this partial order is shown in Fig. 25.1.

Continuing, the following ideas will prove useful.

Definition 25.1: For a partial order img on a set A [often denoted by the pair img], an element x A is called maximal ...

Get Fibonacci and Catalan Numbers: An Introduction now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.