TODO:* Merge со статьей berkeley* Добавить еще примеры* Конспект с лекции. Добавить затронутые темы. Дерево {{---}} очередная структура данных, Рассмотрим динамику по дереву на которой можно увидеть принцип разбиения решения на подзадачи. Представьте дерево <tex>T</tex> с <tex>n</tex> вершинами. Так как примере задачи о максимальном независимом множестве в поддеревья <tex>T</tex> входят все потомки корня, то поддеревьев в <tex>T</tex> ровно столько же, сколько и вершин (<tex>n</tex> в данном случае)дереве.== Максимальное независимое множество в дереве == Если данный граф является деревом, то задача о независимом множестве эффективно решается методом [[динамическое программирование|динамического программирования]]. === Оптимальная подструктура задачи === Структура дерева сама подсказывает решение задачиФайл: Обозначим корнем дерева любую вершину и назовем её <tex>r</tex>Independent_set_tree. Пусть <tex>I(u)</tex> обозначает размер максимального независимого множества png|100px|right|frame|Независимый набор из красных вершин поддерева, корнем которого является вершина <tex>u</tex>. Тогда ответом на задачу будет являться <tex>I(r)</tex>. Нетрудно видеть, что если мы включаем вершину ''u'' в максимальное независимое множество, то его [[Мощность множества|мощность]] увеличивается на 1, но его детей мы брать не можем (так как они соединены ребром с вершиной ''u''); если же мы не включаем эту вершину, то мощность максимального независимого множества будет равна сумме размеров независимых множеств детей этой вершины. Остается только выбрать максимум из этих двух вариантов, чтобы получить решение задачи:: <tex>I(u) = \max\left\{1\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\},</tex>Определениегде grandchild обозначает всякого «внука» вершины, а child обозначает всякого потомка вершины. === Псевдокод ===Считаем, что в вершине u хранится <tex>I(u)</tex>: get_independent_set(Node u) если I(u) уже посчитано, то возвратить I(u) //мощность множества, которое можно получить, если не брать вершину u children_sum = 0 //мощность множества, которое можно получить, если взять вершину u grandchildren_sum = 0 //цикл по всем детям for i :|neat = 1 to child_num do children_sum = children_sum + get_independent_set(children[i]) //цикл по всем внукам for i:= 1 to grandchildren_num grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i]) //запоминаем- параметр нужен для того, чтобы определение не персчитывать ещё раз Iрастягивалось на всю страницу(uне обязательно) |definition= max(1 + grandchildren_sumПусть дано подвешенное за корень дерево, children_sum) возвратить I(u) Вызов get_independent_set(''r'') даст ответ имеющее веса на задачукаждой из ее вершин. Время выполнения алгоритмаНеобходимо выбрать такое множество вершин, очевидно, <tex>Oчто бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (|V| + |E|отец-сын)</tex>.}}
