Algorithme d'étiquetage temporel linéaire pour un arbre?

J'ai un arbre non orienté dont je veux étiqueter les sommets. Les nœuds foliaires doivent être étiquetés un. Supposez ensuite que les feuilles ont été retirées. Dans l'arbre qui reste, les feuilles doivent être étiquetées deux. Ce processus se poursuit de manière évidente jusqu'à ce que tous les sommets aient une étiquette. La raison pour laquelle je fais cela est que je veux stocker les sommets dans une file d'attente et les parcourir "laisse d'abord". Existe-t-il un moyen facile de faire ce temps ? $O(n+m)$

Je peux résoudre le problème en faisant un BFS à chaque étape. Mais dans le pire des cas, à chaque étape, je passe par chaque sommet, j'enlève exactement deux feuilles et je les mets en file d'attente. Je crois que cela prend du temps quadratique.

Une autre idée était de trouver d'abord toutes les feuilles, puis de faire un BFS à partir de chaque feuille. Cela ne me donne pas la solution souhaitée. Par exemple, considérez une sorte de "graphique de couronne" comme dans la figure ci-dessous. La solution souhaitée est indiquée, mais le lancement d'un BFS à partir de chaque feuille entraînerait l'utilisation de seulement deux étiquettes.

entrez la description de l'image ici

Idéalement, l'algorithme de temps linéaire serait également facile à expliquer et à mettre en œuvre.

algorithms trees Bob Whiz
la source

Réponses:

Arbres non racinés

Vous pouvez utiliser une file d'attente prioritaire pour résoudre ce problème dans : $O(E+V\log V)$

Mettez tous les sommets dans une file d'attente prioritaire, leur priorité étant leur degré.
Alors que la file d'attente n'est pas vide:
- Supprimez un sommet de priorité minimale, qui doit être (ou à la toute fin). $v$ $1$ $0$
- Soit , où passe en revue tous les voisins d' origine de . $\sigma(v) = 1 + \max \sigma(u)$ $u$ $v$
- Soustrayez de la priorité de l'unique voisin restant de (le cas échéant). $1$ $u$

En fait, nous n'avons pas vraiment besoin d'une file d'attente prioritaire, et cet algorithme peut être implémenté en utilisant une simple file d'attente dans le temps : $O(E+V)$

Initialisez un tableau de longueur avec les degrés de tous les sommets. $V$
Initialisez un autre tableau de longueur avec "vivant". $V$
Parcourez une fois le premier tableau et placez tous les sommets de degré dans une file d'attente. $1$
Alors que la file d'attente n'est pas vide:
- Pop un sommet . $v$
- Soit , où passe en revue tous les voisins d'origine de . $\sigma(v) = 1 + \max \sigma(u)$ $u$ $v$
- Marquez comme "mort". $v$
- Si a un voisin "vivant" , soustrayez du degré de . $v$ $u$ $1$ $u$
- Si le nouveau degré de est , poussez dans la file d'attente. $u$ $1$ $u$

Arbres enracinés

Utilisez plutôt DFS. Voici un croquis de l'algorithme.

Étant donné un nœud , si est une feuille, définissez . $v$ $v$ $d(v) = 1$
Si n'est pas une feuille, exécutez l'algorithme sur tous ses enfants, puis laissez , où passe en revue l'ensemble de tous les enfants. $v$ $d(v) = 1 + \max d(u)$ $u$

Vous exécutez cet algorithme à la racine.

Yuval Filmus
la source

Est-ce correct? Considérez l'arbre 1-> 2-> 3-> 4-> 5, où 1 est la racine. 2 devrait obtenir l'étiquette 1, mais vous donnez 3? Ou par enfants, vous parlez de voisins? À partir de quel nœud commençons-nous le DFS?

Knoothe

Mon implémentation est "off by one", mais selon votre description, devrait obtenir le label , car vous devez supprimer , puis , puis , et c'est seulement à ce moment-là que devient une feuille.

2

$2$

4

$4$

5

$5$

4

$4$

3

$3$

2

$2$

Yuval Filmus

Je n'ai pas posé la question :-). J'ai interprété la question comme: un arbre non dirigé. Étiquetez toutes les feuilles. Supprime-les. Recurse sur l'arbre résultant. Dans ce cas, l'arborescence est en fait 1-2-3-4-5, étape 1, vous supprimez 1 et 5, puis 2 et 4, puis 3. Voir le paragraphe sur le "graphique de la couronne". C'est l'un des algorithmes classiques pour trouver le centre d'un arbre.

Knoothe

1 n'est pas une feuille. C'est très loin d'être une feuille, c'est la racine. J'ai interprété la question comme ciblant les arbres enracinés. Nous devrions peut-être attendre que le PO réponde.

Yuval Filmus

@YuvalFilmus, juste pour jeter mes 2 cents, ne devrait-il pas être ? Les feuilles sont égales à , si vous les supprimez, les nouvelles feuilles doivent être égales à , c'est donc une sorte de mesure du nombre de couches que vous devez supprimer avant que le sommet ne devienne une feuille. Avec min, tout sommet adjacent à une feuille obtient 2, mais il peut ne pas devenir une feuille lorsque les feuilles sont supprimées. Cette phrase contenait trop de feuilles. J'ai besoin d'un balai.

1 + m a x {d (u)}

$1+max\{d(u)\}$

1

$1$

2

$2$

Luke Mathieson

Une réponse simple est la suivante:

Transformez cela en un graphique dirigé, où nous avons une arête de chaque nœud à son parent . Notez que vous obtenez un dag (graphique acyclique dirigé). $(u,v)$ $u$ $v$
Tri topologique du graphique.
Scannez les sommets, dans l'ordre trié. Étiquetez chaque sommet avec une de plus que la plus grande des étiquettes de ses prédécesseurs. Puisque nous numérisons dans l'ordre topologique, tous les prédécesseurs de auront déjà reçu une étiquette avant d'essayer d'étiqueter . $v$ $v$

Chacune de ces étapes peut être effectuée en temps , de sorte que le temps de fonctionnement total est . Je ne mentionne cette approche alternative que si vous la trouvez conceptuellement plus facile à comprendre que la réponse de Yuval. $O(n+m)$ $O(n+m)$

DW
la source