Menu
Is there an established algorithm for finding redundant edges in a graph?
For example, I'd like to find that a->d and a->e are redundant, and then get rid of them, like this:
=> 
Edit: Strilanc was nice enough to read my mind for me. "Redundant" was too strong of a word, since in the example above, neither a->b or a->c is considered redundant, but a->d is.
589
If M = N – 1, then the network is a tree, and…. If M > N – 1, then the network has circuits and is not a tree. If R = 0, then the network has no redundancy and the network is a tree. If R > 0, then the network has redundancy and the network is not a tree.
An edge (or link) of a network (or graph) is one of the connections between the nodes (or vertices) of the network. Edges can be directed, meaning they point from one node to the next, as illustrated by the arrows in the first figure below.
You want to compute the smallest graph which maintains vertex reachability.
This is called the transitive reduction of a graph. The wikipedia article should get you started down the right road.
65
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
