## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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 is defined on A by (that is, x is related to y) when x divides y. (Recall that we may also write in place of .) The Hasse diagram for this partial order is shown in Fig. 25.1.

Figure 25.1 Continuing, the following ideas will prove useful.

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required