Quel est un bon algorithme pour obtenir la couverture minimale des sommets d'un arbre ?

Question

Quel est un bon algorithme pour obtenir la couverture minimale des sommets d'un arbre ?

INPUT :

Les voisins du nœud.

SORTIE :

Le nombre minimum de sommets.

Answer 1

Je n'ai pas tout compris après avoir lu les réponses ici, alors j'ai pensé en poster une à partir de aquí

L'idée générale est que l'on Root l'arbre à un nœud arbitraire, et que l'on demande si ce Root est dans la couverture ou non. Si c'est le cas, on calcule alors la couverture minimale des sous-arbres enracinés à ses enfants par récurrence. S'il ne l'est pas, alors chaque enfant de la racine doit être dans la couverture des sommets de sorte que chaque arête entre la racine et ses enfants soit couverte. Dans ce cas, on récure sur les petits-enfants de la racine.

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

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

Notez que par inspection, vous savez que la couverture de sommet min est {B, C} . Nous allons trouver cette couverture min.

Ici, nous commençons par A .

A est dans la couverture

Nous nous déplaçons vers les deux sous-arbres de B y C et de récursion sur cet algorithme. Nous ne pouvons pas simplement affirmer que B y C ne sont pas dans la couverture, car même si AB y AC sont couvertes, nous ne pouvons pas dire si nous aurons besoin de B y C d'être dans la couverture ou pas.

(Pensez à l'arbre suivant, où la racine et l'un de ses enfants se trouvent tous deux dans la couverture minimale ( {A, D} )

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

)

A n'est pas dans la couverture

Mais nous savons que AB y AC doivent être couverts, nous devons donc ajouter B y C à la couverture. Depuis B y C sont dans la couverture, nous pouvons récurrer sur leurs enfants au lieu de récurrer sur B y C (même si nous le faisions, cela ne nous donnerait pas plus d'informations).

"Officiellement"

Soit C(x) soit la taille de la couverture min ayant pour racine x .

Ensuite,

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) est un arbre, ce qui implique que pour toute feuille, toute couverture minimale de sommets doit inclure soit la feuille, soit le sommet adjacent à la feuille. Cela nous donne l'algorithme suivant pour trouver S, la couverture de sommets :

1. Trouver toutes les feuilles de l'arbre (BFS ou DFS), O(|V|) dans un arbre.
2. Si (u,v) est une arête telle que v est une feuille, ajouter u à la couverture de sommets et élaguer (u,v). Vous obtenez ainsi une forêt T_1(V_1,E_1),...,T_n(U_n,V_n).
3. Maintenant, si V_i={v}, c'est-à-dire |V_i|=1, alors cet arbre peut être abandonné puisque tous les bords incidents sur v sont couverts. Cela signifie que nous avons une condition de terminaison pour une récursion, où nous avons soit un ou aucun sommet, et nous pouvons calculer S_i comme couverture pour chaque T_i et définissez S comme étant tous les sommets de l'étape 2, l'union de la couverture de chaque T_i .

Maintenant, il ne reste plus qu'à vérifier que si l'arbre original n'a qu'un seul sommet, on retourne 1 et on ne commence jamais la récursion, et la couverture minimale des sommets peut être calculée.

Editar:

En fait, après y avoir réfléchi un peu, cela peut être réalisé avec une simple variante de DFS.

Answer 3

J'espère aquí vous pouvez trouver des réponses plus pertinentes à votre question.

---

J'ai réfléchi à ma solution, vous devrez probablement la peaufiner mais tant que la programmation dynamique est dans l'une de vos balises, vous en aurez probablement besoin :

1. Pour chaque sommet u, définir S+(u) est la taille de la couverture avec le sommet u et S-(u) la couverture sans le sommet u.
2. S+(u)= 1 + Somme(S-(v)) pour chaque enfant v de u.
3. S-(u)=Somme(max{S-(v),S+(v)}) pour chaque enfant v de u.
4. La réponse est max(S+(r), S-(r)) où r est la racine de votre arbre.

---

Après avoir lu este . J'ai modifié l'algorithme ci-dessus pour qu'il trouve l'ensemble indépendant maximum, puisque l'article de wiki indique que

Un ensemble est indépendant si et seulement si son complément est une couverture de sommets.

Ainsi, en remplaçant min par max, nous pouvons trouver l'ensemble indépendant maximal et, par complément, la couverture de sommets minimale, puisque les deux problèmes sont équivalents.

Answer 4

{- 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 5

Nous pouvons utiliser un algorithme basé sur DFS 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 la couverture des sommets.