47
правок
Изменения
м
→Решение
===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальный независимый набор из красных вершинМаксимальное взвешенное паросочетание]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
