TADM2E 6.17

From Algorithm Wiki
Revision as of 19:12, 23 April 2015 by Dentin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

a) No, Look at the graph on page 196 for a counter example.


No to both. A counterexample to both is a four node, four edge graph connected in a square:

  • Edge 1 - A:B, weight 1
  • Edge 2 - B:C, weight 7
  • Edge 3 - C:D, weight 2
  • Edge 4 - D:A, weight 8

The MST is A:B:C:D, and edge 4 is never included. The path from A to D through the MST is 10, but the direct path through edge 4 is weight 8.