Algorithmes de référence : Problèmes d'arbres
Définition et notations :
Un arbre est un graphe non-orienté connexe et sans cycle.
Une arborescence est un graphe orienté connexe et sans cycle (càd sa fermeture
symétrique n'a pas de circuit).
Dans une arborescence, le plus proche ancêtre commun (PA) de deux sommets x et
y est le sommet z ascendant de x et de y qui minimise la longueur des
chemins x~z et y~z.
Ce PAC existe et il est unique. Les chemins x~z et y~z
sont aussi uniques. PAC(x,y)=x si y est un descendant de x.
schéma algorithmique symPAC
Donnée : Une arborescence A=(V,E) de racine r.
Deux sommets x et y de V.
Résultat : le premier ancêtre commun z de x et y.
B← Dual(A);
Dans B, construire l'unique chemin x~r de x vers la racine r de A;
Dans B, construire l'unique chemin y~r de y vers la racine r de A;
PAC(x,y) est le premier sommet commun de x~r et y~r
(le plus éloigné de r donc).
Complexité linéaire dans la taille de A
(càd O(n), avec n=|V| et |E|=n-1).
Le calcul du dual est réalisé une seule fois pour la recherche de tous les
PAC, chaque recherche de PAC se faisant alors en temps linéaire dans ce
schéma algorithmique.
fonction CODER
Donnée : Une arborescence A=(V,E), un sommet x∈V,
une suite de bit P.
Résultat : un codage (C,K) des sommets de A.
Appel initial : CODER(A,racine de A,())
// k bis sont nécessaires pour coder x en fonction de son nombre de successeur;
K[x]← arrondi entier supérieur de lg(degré(x));
C[x]← P + (K[x] fois 0);
i←0;
Pour y∈Succ(x)
faire
i← i+1;
Q← P + (code binaire de i sur k bits);
CODER(A,y,Q).
Complexité : linéaire dans la taille de l'arbre ?
N.B. On considère que la taille d'un mot mémoire est d'au
moins lg(n) bits pour coder les sommets de l'arbre et donc le calcul de
K[x] et C[x] serait en O(1). S'il ne sont pas connus à l'avance, les degrés
des sommets peuvent être calculés préalablement en O(n) en triant en même
temps les sommets par degré croissant, sans complexité supplémentaire donc
si on utilise une structure de donnée adéquate ?...
Théorème : le codage (C,K) d'un sommet x fournit le codage de tous
les sommets sur le chemin de la racine vers x et fournit immédiatement le PAC
de deux sommets quelconque de l'arbre.
Preuve : à rédiger :-)
Question : après le calcul de ce codage, quelle est la complexité
pour trouver le PAC de deux sommets : O(n), O(lg(n)), O(1) ?
Peut-on faire mieux ?
schéma algorithmique EFFEUILLER
Donnée : Un arbre A=(V,E).
Résultat : un schéma d'effeuillage.
Tantque il reste une feuille dans A
faire
Choisir une feuille de A et la supprimer.
Preuve d'arrêt : Quelque soit l'ordre dans lequel on retire les
feuilles, on termine toujours par un arbre vide, car un arbre non-vide
possède au moins une feuille.
Complexité : O(n) ... si le choix d'une feuille et la mise à jour
de la table des degrés se fait en O(1) (voir la gestion de partitions
ordonnées).
Il n'est pas plus complexe de supprimer d'un coup à chaque étape toutes les
feuilles :
schéma algorithmique EPLUCHER
Donnée : Un arbre A=(V,E).
Résultat : un schéma d'effeuillage.
Tantque A n'est pas vide
faire
Supprimer toutes les feuilles de A.
N.B. Avant la dernière étape de l'effeuillage, il reste dans
l'arbre un sommet isolé ou bien deux sommets reliés qui constituent le centre
de l'arbre. Il peut donc y avoir deux manières de choisir une racine pour
transformer un arbre en arborescence de profondeur minimale.