130
правок
Изменения
→Динамика по поддеревьям
==Динамика по поддеревьям==
Главной особенностью [[динамическое программирование|динамического программирования]] по [[Дерево, эквивалентные определения | поддеревьям ]] является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
== Задача о паросочетании максимального веса в дереве ==
Пусть задано взвешенное дерево, с весами, обозначенными как <tex>w_{i,j}</tex>, где <tex>i</tex> и <tex>j</tex> — вершины дерева, соединённые ребром. Задача: составить такое [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях | паросочетание]], чтобы суммарный вес всех рёбер, входящих в него, был максимальным.
