Каков хороший алгоритм для получения минимального покрытия вершин дерева?

Question

Какой хороший алгоритм для получения минимального покрытия вершин дерева?

INPUT:

Соседи узла.

ВЫВОД:

Минимальное количество вершин.

Answer 1

Я не совсем понял после прочтения ответов здесь, поэтому я думал, что я отправлю один из здесь

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

Так, например, если у вас было следующее дерево:

    A
   / \
  B   C
 / \ / \
D  E F  G

Обратите внимание, что при проверке вы знаете, что минимальная вершина покрытия равна {B, C}. Мы найдем эту минимальную обложку.

Здесь мы начнем с A.

А в обложке

Мы переходим к двум поддеревам B и C и повторяем этот алгоритм. Мы не можем просто заявить, что B и C не находятся в обложке, потому что даже если AB и AC покрыты, мы не можем ничего сказать о том, нужны ли нам B и C быть в обложке или нет.

(Подумайте о следующем дереве, где корень и один из его дочерних элементов находятся в минимальной обложке ({A, D})

  A
 /|\___
B C    D
      /|\
     E F G

)

А не в обложке

Но мы знаем, что AB и AC должны быть покрыты, поэтому мы должны добавить B и C к обложке. Поскольку B и C находятся на обложке, мы можем использовать их детей вместо того, чтобы использовать B и C (даже если бы мы это сделали, это не дало бы нам больше информации).

"Формально"

Пусть C(x) будет размером минимальной обложки с корнем в x.

Тогда

C(x) = min ( 
            1 + sum ( C(i) for i in x's children ),                    // root in cover
            len(x's children) + sum( C(i) for i in x's grandchildren)  // root not in cover
            )

Answer 2

T (V, E) - это дерево, из которого следует, что для любого листа любое минимальное покрытие вершин должно включать либо лист, либо вершину, смежную с листом. Это дает нам следующий алгоритм нахождения S, покрытия вершин:

1. Найти все листья дерева (BFS или DFS), O (| V |) в дереве.
2. Если (u, v) - ребро, такое, что v - лист, добавьте u к покрытию вершины и обрежьте (u, v). Это оставит вас с лесом T_1 (V_1, E_1), ..., T_n (U_n, V_n).
3. Теперь, если V_i = {v}, что означает | V_i | = 1, то это дерево можно отбросить, поскольку все ребра, падающие на v, покрыты. Это означает, что у нас есть условие завершения для рекурсии, где у нас есть одна или нет вершин, и мы можем вычислить S_i в качестве покрытия для каждого T_i и определить S как все вершины из шага 2 объединяют обложку каждого T_i .

Теперь осталось только проверить, что если исходное дерево имеет только одну вершину, мы возвращаем 1 и никогда не запускаем рекурсию, и можно вычислить минимальное покрытие вершин.

Edit:

На самом деле, подумав немного, можно сделать это с помощью простого варианта DFS.

Answer 3

Я надеюсь здесь вы можете найти более связанный ответ на ваш вопрос.

---

Я думал о своем решении, возможно, вам придется его отшлифовать, но пока динамическое программирование находится в одном из ваших тегов, вам, вероятно, потребуется:

1. Для каждой вершины u определить S + (u) покройте размер вершинами u и S- (u) покрытие без вершины u.
2. S + (u) = 1 + сумма (S- (v)) для каждого ребенка v из u.
3. S- (u) = Сумма (max {S- (v), S + (v)}) для каждого ребенка v из u.
4. Ответ - max (S + (r), S- (r)), где r - корень вашего дерева.

---

После прочтения это . Изменен вышеуказанный алгоритм, чтобы найти максимально независимый набор, так как в статье в вики указано

Множество является независимым тогда и только тогда, когда его дополнение является покрытием вершин.

Таким образом, изменяя min на max, мы можем найти максимальное независимое множество и дополнить минимальное покрытие вершин, поскольку обе задачи эквивалентны.

Answer 4

Мы можем использовать алгоритм на основе DFS для решения этой проблемы:

DFS(node x)
{

    discovered[x] = true;

    /* Scan the Adjacency list for the node x*/
    while((y = getNextAdj() != NULL)
    {

        if(discovered[y] == false)
        {

            DFS(y);

           /* y is the child of node x*/
           /* If child is not selected as a vertex for minimum selected cover
            then select the parent */ 
           if(y->isSelected == false)
           {
               x->isSelected = true;
           }
        }
   }
}

Листовой узел никогда не будет выбран для покрытия вершины.

Answer 5

{- Haskell implementation of Artem's algorithm -}

data Tree = Branch [Tree]
    deriving Show

{- first int is the min cover; second int is the min cover that includes the root -}
minVC :: Tree -> (Int, Int)
minVC (Branch subtrees) = let
    costs = map minVC subtrees
    minWithRoot = 1 + sum (map fst costs) in
    (min minWithRoot (sum (map snd costs)), minWithRoot)

Answer 6

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

Здесь DP1 [v] для любой вершины v = когда мы ее включаем. DP2 [v] для любой вершины v = когда мы ее не включаем.

DP1 [v] = 1 + сумма (мин (DP2 [c], DP1 [c])) - это означает, что текущий и может включать или не включать его дочерние элементы, исходя из того, что является оптимальным.

DP2 [v] = сумма (DP1 [c]) - это означает, что не включая текущий, нам нужно включить потомков текущей вершины. Здесь c - потомок вершины v.

Тогда наше решение min (DP1 [root], DP2 [root])

#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > g;

int dp1[100010], dp2[100010];

void dfs(int curr, int p){
    for(auto it : g[curr]){
        if(it == p){
            continue;
        }
        dfs(it, curr);
        dp1[curr] += min(dp1[it], dp2[it]);
        dp2[curr] += dp1[it];
    }
    dp1[curr] += 1;
}

int main(){
    int n;
    cin >> n;
    g.resize(n+1);
    for(int i=0 ; i<n-1 ; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << min(dp1[1], dp2[1]);
    return 0;
} 

Answer 7

Я бы просто использовал линейную программу для решения задачи о минимальном покрытии вершин. Формулировка в виде целочисленной линейной программы может выглядеть как приведенная здесь: Формула ILP

Я не думаю, что ваша собственная реализация будет быстрее, чем эти высоко оптимизированные LP-решатели.