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:
“Much poetry seems to be aware of its situation in time and of its relation to the metronome, the clock, and the calendar. ... The season or month is there to be felt; the day is there to be seized. Poems beginning “When” are much more numerous than those beginning “Where” of “If.” As the meter is running, the recurrent message tapped out by the passing of measured time is mortality.”
—William Harmon (b. 1938)
“Any relation to the land, the habit of tilling it, or mining it, or even hunting on it, generates the feeling of patriotism. He who keeps shop on it, or he who merely uses it as a support to his desk and ledger, or to his manufactory, values it less.”
—Ralph Waldo Emerson (1803–1882)
“It is characteristic of the epistemological tradition to present us with partial scenarios and then to demand whole or categorical answers as it were.”
—Avrum Stroll (b. 1921)
“There is nothing on earth more exquisite than a bonny book, with well-placed columns of rich black writing in beautiful borders, and illuminated pictures cunningly inset. But nowadays, instead of looking at books, people read them. A book might as well be one of those orders for bacon and bran.”
—George Bernard Shaw (1856–1950)