Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- This is a 4 node graph with 5 edges of edge lengths 40, 30, 20, 10, and 5. The edge of length 5 is between edges 4 and 3. The edge of weight 10 will be a part of the MST only if it is not the heaviest edge of all cycles that it is a part of. But it is the heaviest edge in the cycle 4 to 3 to 4. So it is not a part of some MST.
- 40
- 1-----------2
- | |
- 30| | 20
- | |
- | 10 |
- 4-----------3
- | |
- |-----------|
- 5
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement