Loading AI tools
graphe non orienté, connecté et acyclique De Wikipédia, l'encyclopédie libre
En théorie des graphes, un arbre est un graphe acyclique et connexe[1]. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytique[2], qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley.
Un ensemble d'arbres est appelé une forêt.
Un graphe représente un ensemble de points, appelés sommets ou nœuds, reliés ou non entre eux par des traits, appelés arêtes.
Il s'agit donc d'un concept très simple et d'un outil de modélisation très général, utile dans de nombreux domaines.
À noter que la disposition des sommets (position dans l'espace) n'a pas d'importance, ni même la forme des arêtes reliant éventuellement ces sommets (ligne droite, courbe etc). La seule chose qui compte est la relation entre les sommets.
Un arbre est un graphe qui vérifie les propriétés suivantes :
Un graphe est un couple tel que
Un arbre est un graphe tel que
Dans le cas d'arbres finis, c'est-à-dire quand l'ensemble des sommets est fini, il existe une définition alternative. En effet, il est possible de définir par récurrence l'ensemble des arbres finis dont les sommets appartiennent à un ensemble non vide donné E (fini ou infini) :
Autrement dit, l'ensemble des arbres dont les sommets appartiennent à E est le plus petit ensemble de graphes qui vérifie les deux premières règles ci-dessus.
Il existe plusieurs notions très utiles associées aux arbres, certaines sont données dans le tableau ci-dessous. Les notions données ici sont en fait toutes valables dans le cadre général de graphes. Dans le tableau on se fixe un arbre (S,A).
Notion | Définition intuitive | Définition formelle |
---|---|---|
Sommets adjacents | Deux sommets x et y sont adjacents s'ils sont reliés par une arête. | |
Arêtes adjacentes | Deux arêtes a1 et a2 sont adjacentes si elles partagent une extrémité en commun. | |
Degré d'un sommet x | Nombre de sommets adjacents à x. | |
Feuille | Sommet x dont le degré vaut 1. | |
Sommet interne | Sommet x dont le degré est strictement supérieur à 1. | |
Chemin d'arêtes | Chemin constitué de plusieurs arêtes adjacentes mises bout à bout. | |
Distance entre deux sommets x et y | Taille du plus court chemin reliant x et y. | Si x et y sont distincts alors la distance d(x,y) vaut
et sinon la distance vaut 0. |
Il existe plusieurs types d'arbres qui peuvent être des cas particuliers d'arbres ou alors des arbres sur lesquels de la structure a été rajoutée.
Un arbre fini est un arbre tel que l'ensemble de ses sommets est fini. Formellement, un arbre (S,A) est fini si S est de cardinal fini. Dans la suite, |S| est le nombre de sommets et |A| est le nombre d'arêtes.
On peut remarquer les propriétés suivantes :
Dans le cas particulier où S est l'ensemble des entiers entre 1 et n alors on dit que l'arbre (S,A) est un arbre de Cayley (avec n sommets).
Un arbre localement fini est un arbre tel que le degré de chaque sommet est fini. Formellement, un arbre (S,A) est localement fini si pour tout sommet x de S, deg(x) est fini.
Un arbre fini est toujours localement fini mais la réciproque n'est pas vraie. Le nombre de sommets d'un arbre localement fini est fini ou dénombrable.
Un arbre enraciné est simplement un arbre dont un sommet porte le statut particulier de racine. Formellement, un arbre enraciné est un triplet (S,A,r) où (S,A) est un arbre et r est un élément de S appelé racine.
Cette notion de racine permet de se munir d'un ordre de type ancêtre/descendant entre les sommets de l'arbre. Les arbres enracinés sont utiles pour modéliser la généalogie d'une population.
Notion | Définition intuitive | Définition formelle |
---|---|---|
Hauteur d'un sommet x | Distance entre x et la racine r. | |
Enfant (ou fils) d'un sommet x | Sommet adjacent à x dont la hauteur vaut celle de x plus 1. | |
Parent d'un sommet x | Sommet tel que x est son enfant. | |
Descendant d'un sommet x[3] | Sommet qui découle d'une lignée parent/enfant partant de x. |
|
Ancêtre d'un sommet x[3] | Sommet tel que x est un descendant. |
|
Arête découlant d'un sommet x | Arête qui relie x à un de ses enfants. |
Un arbre étiqueté est un arbre dont les sommets (ou les arêtes) possèdent une étiquette, c'est-à-dire un élément d'un ensemble non vide quelconque (souvent les étiquettes sont des entiers ou des nombres réels).
Un arbre possède toujours un étiquetage de sommets canonique : chaque sommet reçoit lui-même en tant qu'étiquète. Ainsi un arbre de Cayley de n sommets peut être vu comme un arbre étiqueté de manière injective avec les entiers de 1 à n. Avec cet étiquetage canonique, les sommets ont tous des étiquettes différentes. L'avantage du concept d'étiquette est qu'il est possible de donner des étiquettes identiques à plusieurs sommets différents.
Un arbre orienté est un arbre où les arêtes sont orientées, c'est-à-dire qu'elles ont une direction (elles partent d'un sommet pour arriver à un autre). Formellement un arbre orienté est un couple tel que
Un arbre enraciné possède deux orientations canoniques :
Un arbre orienté est toujours connexe par définition (on dit aussi faiblement connexe) mais n'est pas forcément fortement connexe. En fait le seul arbre orienté fortement connexe est l'arbre trivial qui ne possède qu'un seul sommet.
Un arbre ordonné est un arbre enraciné tel que pour chaque sommet, un ordre total a été spécifié pour l'ensemble des enfants de ce sommet.
On peut démontrer qu'il y a nn – 2 arbres numérotés à n sommets. La découverte de cette formule a été attribuée un temps à Arthur Cayley. Pour cette raison, les arbres comme graphes sont parfois appelés arbres de Cayley. Parmi de nombreuses démonstrations, citons celle qui utilise la bijection de Joyal : pour compter les éléments de l'ensemble des arbres de Cayley à n sommets, Joyal établit une bijection entre et l'ensemble des applications de dans , noté usuellement . On a ainsi
Si on choisit un sommet r quelconque dans un arbre, il est possible d'enraciner l'arbre en r, c'est-à-dire orienter toutes les arêtes de sorte qu'il existe un chemin de r à tous les autres nœuds. On obtient alors un arbre enraciné.
Un arbre est un graphe planaire : un graphe qu'on peut dessiner dans le plan sans que ses arêtes ne se touchent, sauf à leurs extrémités. Un tel dessin est parfois appelé plongement d'un graphe. La plupart des graphes planaires ont plusieurs plongements non homéomorphes, au sens où, pour au moins deux de ces plongements, il n'existe pas d'homéomorphisme du plan entier vers lui-même qui envoie un plongement sur l'autre plongement[4] : les classes d'homéomorphismes de ces plongements sont appelés cartes planaires. Les classes d'homéomorphismes des plongements des arbres (graphes) sont aussi appelés arbres (planaires, généraux, de Catalan). Pour le dénombrement, il est commode de les munir d'une racine, à savoir une arête orientée : on parle alors d'arbres planaires enracinés. Ainsi le nombre d'arbres planaires enracinés à n arêtes est le n-ième nombre de Catalan :
Les arbres planaires sont non étiquetés, alors que les arbres de Cayley le sont (les n sommets sont étiquetés de 1 à n). Par exemple, il y a deux arbres non enracinés et non étiquetés à 3 arêtes, celui qui possède un sommet de degré 3 et 3 feuilles (étoile à 3 branches) et celui qui possède 2 sommets de degré 2 et deux feuilles (ligne).
L'arbre peut être représenté avec l'origine de l'arête racine en bas ou en haut (en informatique, la racine est souvent figurée en haut), et l'arête racine soit complètement à droite soit complètement à gauche (dans la figure ci-dessus l'arête racine commence au point rouge et aboutit au point bleu).
Un arbre planaire enraciné peut être décrit de manière non ambigüe par la liste de ses sommets, chacun désigné par une suite finie d'entiers, qui sont les positions, au sein de leur fratrie, des ancêtres du sommet : c'est la notation de Neveu[5]. On utilise ici l'arbre généalogique comme métaphore pour l'arbre planaire : le sommet 2|4|3 désigne le 3e fils du 4e fils du 2e fils de l'ancêtre (l'ancêtre étant lui-même désigné par la suite vide, notée ). Par convention, l'ancêtre est le sommet initial de l'arête racine, et le sommet final de l'arête racine est le fils ainé de l'ancêtre : en tant que tel, il est noté 1. La longueur de la suite associée à un sommet est la hauteur (ou la profondeur) du sommet, i.e. la distance entre ce sommet et le début de la racine, qui représente l'ancêtre : en filant la métaphore, un sommet de hauteur n représente un individu appartenant à la n-ème génération de la population fondée par l'ancêtre.
Les 5 arbres à 3 arêtes sont ainsi décrits par les 5 ensembles de mots
Le parcours des sommets dans l'ordre lexicographique est alors le parcours en profondeur préfixé (ou parcours préfixe) d'un arbre vu comme structure de données en informatique. Par ailleurs, à travers la notation de Neveu, on perçoit comment un arbre planaire encode commodément une réalisation de processus de Galton-Watson avec extinction : l'arbre aléatoire obtenu en encodant une réalisation de processus de Galton-Watson est parfois appelé arbre de Galton-Watson. Rien ne s'oppose à définir un arbre planaire infini à l'aide de la notation de Neveu, ce qui permet d'encoder les réalisations de processus de Galton-Watson où la population ne s'éteint pas.
Du fait des propriétés intéressantes des arbres notamment en informatique théorique, il est parfois utile de décomposer des graphes généraux en arbres. Ainsi on définit par exemple la largeur arborescente en faisant des groupes de nœuds organisés en arbre et l'arboricité en faisant une partition des arêtes en forêts.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.