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

TODO:

• Merge со статьей berkeley
• Добавить еще примеры
• Конспект с лекции. Добавить затронутые темы.

Дерево — очередная структура данных, на которой можно увидеть принцип разбиения решения на подзадачи. Представьте дерево [math]T[/math] с [math]n[/math] вершинами. Так как в поддеревья [math]T[/math] входят все потомки корня, то поддеревьев в [math]T[/math] ровно столько же, сколько и вершин ([math]n[/math] в данном случае).

Максимальное независимое множество в дереве

Если данный граф является деревом, то задача о независимом множестве эффективно решается методом динамического программирования.

Оптимальная подструктура задачи

Структура дерева сама подсказывает решение задачи: Обозначим корнем дерева любую вершину и назовем её [math]r[/math]. Пусть [math]I(u)[/math] обозначает размер максимального независимого множества вершин поддерева, корнем которого является вершина [math]u[/math]. Тогда ответом на задачу будет являться [math]I(r)[/math].

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

[math]I(u) = \max\left\{1\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\},[/math]

где grandchild обозначает всякого «внука» вершины, а child обозначает всякого потомка вершины.

Псевдокод

Считаем, что в вершине u хранится [math]I(u)[/math]:

  get_independent_set(Node u)     
      если I(u) уже посчитано, то возвратить I(u)
      //мощность множества, которое можно получить, если не брать вершину u
      children_sum = 0
      //мощность множества, которое можно получить, если взять вершину u
      grandchildren_sum = 0
      //цикл по всем детям
      for i := 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) = max(1 + grandchildren_sum, children_sum)
      возвратить I(u)

Вызов get_independent_set(r) даст ответ на задачу. Время выполнения алгоритма, очевидно, [math]O(|V| + |E|)[/math].