Les Arbres en Théorie des Graphes

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Un arbre a sept définitions, et elles disent toutes la même chose

Demandez à trois personnes de définir un arbre et vous obtiendrez trois réponses. La première dit que c'est un graphe connexe sans cycle. La deuxième, que c'est un graphe avec exactement un chemin entre deux sommets quelconques. La troisième, que c'est un graphe connexe avec n - 1 arêtes. Les trois ont raison, tout comme quatre autres définitions, parce que ces conditions sont équivalentes : tout graphe qui en vérifie une les vérifie toutes.

C'est inhabituel, et c'est la raison pour laquelle les arbres sont le cas particulier le plus utile de la discipline. Une structure dotée de sept caractérisations équivalentes offre sept façons différentes de démontrer quelque chose à son sujet, et en pratique on choisit celle qui rend la démonstration la plus courte.

Partons de la définition standard, celle de Diestel et de Bondy et Murty :

Un arbre est un graphe connexe acyclique. Un graphe dont toutes les composantes sont des arbres est une forêt. Un sommet de degré 1 dans un arbre est une feuille.

Tout ce qui suit concerne un graphe fini, simpleet non orienté , ce qui est le cadre standard. De toute façon, un arbre ne peut avoir ni boucle ni arête parallèle, puisque l'une comme l'autre forme un cycle.

Écrit en entier, l'exemple récurrent est

V = {1, 2, 3, 4, 5, 6, 7, 8}
E = { {1,3}, {2,3}, {3,4}, {4,5}, {5,6}, {5,7}, {7,8} }

degrés    1:1   2:1   3:3   4:2   5:3   6:1   7:2   8:1
n = 8     m = 7 = n - 1      somme des degrés = 14 = 2m      feuilles : 1, 2, 6, 8

2. Le théorème d'équivalence et le fonctionnement de sa démonstration

Voici le résultat complet. Il figure pour l'essentiel sous cette forme chez West, chez Bondy et Murty et chez Diestel, et il vaut la peine de le retenir, car chaque ligne est un outil.

Théorème. Pour un graphe G à n sommets, les propositions suivantes sont équivalentes :
(1) G est un arbre, c'est-à-dire connexe et acyclique.
(2) Deux sommets quelconques de G sont reliés par exactement un chemin.
(3) G est connexe et possède n - 1 arêtes.
(4) G est acyclique et possède n - 1 arêtes.
(5) G est connexe, et la suppression de n'importe quelle arête le déconnecte (minimalement connexe).
(6) G est acyclique, et l'ajout de n'importe quelle arête crée un cycle (maximalement acyclique).
(7) G est connexe et chaque arête est un pont.

La démonstration n'est pas un argument unique mais un cycle d'implications, chacune brève. Il vaut la peine d'en voir la forme, car elle explique pourquoi les conditions semblent si différentes les unes des autres tout en décrivant le même objet.

Deux d'entre elles méritent d'être soulignées, car ce sont celles qu'on utilise vraiment.

« Connexe avec n - 1 arêtes » est le test le moins coûteux. Compter les arêtes coûte O(m) et vérifier la connexité coûte O(n + m), on peut donc décider en temps linéaire si un graphe est un arbre sans jamais chercher de cycle. Notez qu'aucune des deux moitiés ne suffit seule : un triangle plus un sommet isolé a 4 sommets et 3 arêtes mais n'est pas un arbre, pas plus qu'un 4-cycle, connexe avec 4 arêtes.

« Minimalement connexe » et « maximalement acyclique » sont le même objet vu sous deux angles. Un arbre se situe exactement sur la frontière : il a aussi peu d'arêtes que la connexité le permet et autant que l'acyclicité le permet. C'est pourquoi les arbres apparaissent dès qu'un problème demande la structure de connexion la moins coûteuse, ce qui est précisément le problème de l'arbre couvrant de poids minimum .

Les sept conditions sont vraies sur l'exemple récurrent, et chacune a été vérifiée directement : il est connexe, acyclique, a 7 arêtes pour 8 sommets, possède exactement un chemin entre chacune des 28 paires de sommets, chacune de ses 7 arêtes est un pont, et chacune des 21 arêtes absentes ferme un cycle quand on l'ajoute.

3. Le lemme des feuilles

Un petit résultat porte la plupart des démonstrations par récurrence de la discipline.

Lemme des feuilles. Tout arbre fini ayant au moins deux sommets possède au moins deux feuilles.

La démonstration est appréciée car elle n'utilise rien d'autre que la définition. Prenez un plus long chemin P dans l'arbre, disons de u à v. Un tel chemin existe car l'arbre est fini. Considérez maintenant u. Si u avait un voisin w hors de P, alors P pourrait être prolongé par cette arête, ce qui contredit sa maximalité. Si u avait un second voisin sur P, cela fermerait un cycle, ce qui contredit l'acyclicité. Donc u a exactement un voisin et est une feuille, et le même argument s'applique à v.

Deux conséquences en découlent aussitôt, et toutes deux servent constamment :

• Une récurrence sur les arbres a toujours un cas de base à retirer. Retirez une feuille d'un arbre et ce qui reste est un arbre avec un sommet de moins. Ce seul geste est le moteur de la démonstration qu'un arbre possède n - 1 arêtes, du codage de Prüfer de la section 7et de l'algorithme de recherche du centre de la section 10.
• La borne est optimale. Un chemin a exactement deux feuilles, donc « au moins deux » ne peut pas être amélioré en général. À l'autre extrême, l'étoile K1,n-1 possède n - 1 feuilles.

L'exemple récurrent a quatre feuilles, 1, 2, 6 et 8, confortablement plus que les deux garanties. Une vérification de bon sens utile pour déboguer du code sur les arbres : si votre structure prétend être un arbre et signale moins de deux feuilles, quelque chose cloche, et le coupable habituel est un cycle accidentel.

Le lemme est aussi exactement ce qui échoue sur les graphes infinis. Le chemin infini dans un seul sens a une seule feuille et le chemin infini dans les deux sens n'en a aucune, l'une des illustrations les plus nettes de ce qu'apporte la finitude, traitée dans le guide sur les graphes finis et infinis.

4. Les forêts, et compter les composantes gratuitement

Une forêt est un graphe acyclique, connexe ou non. Chaque composante d'une forêt est un arbre, ce qui donne une identité de comptage à connaître par cœur :

Une forêt à n sommets et k composantes possède exactement n - k arêtes.

La démonstration tient en une ligne : chaque composante est un arbre, donc une composante à ni sommets apporte ni - 1 arêtes, et la somme sur les k composantes donne n - k. En posant k = 1 , on retrouve le cas de l'arbre.

Lue à l'envers, l'identité devient un outil plutôt qu'un fait :

k = n - m        le nombre de composantes d'une forêt,
                 calculé à partir de sa seule taille, sans aucun parcours

C'est réellement utile. Si vous savez qu'un graphe est acyclique, compter ses sommets et ses arêtes vous dit en combien de morceaux il se trouve, sans lancer de recherche. C'est aussi l'identité derrière l'invariant standard de la structure union-find : chaque union réussie fusionne deux composantes et ajoute une arête, donc le compteur courant n - (unions effectuées) est à tout instant le nombre de composantes.

Une mise en garde. L'identité suppose l'acyclicité. Pour un graphe quelconque, on a toujours m ≥ n - k , avec égalité exactement lorsque le graphe est une forêt, donc un graphe ayant plus de n - k arêtes contient nécessairement un cycle. Cette inégalité est le moyen le plus rapide de prouver qu'un graphe a un cycle sans le trouver : si m ≥ n, il y a un cycle quelque part.

5. Les arbres couvrants

Un arbre couvrant d'un graphe connexe G est un sous-graphe qui est un arbre et contient tous les sommets de G. C'est le squelette minimal qui maintient le graphe d'un seul tenant.

Tout graphe fini connexe en possède un, et la démonstration constructive mérite d'être connue car c'est aussi un algorithme : tant qu'un cycle existe, supprimez l'une de ses arêtes. Supprimer une arête d'un cycle ne peut pas déconnecter le graphe, puisque le reste du cycle relie toujours ses extrémités, et le procédé s'arrête car chaque étape retire une arête. Ce qui reste est connexe et acyclique. De façon équivalente, et plus pratique, l'arbre des arêtes de découverte produit par tout parcours BFS ou DFS est déjà un arbre couvrant, obtenu en O(n + m).

Trois faits sur les arbres couvrants qui reviennent sans cesse :

• Tout arbre couvrant possède exactement n - 1 arêtes, quelle que soit l'allure du graphe. Sur un graphe non pondéré, tous les arbres couvrants se valent donc, et le problème de l'arbre couvrant de poids minimum ne devient intéressant que lorsque les arêtes portent des poids.
• Le nombre d'arbres couvrants peut être énorme. Le graphe complet Kn en possède nn-2 , ce qui est à nouveau la formule de Cayley , vue du côté des arbres couvrants.
• Un arbre est son propre et unique arbre couvrant. Évident une fois énoncé, et un cas dégénéré utile pour tester du code : tout compteur d'arbres couvrants doit renvoyer exactement 1 sur un arbre, ce que confirme pour l'exemple récurrent le calcul matrice-arbre de la section 8 .

Pour les graphes infinis, l'énoncé « tout graphe connexe possède un arbre couvrant » reste vrai, mais il nécessite l'axiome du choix, auquel il est d'ailleurs équivalent. Cette frontière est discutée dans le guide sur les graphes finis et infinis .

6. Compter les arbres étiquetés : la formule de Cayley

Combien d'arbres différents peut-on construire sur un ensemble fixé de n sommets étiquetés ? La réponse est l'un des résultats les plus cités de la combinatoire, publié par Arthur Cayley en 1889.

Formule de Cayley. Le nombre d'arbres étiquetés à n sommets est nn-2.

Les premières valeurs croissent vite, et il vaut la peine de les voir car les plus petites se vérifient à la main :

Les valeurs pour n = 4 et n = 5 ci-dessus ne sont pas tirées d'un livre ; elles ont été obtenues en énumérant tous les sous-ensembles de n - 1 arêtes parmi les C(n, 2) candidates et en gardant les connexes, ce qui donne exactement 16 et 125.

Un mot sur le sens de « étiqueté », car la distinction est tout l'objet de la section 9. Cayley compte les arbres dont les sommets sont distinguables, donc le chemin 1 - 2 - 3 et le chemin 2 - 1 - 3 sont des arbres différents bien qu'ils aient la même forme. Retirez les étiquettes et il n'existe qu'une seule forme d'arbre à trois sommets.

Il existe plusieurs démonstrations de la formule, dont un argument de double comptage sur les forêts enracinées et un argument par déterminant via le théorème matrice-arbre. La plus éclairante est une bijection, et elle est assez courte pour être déroulée entièrement.

7. La bijection de Prüfer, déroulée de bout en bout

Heinz Prüfer a donné en 1918 une démonstration de la formule de Cayley en construisant une bijection explicite entre les arbres étiquetés à n sommets et les suites de longueur n - 2 à valeurs dans {1, …, n}. Comme il existe exactement nn-2 telles suites, la formule en découle immédiatement.

Codage. Tant qu'il reste plus de deux sommets, trouvez la feuille de plus petite étiquette, notez l'étiquette de son unique voisin et supprimez la feuille. Arrêtez-vous quand il reste deux sommets. Sur l'exemple récurrent, cela donne, étape par étape :

retirer la feuille 1  →  noter 3      restants : 2,3,4,5,6,7,8
retirer la feuille 2  →  noter 3      restants : 3,4,5,6,7,8
retirer la feuille 3  →  noter 4      restants : 4,5,6,7,8
retirer la feuille 4  →  noter 5      restants : 5,6,7,8
retirer la feuille 6  →  noter 5      restants : 5,7,8
retirer la feuille 5  →  noter 7      restants : 7,8

suite de Prüfer :  (3, 3, 4, 5, 5, 7)        longueur 6 = n - 2

Décodage. L'inverse applique la même idée à rebours. Donnez à chaque sommet un compteur égal à un plus son nombre d'apparitions dans la suite, ce qui sera son degré. Prenez ensuite à répétition le plus petit sommet non encore utilisé dont le compteur vaut 1, reliez-le à la première entrée restante de la suite et décrémentez les deux compteurs. Quand la suite est épuisée, reliez les deux sommets dont le compteur vaut encore 1. Appliqué à (3, 3, 4, 5, 5, 7) , ce procédé redonne exactement l'ensemble d'arêtes d'origine, et c'est ce qui fait de la correspondance une bijection et non un simple résumé.

La propriété la plus utile du codage est la suivante :

Le sommet v apparaît dans la suite de Prüfer exactement deg(v) - 1 fois. En particulier, les feuilles sont précisément les étiquettes qui n'apparaissent jamais.

Vérifiez-le sur l'exemple récurrent. Le sommet 3 est de degré 3 et apparaît deux fois ; le sommet 5 est de degré 3 et apparaît deux fois ; les sommets 4 et 7 sont de degré 2 et apparaissent une fois chacun ; et les feuilles 1, 2, 6 et 8 n'apparaissent pas du tout. Cette correspondance transforme les questions sur les suites de degrés en questions sur la fréquence des symboles dans une chaîne, et c'est pourquoi les suites de Prüfer sont l'outil standard pour compter les arbres à degrés prescrits et pour tirer un arbre étiqueté uniformément au hasard : générez une suite aléatoire de longueur n - 2 et décodez-la.

8. Le théorème matrice-arbre

La formule de Cayley compte les arbres couvrants du graphe complet. Le théorème matrice-arbre de Kirchhoff, antérieur de quatre décennies et issu de ses travaux sur les réseaux électriques en 1847, compte les arbres couvrants de n'importe quel graphe.

Construisez la matrice laplacienne du graphe L = D - A, où D est la matrice diagonale des degrés et A la matrice d'adjacence. Alors :

Théorème matrice-arbre. Supprimez une ligne quelconque et la colonne correspondante de L. Le déterminant de la matrice (n-1) × (n-1) restante est le nombre d'arbres couvrants du graphe. Le choix de la ligne et de la colonne supprimées n'a aucune importance.

Trois calculs rendent le théorème concret, et tous trois ont été effectués plutôt que cités :

Le cas du cycle est celui à garder comme intuition : un cycle à k sommets possède exactement k arbres couvrants, un pour chaque arête que l'on choisit de retirer. Le théorème explique aussi une remarque du guide sur les multigraphes : les arêtes parallèles changent réellement le nombre d'arbres couvrants, car elles entrent dans le laplacien comme multiplicités hors diagonale, si bien que deux sommets reliés par deux arêtes parallèles ont deux arbres couvrants au lieu d'un.

9. Les arbres non étiquetés : une question bien plus difficile

La formule de Cayley est nette parce que les étiquettes rendent les arbres faciles à distinguer. Demandez plutôt combien d'arbres il existe à isomorphisme près, c'est-à-dire combien de formes distinctes existent, et le problème devient réellement difficile.

Les deux colonnes racontent des histoires complètement différentes. Le nombre étiqueté a une forme close d'une ligne ; le nombre non étiqueté n'en a aucune. On ne connaît aucune formule pour le nombre d'arbres à n sommets à isomorphisme près, seulement un traitement par séries génératrices et un résultat asymptotique dû à Richard Otter en 1948, qui montre que ce nombre croît comme C · αn n-5/2 pour des constantes calculées numériquement.

La raison de cet écart est la symétrie. Diviser le nombre étiqueté par n! ne serait correct que si chaque arbre avait un groupe d'automorphismes trivial, et la plupart n'en ont pas : un chemin peut être retourné, les feuilles d'une étoile peuvent être permutées arbitrairement, et chaque symétrie fait que plusieurs étiquetages se confondent en une même forme. Compter les orbites sous le groupe symétrique est précisément la partie difficile, et c'est pourquoi le problème exige la machinerie d'énumération de Pólya plutôt qu'une formule.

Pour qui programme, la forme pratique de cette distinction est le test d'isomorphisme d'arbres : décider si deux arbres ont la même forme. Contrairement à l'isomorphisme de graphes en général, cela se résout en temps linéaire, en hachant canoniquement chaque sous-arbre de bas en haut à partir des feuilles et en comparant les résultats au centre. Que le problème général soit difficile alors que le cas des arbres est facile est une illustration de plus du motif qui traverse tout cet article.

10. Centre, rayon et diamètre

On appelle excentricité d'un sommet sa plus grande distance à tout autre sommet. Le rayon est la plus petite excentricité du graphe, le diamètre la plus grande, et le centre est l'ensemble des sommets qui atteignent le rayon. Pour les arbres, ces notions se comportent de façon remarquablement nette, comme l'a établi Camille Jordan en 1869.

Théorème de Jordan. Le centre d'un arbre est formé soit d'un sommet, soit de deux sommets adjacents.

Jamais trois, jamais deux sommets non adjacents. Comparez avec un cycle, où tous les sommets sont au centre, et la netteté du cas des arbres apparaît clairement.

La démonstration fait aussi office d'algorithme. Supprimez à répétition toutes les feuilles courantes simultanément. Chaque tour diminue de exactement 1 l'excentricité de chaque sommet restant, il préserve donc les sommets minimaux, et le procédé s'arrête avec un ou deux sommets. Sur l'exemple récurrent :

départ                   1 2 3 4 5 6 7 8
retirer les feuilles 1, 2, 6, 8   →   restants  3 4 5 7
retirer les feuilles 3, 7         →   restants  4 5      ← le centre

excentricités   1:5  2:5  3:4  4:3  5:3  6:4  7:4  8:5
rayon 3     diamètre 5     centre {4, 5}, adjacents comme l'exige Jordan

Le résultat de l'effeuillage a été confronté à un calcul direct des huit excentricités, et les deux concordent exactement : les sommets d'excentricité minimale sont précisément 4 et 5. L'algorithme s'exécute en O(n), c'est pourquoi il est la manière standard d'enraciner un arbre « au milieu », par exemple avant le hachage canonique d'un test d'isomorphisme.

Une identité supplémentaire est vraie dans les arbres et mérite d'être retenue :

rayon = ⌈diamètre / 2⌉        ici : 3 = ⌈5 / 2⌉

Elle découle du fait que le diamètre d'un arbre est réalisé par un chemin unique, et que le centre se trouve au milieu de ce chemin. Dans un graphe quelconque, seule l'inégalité plus faible radius ≤ diameter ≤ 2 · radius est vraie.

11. Les distances dans les arbres et l'astuce du double BFS

Comme il existe exactement un chemin entre deux sommets quelconques, la distance dans un arbre est plus simple que dans toute autre classe de graphes. Il n'y a rien à optimiser : l'unique chemin est le plus court chemin, donc ni poids, ni file de priorité, ni Dijkstra ne sont nécessaires pour le trouver.

Cette unicité donne un algorithme élégant et très utilisé pour le diamètre :

Double BFS. Lancez un parcours en largeur depuis un sommet quelconque et soit a un sommet le plus éloigné trouvé. Lancez un second parcours depuis a et soit b un sommet le plus éloigné de celui-ci. Alors le chemin de a à b est un diamètre, et dist(a, b) est la longueur du diamètre.

Deux passes linéaires, pas de poids, pas d'astuce. Sur l'exemple récurrent, en partant du sommet 1, le parcours atteint le sommet 8 comme sommet le plus éloigné, et un second parcours depuis 8 renvoie le sommet 1 à distance 5, ce qui correspond au vrai diamètre calculé comme le maximum de toutes les excentricités.

La raison pour laquelle cela marche mérite d'être énoncée, car l'astuce échoue sur les graphes quelconques et on la transpose pourtant. L'affirmation clé est qu'un sommet le plus éloigné depuis n'importe quel point de départ est toujours une extrémité d'un diamètre. Dans un arbre, c'est vrai parce que les chemins uniques forcent le sommet le plus éloigné à se trouver au bout du plus long chemin ; dans un graphe avec cycles, l'affirmation est tout simplement fausse, et la méthode en deux passes peut sous-estimer. Sur un graphe quelconque, calculer le diamètre exige les distances entre toutes les paires.

D'autres faits sur les distances qui sont vrais dans les arbres et, en général, nulle part ailleurs :

• Supprimer n'importe quelle arête coupe l'arbre en exactement deux composantes, puisque chaque arête est un pont. C'est ce qui fait fonctionner si proprement le diviser pour régner sur les arbres, comme la décomposition par centroïdes.
• Le chemin entre deux sommets se reconstruit à partir des seuls pointeurs vers le parent une fois l'arbre enraciné, en un temps proportionnel à la longueur du chemin, ce qui sous-tend les techniques du plus petit ancêtre commun.
• Les distances vérifient la condition des quatre points, une identité métrique qui caractérise exactement les matrices de distances issues d'arbres, et qui fonde la reconstruction d'arbres phylogénétiques à partir de données de distance génétique.

12. Arbres libres, enracinés et ordonnés

Tout ce qui précède portait sur les arbres libres : des graphes connexes acycliques sans sommet distingué et sans ordre entre les voisins d'un sommet. L'informatique travaille presque toujours avec quelque chose de plus structuré, et l'ouvrage de Knuth, The Art of Computer Programming , distingue soigneusement les trois niveaux, car les dénombrements diffèrent à chacun d'eux.

Enraciner ne modifie pas le graphe, cela modifie la question. L'ensemble d'arêtes sous-jacent est identique ; ce qu'apporte une racine, c'est une orientation, et avec elle tout le vocabulaire de parent, enfant, ancêtre, descendant, profondeur et hauteur, que le guide complémentaire sur les arbres enracinés traite en détail avec les parcours standard.

La différence de dénombrement est la façon la plus nette de voir qu'il s'agit vraiment d'objets différents. Les arbres binaires ordonnés à n nœuds sont comptés par les nombres de Catalan, qui donnent 1, 1, 2, 5, 14, 42 pour n = 0 à 5, alors que les arbres libres ayant le même nombre de sommets sont bien moins nombreux. Chaque élément de structure supplémentaire que l'on impose multiplie le nombre d'objets distincts.

Une remarque pratique qui découle de la section 10 : quand un algorithme a besoin d'une racine et qu'aucune n'est fournie, enraciner au centre est généralement le bon choix par défaut. Cela minimise la hauteur, qui borne la profondeur de toute récursion exécutée sur l'arbre.

13. Où les arbres apparaissent en informatique

Les arbres sont la structure la plus courante en informatique qui soit réellement un graphe, et il vaut la peine de distinguer les cas où l'arbre constitue les données de ceux où il est un certificat produit par un algorithme.

Les arbres comme données. La hiérarchie est l'essentiel :

• Systèmes de fichiers. Les répertoires et les fichiers forment un arbre enraciné, du moins tant que les liens symboliques et les liens physiques ne sont pas autorisés ; à ce moment-là, il devient un graphe quelconque et la garantie d'un chemin unique disparaît. C'est exactement pourquoi les boucles de liens font planter les parcours naïfs de répertoires.
• Arbres d'analyse et arbres syntaxiques abstraits. Tout frontal de compilateur en produit un. Être un arbre est ce qui rend l'évaluation récursive bien fondée : une sous-expression ne peut pas se contenir elle-même.
• Le DOM. Un document HTML est un arbre enraciné ordonné, et les sélecteurs CSS sont des requêtes sur les relations d'ancêtre et de frère en son sein.
• Arbres de recherche, tries et tas. Les arbres binaires de recherche, les arbres B et les tries sont des arbres dont la forme est contrainte pour borner la profondeur, qui est exactement la hauteur de l'arbre enraciné.
• Arbres de décision. Chaque nœud interne teste une caractéristique et chaque feuille porte une prédiction ; l'unique chemin de la racine à la feuille est l'explication de la sortie du modèle.

Les arbres comme certificats. Ici, l'arbre est la sortie d'un algorithme et encode une preuve :

• Arbres BFS et DFS. Tout parcours d'un graphe connexe produit un arbre couvrant d'arêtes de découverte. L'arbre BFS certifie en outre les plus courtes distances dans un graphe non pondéré, et les arêtes de retour de l'arbre DFS sont ce qui permet de détecter les cycles et de trouver les ponts.
• Arbres de plus courts chemins. L'algorithme de Dijkstra en produit un : un arbre couvrant dans lequel le chemin de la source à tout sommet est un plus court chemin. Notez qu'il n'est en général pas un arbre couvrant de poids minimum, et confondre les deux est une erreur classique.
• Arbres couvrants de poids minimum. Kruskal, Prim et Borůvka certifient chacun le sous-graphe de connexion le moins coûteux, traité dans le guide des MST.
• Forêts union-find. La structure d'ensembles disjoints est littéralement une forêt, et la compression de chemin est une opération qui aplatit ses arbres pour maintenir une hauteur quasi constante.
• Arbres de Merkle. Les arbres de hachage des systèmes de gestion de versions et des systèmes distribués exploitent la propriété du chemin unique pour qu'une modification d'une seule feuille se propage le long d'exactement un chemin jusqu'à la racine, ce qui rend la vérification logarithmique.

Une précision s'impose, car la terminologie induit en erreur : l'historique des commits Git n'est pas un arbre. Un commit de fusion a deux parents, donc l'historique est un graphe orienté acyclique. Les objets « tree » de Git sont tout autre chose, à savoir les instantanés de répertoires. La différence entre un DAG et un arbre est précisément qu'un arbre possède un chemin unique entre deux nœuds quelconques, et une fusion détruit cela.

14. Erreurs courantes

• Ne vérifier qu'une moitié de la définition. « Connexe » seul admet des cycles ; « n - 1 arêtes » seul admet un triangle plus un sommet isolé. Il vous faut une paire de conditions du théorème de la section 2, et connexe plus n - 1 arêtes est la moins coûteuse.
• Supposer qu'un arbre de plus courts chemins est un arbre couvrant de poids minimum. Ils optimisent des choses différentes : l'un minimise chaque distance depuis la source, l'autre minimise le poids total des arêtes. Ils diffèrent fréquemment.
• Utiliser l'astuce du double BFS pour le diamètre sur un graphe avec cycles. Elle n'est valable que sur les arbres, où la propriété du chemin unique fait d'un sommet le plus éloigné une extrémité de diamètre. Sur les graphes quelconques, elle peut sous-estimer sans le signaler.
• Confondre dénombrements étiquetés et non étiquetés. Il existe 125 arbres étiquetés à 5 sommets et seulement 3 formes. Diviser par n! ne permet pas de passer de l'un à l'autre, car les arbres ont des symétries.
• Oublier qu'enraciner ne change rien structurellement. Une racine ajoute une question, pas une arête. L'arbre libre sous-jacent est inchangé, donc tout fait structurel démontré pour les arbres libres reste valable.
• S'attendre au lemme des feuilles sur les arbres infinis. Le chemin infini dans les deux sens est acyclique et connexe, sans aucune feuille.
• Traiter un DAG comme un arbre. Un DAG peut avoir plusieurs chemins entre deux nœuds ; un arbre, non. Tout algorithme qui repose sur l'unicité des chemins, y compris une mémoïsation naïve indexée par nœud, se comportera mal.
• Construire un « arbre » qui contient un cycle. La vérification la plus rapide à l'exécution est le nombre d'arêtes : si un prétendu arbre à n sommets n'a pas exactement n - 1 arêtes, arrêtez-vous et cherchez le bug.

15. Glossaire

17. Références

Sources des définitions, théorèmes et attributions ci-dessus, avec les ouvrages de référence où ce matériel est développé, classées par ordre chronologique.

1. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 à 508. Le théorème matrice-arbre.
2. Jordan, C. (1869). "Sur les assemblages de lignes." Journal für die reine und angewandte Mathematik 70, 185 à 190. Le centre d'un arbre est un sommet ou deux sommets adjacents.
3. Cayley, A. (1889). "A Theorem on Trees." Quarterly Journal of Pure and Applied Mathematics 23, 376 à 378.
4. Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen." Archiv der Mathematik und Physik 27, 142 à 144. La bijection de la section 7.
5. Borůvka, O. (1926). "O jistém problému minimálním." Práce Moravské Přírodovědecké Společnosti 3, 37 à 58.
6. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig : Akademische Verlagsgesellschaft.
7. Otter, R. (1948). "The Number of Trees." Annals of Mathematics 49(3), 583 à 599. Asymptotique des arbres non étiquetés.
8. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1), 48 à 50.
9. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6), 1389 à 1401.
10. Harary, F. (1969). Graph Theory. Reading, Massachusetts : Addison-Wesley.
11. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3e édition, section 2.3. Reading, Massachusetts : Addison-Wesley. La distinction entre arbres libres, enracinés et ordonnés.
12. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River : Prentice Hall. Le chapitre 2 développe les arbres et les distances.
13. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition. Cambridge, Massachusetts : MIT Press.
15. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. La section 1.5 traite des arbres et des forêts.