Динамика по поддеревьям

Материал из Викиконспекты
Перейти к: навигация, поиск

Динамика по дереву

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.

Определение:
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
Независимый набор из красных вершин