Динамика по поддеревьям — различия между версиями
Mihver1 (обсуждение | вклад) |
Mihver1 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | =Динамика по дереву= | ||
| + | |||
Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве. | Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве. | ||
| − | |||
{{Определение | {{Определение | ||
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно) | |neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно) | ||
| − | |definition=Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын). | + | |definition=Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын). |
}} | }} | ||
| + | [[Файл:Independent_set_tree.png|100px|right|frame|Независимый набор из красных вершин]] | ||
Версия 18:25, 13 января 2013
Динамика по дереву
Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
Определение:
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
Независимый набор из красных вершин
