Мне нужен алгоритм для поиска максимального независимого набора в дереве. Я думаю, что начинаем со всех листовых узлов, а затем удаляем прямые родительские узлы в эти листовые узлы, затем выбираем родительские узлы родительских узлов, которые мы удалили, повторяем эту процедуру рекурсивно, пока не получим root. и это делается в O (n) времени? любой ответ приветствуется. спасибо.
И может ли кто-нибудь указать мне алгоритм поиска максимального доминирующего набора в дереве.
Вы можете вычислить максимальный независимый набор путем первого поиска глубины через дерево.
Поиск будет вычислять два значения для каждого поддерева в графике:
Они могут быть вычислены рекурсивно, рассматривая два случая:
Корень поддерева не включен.
B (i) = sum (max (A (j), B (j)) для j у детей (i))
Вложен корень поддерева.
A (i) = 1 + sum (B (j) для j у детей (i))
Размер максимального независимого множества во всем дереве равен max (A (корень), B (корень)).
В соответствии с определение доминирующего набора в wikipedia максимальное доминирующее множество всегда тривиально равно включению всех node в график - но это, вероятно, не то, что вы имеете в виду?
Чтобы найти максимальный независимый набор вершин, мы можем использовать важное свойство дерева: каждое дерево является двудольным, т.е. мы можем покрасить вершины дерева, используя только два цвета, так что никакие две соседние вершины не имеют тот же цвет.
Проведите обход DFS и начните окрашивать вершины с помощью BLACK и WHITE.
Выберите набор вершин (BLACK или WHITE), число которых больше. Это даст вам максимальный независимый набор вершин для дерева.
Некоторая интуиция за тем, почему работает этот алгоритм:
Вернемся сначала к определению максимального независимого множества вершин. Нам нужно выбрать только одну конечную точку ребра, и мы должны покрыть все ребра дерева, удовлетворяющие этому свойству. Нам не разрешено выбирать обе конечные точки ребра.
Теперь, что делает биколорирование графика? Он просто делит множество вершин на два подмножества (WHITE и BLACK), а белые вершины WHITE напрямую связаны с BLACK. Таким образом, если мы выберем либо ВСЕ БЕЛЫЕ, либо ВСЕ ЧЕРНЫЕ, мы по сути выбираем независимый набор вершин. Таким образом, чтобы выбрать максимальный независимый set, go для подмножества, размер которого больше.