algorithme pour trouver max ensemble indépendant dans un arbre

J'ai besoin d'un algorithme pour trouver max indépendant situé dans un arbre. Je pense commencer à partir de tous les nœuds feuilles, puis supprimer le parent direct nœuds de ces nœuds feuilles, puis choisissez les nœuds parents de nœuds parents, nous avons supprimé, répétez cette procédure de manière récursive jusqu'à ce que nous obtenir à la racine. et est de ce fait en O(n) le temps? la réponse est apprécié. merci.

Et quelqu'un pourrait-il svp m'indiquer un algorithme pour trouver le max dominant ensemble dans un arbre.

source d'informationauteur starcaller

  1. 15

    MAXIMUM INDÉPENDANT

    Vous pouvez calculer le maximum d'ensemble indépendant par un parcours en profondeur d'abord rechercher dans l'arbre.

    La recherche permettra de calculer deux valeurs pour chaque sous-arbre dans le graphe:

    1. A(i) = La taille maximale indépendant situé dans le sous-arbre enraciné en moi avec la contrainte d'un noeud i doit être inclus dans l'ensemble.
    2. B(i) = La taille maximale indépendant situé dans le sous-arbre enraciné en moi avec la restriction que le nœud i ne doivent PAS être inclus dans l'ensemble.

    Elles peuvent être calculées de manière récursive par l'examen de deux cas:

    1. La racine du sous-arbre n'est pas inclus.

      B(i) = sum(max(A(j),B(j)) pour j chez les enfants(i))

    2. La racine du sous-arbre est inclus.

      A(i) = 1 + somme(B(j) pour j chez les enfants(i))

    La taille maximale de réglage indépendantes dans l'ensemble de l'arbre est max ((racine),B(racine)).

    MAXIMALE DOMINANT ENSEMBLE

    Selon la définition de domination mis en wikipedia le maximum dominant est toujours trivialement égal à dont chaque nœud dans le graphe - mais ce n'est probablement pas ce que tu veux dire?

  2. 0

    • Pour trouver l'ensemble indépendant maximal de sommets, nous pouvons utiliser une propriété importante d'un arbre: Chaque arbre est Bipartite, c'est à dire On peut changer la couleur de sommets d'un arbre à l'aide de seulement deux couleurs tel que deux sommets adjacents de la même couleur.

    • Faire un DFS de la traversée et de commencer à colorier les sommets de NOIR et de BLANC.

    • Choisir l'ensemble de sommets (NOIR ou BLANC), qui sont plus nombreuses. Cela vous donnera le maximum indépendants ensemble de sommets d'un arbre.

    Une certaine Intuition derrière le pourquoi de cet algorithme fonctionne:

    • Laissez-nous d'abord revoir la définition de l'ensemble indépendant maximal de sommets. Nous devons en choisir qu'un seul point de fin d'un bord et nous avons à couvrir chaque arête de l'arbre satisfaisant cette propriété. Nous ne sommes pas autorisés à choisir les deux points d'extrémité d'une arête.

    • Maintenant, ce n'bicoloring d'un graphe? Il divise tout simplement l'ensemble de sommets en deux sous-ensembles (BLANC et NOIR) et BLANC de couleur sommets sont directement reliés aux NOIRS. Ainsi, si nous choisissons soit tout BLANC ou tout NOIR, il nous est intrinsèquement le choix d'un ensemble de sommets. Donc à choisir maximale indépendant
      ensemble, aller pour le sous-ensemble dont la taille est plus grande.