Qu'est-ce qu'un bon algorithme pour obtenir la couverture vertex minimale d'un arbre?

Qu'est ce qu'un bon algorithme pour obtenir le minimum vertex cover d'un arbre?

D'ENTRÉE:

Le nœud voisin.

De SORTIE:

Le nombre minimum de sommets.

source d'informationauteur John Retallack

  1. 9

    J'espère ici vous pouvez trouver plus liés réponse à votre question.

    Je pensais à ma solution, probablement vous aurez besoin de polir mais tant que la dynamique de programmation est dans l'une de vos étiquettes, vous aurez probablement besoin de:

    1. Pour chaque valeur de u sommet de définir S+(u) est
      taille du couvercle avec un sommet u et S-(u)
      couvrir sans sommet u.
    2. S+(u)= 1 + Somme(S(v)) pour chaque enfant de v de u.
    3. De S(u)=Somme(max{S(v),S+(v)}) pour chaque enfant de v de u.
    4. Réponse est max(S+(r), S-(r)) où r est la racine de votre arborescence.

    Après la lecture de cette. Changé l'algorithme ci-dessus pour trouver le maximum de réglages indépendants, puisque dans l'article wiki a déclaré

    Un ensemble est indépendante si et seulement si son complémentaire est un vertex cover.

    Donc en changeant de min à max, nous pouvons trouver le maximum de réglages indépendants et par complimenter le minimum vertex cover, puisque les deux problèmes sont équivalents.

  2. 11

    T(V,E) est un arbre, ce qui implique que, pour toute feuille, tout minimale du vertex cover est d'inclure la feuille ou le sommet adjacent à la feuille. Cela nous donne l'algorithme suivant pour trouver S, le sommet de couverture:

    1. Trouver toutes les feuilles de l'arbre (BFS ou DFS), O(|V|) dans un arbre.
    2. Si (u,v) est une arête tels que v est une feuille, ajouter u pour le vertex cover et prune (u,v). Cela vous laisse avec une forêt T_1(V_1,E_1),...,T_n(U_n,V_n).
    3. Maintenant, si V_i={v}, ce qui signifie que |V_i|=1, alors que l'arbre peut être diminué depuis tous les bords de l'incident sur v sont couverts. Cela signifie que nous avons un licenciement condition pour que la récursivité, où nous avons soit un ou pas de sommets, et nous pouvons calculer S_i que la couverture pour chaque T_iet de définir S, ainsi que de tous les sommets à partir de l'étape 2 de l'union de la couverture de chaque T_i.

    Maintenant, il ne reste plus qu'à vérifier si l'arbre d'origine a un seul sommet, nous sommes de retour 1 et ne jamais démarrer la récursivité, et le peu de vertex cover peut être calculée.

    Edit:

    En fait, après y avoir réfléchi un peu, il peut être accompli avec un simple DFS variante.

  3. 11

    Je n'ai pas bien compris après avoir lu les réponses ici, donc je pensais que je poste un de ici

    L'idée générale est que vous la racine de l'arbre à l'arbitraire d'un nœud, et de vous demander si cette racine est dans le cache ou pas. Si c'est le cas, vous devez calculer le min vertex cover de la sous-arbres enracinés à ses enfants par recursing. Si elle ne l'est pas, ensuite, chaque enfant de la racine doit être dans le sommet de couverture, de sorte que chaque arête entre la racine et de ses enfants est couverte. Dans ce cas, vous recurse sur la racine de petits-enfants.

    Ainsi, par exemple, si vous aviez l'arbre suivant:

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

    Noter que, par l'inspection, vous savez le min vertex cover est {B, C}. Nous allons trouver ce min de couverture.

    Ici, nous commençons avec A.

    Un est dans le couvercle

    Nous déplacer vers le bas pour les deux sous-arbres de B et Cet de manière récursive sur cet algorithme. Nous ne pouvons pas nous contenter de dire qu' B et C ne sont pas dans le cache, parce que même si AB et AC sont couverts, nous ne pouvons rien dire quant à savoir si nous aurons besoin de B et C être dans le cache ou pas.

    (Penser à l'arbre suivant, où à la fois la racine et l'un de ses enfants sont dans le min de couverture ({A, D})

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

    )

    Un n'est pas dans le couvercle

    Mais nous savons que AB et AC doivent être couverts, alors nous devons ajouter B et C à la couverture. Depuis B et C sont dans la pochette, on peut répéter à leurs enfants au lieu de recursing sur B et C (même si nous, il ne nous donne pas plus d'informations).

    "Officiellement"

    Laisser C(x) être la taille de la min couvrir la racine x.

    Puis,

    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
            )
  4. 2
    { - 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)
  5. 2

    Nous pouvons utiliser un DFS en fonction de l'algorithme pour résoudre ce problème:

    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;
           }
        }
   }
}

    Le nœud feuille ne sera jamais sélectionné pour le vertex cover.

  6. 1

    Nous avons besoin de trouver le minimum vertex cover pour chaque nœud, nous avons à faire des choix, que ce soit pour l'inclure ou de ne pas l'inclure. Mais, selon le problème pour chaque arête (u, v), soit de " u "ou en" v " doit être dans le couvercle de sorte que nous devons prendre en charge que si le sommet n'est pas inclus nous nous devons de les inclure ses enfants, et si nous sommes, y compris les vertex ensuite, nous peut ou peut ne pas inclure ses enfants basé sur la solution optimale.

    Ici, DP1[v] pour tout sommet v = Lorsque nous l'indiquer.
    DP2[v] pour tout sommet v = quand on n'a pas l'inclure.

    DP1[v] = 1 + somme(min(DP2[c], DP1[c])) - ce sont également des moyens actuels et peut ou peut ne pas inclure ses enfants, basée sur ce qui est optimal.

    DP2[v] = sum(DP1[c]) - ce qui signifie pas de courants, alors nous avons besoin d'inclure les enfants de l'actuel sommet. Ici, c est l'enfant de vertex v.

    Ensuite, notre solution est min(DP1[racine], 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;
}
  7. 0

    Je voudrais simplement utiliser un programme linéaire pour résoudre le minimum vertex cover problème.
    Une formulation comme un programme linéaire en nombres entiers pourrait ressembler à celle donnée ici: Formulation ILP

    Je ne pense pas que votre propre mise en œuvre serait plus rapide que ces très optimisé LP solveurs.