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