TreeEdit

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

• G est connecté 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 arête unique est retirée de G.
• G est connecté et le graphe complet à 3 sommets K3 n’est pas un mineur de G.
• Deux sommets quelconques dans G peuvent être connectés par un chemin simple unique.

Si G a un nombre infini de sommets, disons n d’entre eux, alors les instructions ci-dessus sont également équivalentes à l’une des conditions suivantes :

• G est connecté et a n−1 arêtes.
• G est connecté, 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 connecté et 1-dégénéré.)
• G n’a pas de cycles simples et a des bords n-1.

Comme 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 connecté de manière vide en tant que graphe (deux sommets quelconques peuvent être connectés par un chemin), il n’est pas connecté à 0 (ou même (-1) connecté) en topologie algébrique, contrairement aux arbres non vides, et viole la relation « un sommet de plus que les arêtes ». Elle peut cependant être considérée comme une forêt composée de zéro arbre.

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

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).

ForestEdit

Une forêt est un graphe non orienté dans lequel deux sommets quelconques sont reliés par au plus un chemin. De manière équivalente, une forêt est un graphe acyclique non orienté, dont toutes les composantes connectées sont des arbres; en d’autres termes, le graphe consiste en une union disjointe d’arbres. Comme cas particuliers, le graphe d’ordre zéro (une forêt composée de zéro arbre), un seul arbre et un graphe sans bord sont des exemples de forêts.Puisque 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 les sommets totaux et les arêtes totales. TV-TE = nombre d’arbres dans une forêt.

PolytreeEdit

Un polytree (ou arbre dirigé ou arbre orienté ou réseau connecté individuellement) est un graphe acyclique dirigé (DAG) dont le graphe non orienté sous-jacent est un arbre. En d’autres termes, si nous remplaçons ses arêtes dirigées par des arêtes non dirigées, nous obtenons un graphe non orienté à la fois connecté 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 loin d’un sommet particulier (voir arborescence).

PolyforestEdit

Un polyforest (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. En d’autres termes, si nous remplaçons ses arêtes dirigées par des arêtes non dirigées, nous obtenons un graphe non orienté qui est acyclique.

Certains auteurs limitent l’expression « forêt dirigée » au cas où les arêtes de chaque composant connecté sont toutes dirigées vers un sommet particulier, ou toutes dirigées à l’écart d’un sommet particulier (voir ramification).

Arbre enraciné

Un arbre enraciné est un arbre dans lequel un sommet a été désigné racine. Les bords d’un arbre enraciné peuvent se voir attribuer une orientation naturelle, soit à l’écart, soit vers la racine, auquel cas la structure devient un arbre enraciné dirigé. Lorsqu’un arbre enraciné dirigé a une orientation éloignée de la racine, on parle d’arborescence ou d’arbre extérieur; lorsqu’il a une orientation vers la racine, on parle d’anti-arborescence ou d’arbre intérieur. L’ordre des arbres 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 chemin T dans G sont comparables dans cet ordre des arbres (Diestel 2005, p. 15). Les arbres enracinés, souvent avec une structure supplémentaire telle que l’ordre des voisins à chaque sommet, sont une structure de données clé en informatique; voir structure de données arborescentes.

Dans un contexte où les arbres sont censés avoir 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 reçoivent généralement les étiquettes 1, 2,…, n. Un arbre récursif est un arbre enraciné étiqueté où les étiquettes de sommet respectent l’ordre des arbres (i.e., 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 la racine qui 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) l’ascendant du parent de v. Un descendant d’un sommet v est tout sommet qui est soit l’enfant de v, soit (récursivement) le descendant de l’un des enfants de v. Un frère à un sommet v est tout autre sommet de l’arbre qui a le même parent que v. Une feuille est un sommet sans enfants. 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 plus long chemin descendant 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). Ceci est généralement nécessaire dans la manipulation des différents arbres auto-équilibrants, en particulier les arbres AVL. La racine a une profondeur nulle, les feuilles ont une hauteur nulle et un arbre avec un seul sommet (donc à la fois une racine et une feuille) a une profondeur et une hauteur nulles. Classiquement, un arbre vide (un arbre sans sommets, si cela est autorisé) a une profondeur et une hauteur de -1.

Un arbre k-ary est un arbre enraciné dans lequel chaque sommet a au plus k enfants. les arbres 2-ary sont souvent appelés arbres binaires, tandis que les arbres 3-ary sont parfois appelés arbres ternaires.

Ordered treeEdit

Un arbre ordonné (ou platane) est un arbre enraciné dans lequel un ordre est spécifié pour les enfants de chaque sommet. C’est ce qu’on appelle un « platane » car un ordre des enfants équivaut à un encastrement de l’arbre dans le plan, avec la racine en haut et les enfants de chaque sommet plus bas que ce sommet. Étant donné un encastrement d’un arbre enraciné dans le plan, si l’on fixe une direction des enfants, disons de gauche à droite, alors un encastrement donne un ordre des enfants. Inversement, étant donné un arbre ordonné, et en dessinant classiquement la racine en haut, les sommets enfants d’un arbre ordonné peuvent être dessinés de gauche à droite, ce qui donne un encastrement plan essentiellement unique.