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.
