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

Теперь обратимся к более сложной задаче — нахождению независимого множества с максимальным весом. Как и прежде, предполагается, что граф представляет собой дерево T = (V, E), но теперь с каждым узлом связывается положительный вес wv.

Задача нахождения независимого множества с максимальным весом заключается в нахождении в графе T = (V, E) такого независимого множества S, что общий вес.

Сначала мы опробуем идею, которая использовалась ранее для построения жадного решения в случае без весов.

Рассмотрим ребро e = (u, v), для которого v является листом. Включение v блокирует вхождение в независимое множество меньшего числа узлов; следовательно, если вес v хотя бы не меньше веса u, мы можем принять жадное решение, как это делалось в случае без весов.

Однако если wv < wu, мы сталкиваемся с дилеммой: включение u обеспечивает больший вес, но включение v оставляет больше вариантов на будущее. Похоже, простого способа принять решение локально, без учета оставшейся части графа, не существует. Впрочем, кое-что сказать все же можно.

Если узел u имеет много соседей v1, v2, …, которые являются листьями, это же решение следует принять для всех: принимая решение о том, что u не включается в независимое множество, мы с таким же успехом можем включить все соседние листья.

Таким образом, для поддерева, состоящего из u и соседних листьев, стоит рассматривать только два «разумных» решения: включать u или включать все листья.

Эти идеи будут использоваться для разработки алгоритма с полиномиальным временем средствами динамического программирования.

Как вы помните, динамическое программирование позволяет сформировать несколько разных решений, которые строятся через последовательность подзадач, и только в конце решить, какие из этих возможностей будут использоваться в общем решении.

Первое решение, которое следует принять для алгоритма динамического программирования, — выбор подзадач. Для независимого множества с максимальным весом подзадачи будут строиться размещением корня дерева T в произвольном узле r; вспомните, что это операция «ориентирует» все ребра дерева в направлении от r.

А именно: для каждого узла u ≠ r родителем p(u) узла u является узел, смежный с u на пути от корня r.

Другими соседями u становятся его дочерние узлы; для обозначения множества дочерних узлов u будет использоваться запись children(u). Узел u и все его потомки образуют поддерево Tu, корнем которого является u.

Наши подзадачи будут базироваться на этих поддеревьях Tu. Дерево Tr соответствует исходной задаче. Если u ≠ r является листом, то Tu состоит из одного узла. Для узла u, все дочерние узлы которого являются листьями, Tu является как раз таким поддеревом, о котором говорилось выше.