Difference between revisions of "Talk:TADM2E 5.13"
(Created page with "I think the answer for the third case does not work since in a weighted graph it might not be optimal to choose alternating nodes: 100 - 1 - 1 - 100 (a path with4 nodes, high...") |
(→Solution to 2 is probably wrong) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
I think the answer for the third case does not work since in a weighted graph it might not be optimal to choose alternating nodes: 100 - 1 - 1 - 100 (a path with4 nodes, high weights on the leaves, low weights on the inner nodes). | I think the answer for the third case does not work since in a weighted graph it might not be optimal to choose alternating nodes: 100 - 1 - 1 - 100 (a path with4 nodes, high weights on the leaves, low weights on the inner nodes). | ||
| + | |||
| + | == Solution to 2 is probably wrong == | ||
| + | |||
| + | |||
| + | The solution to 2) as I understand it ("do the same as for 1") is wrong. Take a tree where the root has 50 children, each having one child of its own. The algorithm results in the children of the root plus the root being selected for a total weight of 2*50 + 50 = 150, while an optimal cover would be the root plus all the leaves for a total weight of 50 + 50. | ||
| + | |||
| + | 2-coloring the tree and using either of the colors as the solution should be correct since that way, every edge is covered exactly once and as every edge contributes 1 to the weight of either of its endpoints, thats minimal cost. | ||
Latest revision as of 12:55, 13 September 2019
I think the answer for the third case does not work since in a weighted graph it might not be optimal to choose alternating nodes: 100 - 1 - 1 - 100 (a path with4 nodes, high weights on the leaves, low weights on the inner nodes).
Solution to 2 is probably wrong
The solution to 2) as I understand it ("do the same as for 1") is wrong. Take a tree where the root has 50 children, each having one child of its own. The algorithm results in the children of the root plus the root being selected for a total weight of 2*50 + 50 = 150, while an optimal cover would be the root plus all the leaves for a total weight of 50 + 50.
2-coloring the tree and using either of the colors as the solution should be correct since that way, every edge is covered exactly once and as every edge contributes 1 to the weight of either of its endpoints, thats minimal cost.
