113
правок
Изменения
→Задача о паросочетании максимального веса в дереве
== Задача о паросочетании максимального веса в дереве ==
{{Задача|definition = Cоставить такое [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях | паросочетание]], чтобы суммарный вес всех рёбер, входящих в него, был максимальным.}}Пусть задано взвешенное дерево, с весами, обозначенными как <tex>w_{i,j}</tex>, где <tex>i</tex> и <tex>j</tex> — вершины дерева, соединённые ребром. Задача: составить такое [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях | паросочетание]], чтобы суммарный вес всех рёбер, входящих в него, был максимальным.
Для решения данной задачи существует несколько алгоритмов. Например, [[алгоритм_Куна_для_поиска_максимального_паросочетания | алгоритм Куна]], который имеет верхнюю оценку порядка <tex>O \left ( n^3 \right )</tex>. Но так как нам дано дерево, то можно использовать динамическое программирование, время работы алгоритма с которым улучшается до <tex>O \left ( n \right )</tex>.
=== Псевдокод ===
'''function''' dfs(x: '''int'''): <font color = darkgreen>//в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] </font color = darkgreen> '''function''' dfs(x: '''int'''):
'''for''' (i : Ch[x])
dfs(i)
