In Directed Acyclic Graphs
The transitive reduction of a finite directed graph G is a graph with the fewest possible edges that has the same reachability relation as the original graph. That is, if there is a path from a vertex x to a vertex y in graph G, there must also be a path from x to y in the transitive reduction of G, and vice versa. The following image displays drawings of graphs corresponding to a non-transitive binary relation (on the left) and its transitive reduction (on the right).
The transitive reduction of a finite directed acyclic graph G is unique, and consists of the edges of G that form the only path between their endpoints. In particular, it is always a subgraph of the given graph. For this reason, the transitive reduction coincides with the minimum equivalent graph in this case.
In the mathematical theory of binary relations, any relation R on a set X may be thought of as a directed graph that has the set X as its vertex set and that has an arc xy for every ordered pair of elements that are related in R. In particular, this method lets partially ordered sets be reinterpreted as directed acyclic graphs, in which there is an arc xy in the graph whenever there is an order relation x < y between the given pair of elements of the partial order. When the transitive reduction operation is applied to a directed acyclic graph that has been constructed in this way, it generates the covering relation of the partial order, which is frequently given visual expression by means of a Hasse diagram.
Read more about this topic: Transitive Reduction
Famous quotes containing the word directed:
“In history the great moment is, when the savage is just ceasing to be a savage, with all his hairy Pelasgic strength directed on his opening sense of beauty;—and you have Pericles and Phidias,—and not yet passed over into the Corinthian civility. Everything good in nature and in the world is in that moment of transition, when the swarthy juices still flow plentifully from nature, but their astrigency or acridity is got out by ethics and humanity.”
—Ralph Waldo Emerson (1803–1882)