Difference between revisions of "TADM2E 5.13"
From Algorithm Wiki
| Line 1: | Line 1: | ||
(a) We can determine that leaf should never be included into the cover. Therefore all leaves should be unmarked, which means that all of their parents should be marked. Now we remove all leaves from the tree and all of their parents, together with all of their edges. We then repeat this process on the modified tree. | (a) We can determine that leaf should never be included into the cover. Therefore all leaves should be unmarked, which means that all of their parents should be marked. Now we remove all leaves from the tree and all of their parents, together with all of their edges. We then repeat this process on the modified tree. | ||
| + | |||
(b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward. | (b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward. | ||
Revision as of 15:16, 25 March 2015
(a) We can determine that leaf should never be included into the cover. Therefore all leaves should be unmarked, which means that all of their parents should be marked. Now we remove all leaves from the tree and all of their parents, together with all of their edges. We then repeat this process on the modified tree.
(b) Since the degree of the parent of a leaf is sum of degrees of all leaves + 1 we see that, again, the leaves should be left unmarked. The process after that, as shown above, is straightforward.
