<< Chapter < Page Chapter >> Page >

The poset of the set of positive real numbers with the less-than-or-equal-to relation is not a well order, because the set itself does not have any least element (0 is not in the set).

A digraph of a binary relation on a set can be simplified if the relation is a partial order. Hasse diagrams defined as follows are such graphs.

Definition(Hasse diagram): A Hasse diagram is a graph for a poset which does not have loops and arcs implied by the transitivity. Further, it is drawn so that all arcs point upward eliminating arrowheads.

To obtain the Hassse diagram of a poset, first remove the loops, then remove arcs<a, b>if and only if there is an element c that<a, c>and<c, b>exist in the given relation.

Example 10: For the relation {<a, a>,<a, b>,<a, c>,<b, b>,<b, c>,<c, c>} on set {a, b,c}, the Hasse diagram has the arcs {<a, b>,<b, c>} as shown in Figure 10.

Topological sorting

The elements in a finite poset can be ordered linearly in a number of ways while preserving the partial order. For example {∅, {1}, {2}, {1, 2}} with the partial order ⊆, can be ordered linearly as ∅, {1}, {2}, {1, 2}, or ∅, {2}, {1}, {1, 2}. In these orders a set appears before (to the left of) another set if it is a subset of the other. In real life, tasks for manufacturing goods in general can be partially ordered based on the prerequisite relation, that is certain tasks must be completed before certain other tasks can be started. For example the arms of a chair must be carved before the chair is assembled. Scheduling those tasks is essentially the same as arranging them with a linear order (ignoring here some possible concurrent processing for simplicity's sake).

The topological sorting is a procedure to find from a partial order on a finite set a linear order that does not violate the partial order. It is based on the fact that a finite poset has at least one minimal element. The basic idea of the topological sorting is to first remove a minimal element from the given poset, and then repeat that for the resulting set until no more elements are left. The order of removal of the minimal elements gives a linear order. The following algorithm formally describes the topological sorting.

Algorithm Topological Sort

Input: A finite poset<A, R>.

Output: A sequence of the elements of A preserving the order R.

integer i;

i := 1;

while ( A ≠∅) {

    pick a minimal element b from A;

    A := A - {b};

    i := i + 1;

    output b

} Example: Let A = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} with the partial order ⊆. This given A has three minimal elements {1}, {2}, and {3}.

Select {2} and remove it from A. Let A denote the resultant set i.e. A := A - {2}. The new A has two minimal elements {1}, and {3}.

Select {1} and remove it from A. Denote by A the resultant set, that is A = {{3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

This new A has two minimal elements {3} and {1, 2}.

Select {1, 2} and remove it from A.

Proceeding in like manner, we can obtain the following linear order: {{2}, {1}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Discrete structures. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10768/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete structures' conversation and receive update notifications?

Ask