Arbre (théorie des graphes)

En théorie des graphes , un arbre est un graphe non orienté dans lequel deux sommets quelconques sont connectés par exactement un chemin , ou de manière équivalente un graphe non orienté acyclique connexe . Une forêt est un graphe non orienté dans lequel deux sommets quelconques sont connectés par au plus un chemin, ou de manière équivalente un graphe non orienté acyclique, ou de manière équivalente une union disjointe d'arbres.

Un arbre dirigé, arbre orienté, polytree , ou réseau simple connexe est un graphe acyclique dirigé (DAG) dont le graphe non orienté sous-jacent est un arbre. Une polyforêt (ou forêt dirigée ou forêt orientée) est un graphe acyclique dirigé dont le graphe non orienté sous-jacent est une forêt.

Les différents types de structures de données appelés arbres en informatique ont des graphes sous-jacents qui sont des arbres en théorie des graphes, bien que ces structures de données soient généralement des arbres enracinés. Un arbre enraciné peut être dirigé, appelé arbre enraciné dirigé, soit en faisant en sorte que toutes ses arêtes pointent loin de la racine - auquel cas il est appelé arborescence ou arbre sortant - soit en faisant en sorte que toutes ses arêtes pointent vers la racine - auquel cas il est appelé anti-arborescence ou arbre entrant . Un arbre enraciné lui-même a été défini par certains auteurs comme un graphe orienté. Une forêt enracinée est une union disjointe d'arbres enracinés. Une forêt enracinée peut être dirigée, appelée forêt enracinée dirigée, soit en faisant en sorte que tous ses bords pointent loin de la racine dans chaque arbre enraciné - auquel cas elle est appelée une forêt ramifiée ou extérieure - soit en faisant en sorte que tous ses bords pointent vers la racine dans chaque arbre enraciné - auquel cas elle est appelée une forêt anti-ramifiée ou intérieure.

Le terme arbre a été inventé en 1857 par le mathématicien britannique Arthur Cayley .

Un arbre est un graphe non orienté G qui satisfait l'une des conditions équivalentes suivantes :

• G est connexe et acyclique (ne contient aucun cycle).
• G est acyclique et un cycle simple est formé si une arête est ajoutée à G.
• G est connecté, mais deviendrait déconnecté si une seule arête était supprimée de G.
• G est connexe et le graphe complet K ₃ n'est pas un mineur de G .
• Deux sommets quelconques de G peuvent être connectés par un chemin simple unique .

Si G possède un nombre fini de sommets, disons n , alors les affirmations ci-dessus sont également équivalentes à l'une des conditions suivantes :

• G est connexe et possède n − 1 arêtes.
• G est connexe, et chaque sous-graphe de G comprend au moins un sommet avec zéro ou une arête incidente. (C'est-à-dire que G est connexe et 1-dégénéré .)
• G n’a pas de cycles simples et possède n − 1 arêtes.

Comme partout ailleurs dans la théorie des graphes, le graphe d'ordre zéro (graphe sans sommets) n'est généralement pas considéré comme un arbre : bien qu'il soit connexe en tant que graphe (deux sommets quelconques peuvent être connectés par un chemin), il n'est pas connexe en 0 (ni même connexe en (−1)) en topologie algébrique, contrairement aux arbres non vides, et viole la relation « un sommet de plus que d'arêtes ». Il peut cependant être considéré comme une forêt composée de zéro arbre.

Un sommet interne (ou sommet intérieur) est un sommet de degré au moins 2. De même, un sommet externe (ou sommet extérieur, sommet terminal ou feuille) est un sommet de degré 1. Un sommet de branche dans un arbre est un sommet de degré au moins 3.

Un arbre irréductible (ou arbre réduit en série) est un arbre dans lequel il n'y a pas de sommet de degré 2 (énuméré à la séquence A000014 dans l' OEIS ).

Une forêt est un graphe acyclique non orienté ou, de manière équivalente, une union disjointe d'arbres. Trivialement, chaque composant connexe d'une forêt est un arbre. Comme cas particuliers, le graphe d'ordre zéro (une forêt composée de zéro arbre), un arbre unique et un graphe sans arête sont des exemples de forêts. Comme pour chaque arbre V − E = 1 , nous pouvons facilement compter le nombre d'arbres qui se trouvent dans une forêt en soustrayant la différence entre le nombre total de sommets et le nombre total d'arêtes. V − E = nombre d'arbres dans une forêt.

Un polyarbre (ou arbre dirigé ou arbre orienté ou réseau simple connexe ) est un graphe acyclique dirigé (DAG) dont le graphe non orienté sous-jacent est un arbre. En d'autres termes, si l'on remplace ses arêtes dirigées par des arêtes non orientées, on obtient un graphe non orienté qui est à la fois connexe et acyclique.

Certains auteurs limitent l'expression « arbre dirigé » au cas où les arêtes sont toutes dirigées vers un sommet particulier, ou toutes dirigées à l'opposé d'un sommet particulier (voir arborescence ).

Une polyforêt (ou forêt dirigée ou forêt orientée) est un graphe orienté acyclique dont le graphe non orienté sous-jacent est une forêt. En d'autres termes, si on remplace ses arêtes orientées par des arêtes non orientées, on obtient un graphe non orienté qui est acyclique.

Comme pour les arbres dirigés, certains auteurs limitent l'expression « forêt dirigée » au cas où les arêtes de chaque composant connexe sont toutes dirigées vers un sommet particulier, ou toutes dirigées loin d'un sommet particulier (voir ramification ).

Un arbre enraciné est un arbre dans lequel un sommet a été désigné comme racine. Les arêtes d'un arbre enraciné peuvent se voir attribuer une orientation naturelle, soit loin soit vers la racine, auquel cas la structure devient un arbre enraciné dirigé. Lorsqu'un arbre enraciné dirigé a une orientation loin de la racine, il est appelé arborescence ou out-tree ; lorsqu'il a une orientation vers la racine, il est appelé anti-arborescence ou in-tree . L'ordre de l'arbre est l' ordre partiel sur les sommets d'un arbre avec u < v si et seulement si le chemin unique de la racine à v passe par u . Un arbre enraciné T qui est un sous-graphe d'un graphe G est un arbre normal si les extrémités de chaque T -chemin dans G sont comparables dans cet ordre de l'arbre (Diestel 2005, p. 15). Les arbres enracinés, souvent avec une structure supplémentaire telle qu'un ordre des voisins à chaque sommet, sont une structure de données clé en informatique ; voir structure de données arborescente .

Dans un contexte où les arbres ont généralement une racine, un arbre sans racine désignée est appelé arbre libre .

Un arbre étiqueté est un arbre dans lequel chaque sommet reçoit une étiquette unique. Les sommets d'un arbre étiqueté sur n sommets (pour des entiers non négatifs n ) reçoivent généralement les étiquettes 1, 2, …, n . Un arbre récursif est un arbre enraciné étiqueté où les étiquettes des sommets respectent l'ordre de l'arbre (c'est-à-dire, si u < v pour deux sommets u et v , alors l'étiquette de u est plus petite que l'étiquette de v ).

Dans un arbre enraciné, le parent d'un sommet v est le sommet connecté à v sur le chemin vers la racine ; chaque sommet a un parent unique, sauf que la racine n'a pas de parent. Un enfant d'un sommet v est un sommet dont v est le parent. Un ascendant d'un sommet v est tout sommet qui est soit le parent de v , soit (récursivement) un ascendant d'un parent de v . Un descendant d'un sommet v est tout sommet qui est soit un enfant de v , soit (récursivement) un descendant d'un enfant de v . Un frère d'un sommet v est tout autre sommet de l'arbre qui partage un parent avec v . Une feuille est un sommet sans enfant. Un sommet interne est un sommet qui n'est pas une feuille.

La hauteur d'un sommet dans un arbre enraciné est la longueur du chemin descendant le plus long vers une feuille à partir de ce sommet. La hauteur de l'arbre est la hauteur de la racine. La profondeur d'un sommet est la longueur du chemin vers sa racine ( chemin racine ). La profondeur d'un arbre est la profondeur maximale de tout sommet. La profondeur est généralement nécessaire dans la manipulation des différents arbres auto-équilibrés, en particulier les arbres AVL . La racine a une profondeur de zéro, les feuilles ont une hauteur de zéro et un arbre avec un seul sommet (donc à la fois une racine et une feuille) a une profondeur et une hauteur de zéro. Par convention, un arbre vide (un arbre sans sommets, si ceux-ci sont autorisés) a une profondeur et une hauteur de −1.

Un arbre k -aire (pour les entiers non négatifs k ) est un arbre enraciné dans lequel chaque sommet a au plus k enfants. Les arbres 2-aires sont souvent appelés arbres binaires , tandis que les arbres 3-aires sont parfois appelés arbres ternaires .

Un arbre ordonné (ou arbre plan ou arbre positionnel ) est un arbre enraciné dans lequel un ordre est spécifié pour les enfants de chaque sommet. On l'appelle un « arbre plan » car un ordre des enfants équivaut à une incorporation de l'arbre dans le plan, avec la racine en haut et les enfants de chaque sommet plus bas que ce sommet. Étant donné une incorporation d'un arbre enraciné dans le plan, si l'on fixe une direction des enfants, par exemple de gauche à droite, alors une incorporation donne un ordre des enfants. Inversement, étant donné un arbre ordonné, et en dessinant de manière conventionnelle la racine en haut, alors les sommets enfants d'un arbre ordonné peuvent être dessinés de gauche à droite, ce qui donne une incorporation planaire essentiellement unique.

• Tout arbre est un graphe bipartite . Un graphe est bipartite si et seulement s'il ne contient aucun cycle de longueur impaire. Comme un arbre ne contient aucun cycle, il est bipartite.
• Tout arbre comportant seulement un nombre dénombrable de sommets est un graphe planaire .
• Tout graphe connexe G admet un arbre couvrant , qui est un arbre qui contient tous les sommets de G et dont les arêtes sont les arêtes de G . Des types plus spécifiques d'arbres couvrants, existant dans tout graphe fini connexe, incluent les arbres de recherche en profondeur d'abord et les arbres de recherche en largeur d'abord . En généralisant l'existence des arbres de recherche en profondeur d'abord, tout graphe connexe avec seulement un nombre dénombrable de sommets a un arbre de Trémaux . Cependant, certains graphes d' ordre indénombrable n'ont pas un tel arbre.
• Tout arbre fini à n sommets, avec n > 1 , possède au moins deux sommets terminaux (feuilles). Ce nombre minimal de feuilles est caractéristique des graphes de chemins ; le nombre maximal, n − 1 , n'est atteint que par les graphes en étoile . Le nombre de feuilles est au moins égal au degré maximal du sommet.
• Pour trois sommets quelconques d'un arbre, les trois chemins qui les relient ont exactement un sommet en commun. Plus généralement, un sommet d'un graphe qui appartient aux trois plus courts chemins parmi trois sommets est appelé médiane de ces sommets. Étant donné que tous les trois sommets d'un arbre ont une médiane unique, chaque arbre est un graphe médian .
• Chaque arbre possède un centre constitué d'un sommet ou de deux sommets adjacents. Le centre est le sommet du milieu ou les deux sommets du milieu de chaque chemin le plus long. De même, chaque arbre à n sommets possède un centroïde constitué d'un sommet ou de deux sommets adjacents. Dans le premier cas, la suppression du sommet divise l'arbre en sous-arbres de moins de n /2 sommets. Dans le second cas, la suppression de l'arête entre les deux sommets centraux divise l'arbre en deux sous-arbres d'exactement n /2 sommets.
• Les cliques maximales d'un arbre sont précisément ses arêtes, ce qui implique que la classe des arbres a peu de cliques .

La formule de Cayley stipule qu'il existe n ^{n −2} arbres sur n sommets étiquetés. Une preuve classique utilise les suites de Prüfer , qui montrent naturellement un résultat plus fort : le nombre d'arbres avec des sommets 1, 2, …, n de degrés d ₁ , d ₂ , …, d _n respectivement, est le coefficient multinomial

Un problème plus général est de compter les arbres couvrants dans un graphe non orienté , ce qui est traité par le théorème de l'arbre matriciel . (La formule de Cayley est le cas particulier des arbres couvrants dans un graphe complet .) Le problème similaire de compter tous les sous-arbres quelle que soit leur taille est #P-complet dans le cas général (Jerrum (1994)).

Compter le nombre d'arbres libres non étiquetés est un problème plus difficile. Aucune formule fermée pour le nombre t ( n ) d'arbres à n sommets jusqu'à isomorphisme de graphe n'est connue. Les premières valeurs de t ( n ) sont

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (séquence A000055 dans l' OEIS ).

Otter (1948) a prouvé l'estimation asymptotique

avec C ≈ 0,534949606... et α ≈ 2,95576528565... (séquence A051491 dans l' OEIS ). Ici, le symbole ~ signifie que

Il s'agit d'une conséquence de son estimation asymptotique du nombre r ( n ) d'arbres enracinés non étiquetés à n sommets :

avec D ≈ 0,43992401257... et le même α que ci-dessus (cf. Knuth (1997), chap. 2.3.4.4 et Flajolet & Sedgewick (2009), chap. VII.5, p. 475).

Les premières valeurs de r ( n ) sont

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (séquence A000081 dans l' OEIS ).

• Un graphe de chemins (ou graphe linéaire ) est constitué de n sommets disposés sur une ligne, de sorte que les sommets i et i + 1 sont reliés par une arête pour i = 1, …, n – 1 .
• Un arbre en étoile est constitué d'un sommet central appelé racine et de plusieurs graphes de chemins qui lui sont attachés. Plus formellement, un arbre est en étoile s'il possède exactement un sommet de degré supérieur à 2.
• Un arbre en étoile est un arbre constitué d'un seul sommet interne (et de n – 1 feuilles). En d'autres termes, un arbre en étoile d'ordre n est un arbre d'ordre n avec autant de feuilles que possible.
• Un arbre chenille est un arbre dans lequel tous les sommets sont à une distance de 1 d'un sous-graphe de chemin central.
• Un arbre à homard est un arbre dans lequel tous les sommets sont à une distance de 2 d'un sous-graphe de chemin central.
• Un arbre régulier de degré d est l'arbre infini avec d arêtes à chaque sommet. Ceux-ci apparaissent sous la forme de graphes de Cayley de groupes libres et dans la théorie des bâtiments de Tits . En mécanique statistique, ils sont connus sous le nom de treillis de Bethe .