Advertisement
Guest User

Untitled

a guest
Mar 24th, 2014
911
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.48 KB | None | 0 0
  1. 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.
  2.  
  3. 40
  4. 1-----------2
  5. | |
  6. 30| | 20
  7. | |
  8. | 10 |
  9. 4-----------3
  10. | |
  11. |-----------|
  12. 5
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement