O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 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 ...

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

Start Free Trial

No credit card required