# Difference between revisions of "TADM2E 6.17"

From Algorithm Wiki

(Recovering wiki) |
|||

Line 1: | Line 1: | ||

a) No, Look at the graph on page 196 for a counter example. | 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. |

## Latest revision as of 19:12, 23 April 2015

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.