Transitive Reduction: Difference between revisions
Jump to navigation
Jump to search
(Created page with "In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability amont the nodes. If the graph has cycles every transitive link betw...") |
No edit summary |
||
| Line 1: | Line 1: | ||
In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability | In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability among the nodes. | ||
If the graph has cycles every transitive link between two different strongly connected components is removed. | If the graph has cycles every transitive link between two different strongly connected components is removed. | ||
See https://en.wikipedia.org/wiki/Transitive_reduction for a more detailed discussion. | See https://en.wikipedia.org/wiki/Transitive_reduction for a more detailed discussion. | ||
Latest revision as of 05:39, 30 July 2015
In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability among the nodes.
If the graph has cycles every transitive link between two different strongly connected components is removed.
See https://en.wikipedia.org/wiki/Transitive_reduction for a more detailed discussion.