Relation To Partial Orders
Topological orderings are also closely related to the concept of a linear extension of a partial order in mathematics.
A partially ordered set is just a set of objects together with a definition of the "≤" inequality relation, satisfying the axioms of reflexivity (x = x), antisymmetry (if x ≤ y and y ≤x then x = y) and transitivity (if x ≤ y and y ≤ z, then x ≤ z). A total order is a partial order in which, for every two objects x and y in the set, either x ≤ y or y ≤ x. Total orders are familiar in computer science as the comparison operators needed to perform comparison sorting algorithms. For finite sets, total orders may be identified with linear sequences of objects, where the "≤" relation is true whenever the first object precedes the second object in the order; a comparison sorting algorithm may be used to convert a total order into a sequence in this way. A linear extension of a partial order is a total order that is compatible with it, in the sense that, if x ≤ y in the partial order, then x ≤ y in the total order as well.
One can define a partial ordering from any DAG by letting the set of objects be the vertices of the DAG, and defining x ≤ y to be true, for any two vertices x and y, whenever there exists a directed path from x to y; that is, whenever y is reachable from x. With these definitions, a topological ordering of the DAG is the same thing as a linear extension of this partial order. Conversely, any partial ordering may be defined as the reachability relation in a DAG. One way of doing this is to define a DAG that has a vertex for every object in the partially ordered set, and an edge xy for every pair of objects for which x ≤ y. An alternative way of doing this is to use the transitive reduction of the partial ordering; in general, this produces DAGs with fewer edges, but the reachability relation in these DAGs is still the same partial order. By using these constructions, one can use topological ordering algorithms to find linear extensions of partial orders.
Read more about this topic: Topological Sorting
Famous quotes containing the words relation to, relation, partial and/or orders:
“The adolescent does not develop her identity and individuality by moving outside her family. She is not triggered by some magic unconscious dynamic whereby she rejects her family in favour of her peers or of a larger society.... She continues to develop in relation to her parents. Her mother continues to have more influence over her than either her father or her friends.”
—Terri Apter (20th century)
“Only in a house where one has learnt to be lonely does one have this solicitude for things. One’s relation to them, the daily seeing or touching, begins to become love, and to lay one open to pain.”
—Elizabeth Bowen (1899–1973)
“The only coöperation which is commonly possible is exceedingly partial and superficial; and what little true coöperation there is, is as if it were not, being a harmony inaudible to men. If a man has faith, he will coöperate with equal faith everywhere; if he has not faith, he will continue to live like the rest of the world, whatever company he is joined to.”
—Henry David Thoreau (1817–1862)
“Selflessness is like waiting in a hospital
In a badly-fitting suit on a cold wet morning.
Selfishness is like listening to good jazz
With drinks for further orders and a huge fire.”
—Philip Larkin (1922–1986)