Arbre (graphe)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Arbre (homonymie).
Un arbre avec 4 feuilles et 3 nœuds internes

En théorie des graphes, un arbre est un graphe non orienté, acyclique et connexe[1]. Sa forme évoque en effet la ramification des branches d'un arbre.

Un ensemble d'arbre est appelé un foret.

Définitions[modifier | modifier le code]

On distingue deux types de sommets dans un arbre :

  • Les feuilles dont le degré est 1 ;
  • Les nœuds internes dont le degré est supérieur à 1.

Il existe plusieurs définitions équivalentes d'un arbre, en plus de celle donnée en introduction.

  • Pour deux définitions basées sur la différence entre le nombre d'arêtes et le nombre de sommets :
    • Un arbre est un graphe connexe non orienté dont le nombre de sommets excède le nombre d'arêtes d'une unité exactement.
    • Un arbre est un graphe non orienté sans cycles dont le nombre de sommets excède le nombre d'arêtes d'une unité exactement.
  • Pour une définition inductive :
    • Un sommet est un arbre.
    • Si G = (S, A) est un arbre, alors (S\cup x, A \cup \big\{ \{ x,s \} \big\} ) est un arbre avec :
      • x est un élément quelconque n'appartenant pas à S et
      • s un sommet de S.
    • Aucun autre graphe n'est un arbre.

Combinatoire des arbres[modifier | modifier le code]

Formule de Cayley[modifier | modifier le code]

Articles détaillés : Formule de Cayley et Bijection de Joyal.

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 \ \mathcal{C}_n\ des arbres de Cayley à n sommets, Joyal établit une bijection entre \ \mathcal{C}_n\times[\![1,n]\!]^2\ et l'ensemble des applications de \ [\![1,n]\!]\ dans \ [\![1,n]\!]\ , noté usuellement \ [\![1,n]\!]^{[\![1,n]\!]}\ . On a ainsi

n^n\ =\ \text{Card}\ \left([\![1,n]\!]^{[\![1,n]\!]}\right)\ =\ \text{Card}\ \left(\mathcal{C}_n\times[\![1,n]\!]^2\right)\ =\ n^2\,\text{Card}\ \mathcal{C}_n.

Orientation[modifier | modifier le code]

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

Arbre comme carte[modifier | modifier le code]

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[2] : 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 :

C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{n! (n+1)!}.

Exemple : arbres à 3 arêtes (et 4 sommets)[modifier | modifier le code]

Les 5 arbres planaires à 3 arêtes, en haut, et les 16 arbres de Cayley à 3 arêtes, en bas. L'arête racine des arbres planaires va du point rouge au point bleu.

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'étoile peut être étiquetée de 4 manières (en choisissant librement l'étiquette du centre, parmi 4 possibilités, le choix des étiquettes des 3 feuilles conduisant alors toujours au même arbre). La ligne peut être étiquetée de 4!=24 manières, équivalentes 2 par 2 (par exemple 1234 et 4321 sont équivalents), donc de 12 manières en réalité, ce qui donne 12 + 4 = 16 = 42 arbres de Cayley à 3 arêtes.
  • L'étoile peut être enracinée de deux manières : la racine peut être une des trois arêtes, peu importe laquelle, les deux choix non homéomorphes sont les choix d'une arête rentrante (vers le centre) ou sortante. La ligne peut être enracinée de 3 manières, extrémité sortante ou rentrante, ou arête centrale, d'où 5 arbres planaires :
2+3=5=C_3 = \frac{1}{4}{6 \choose 3} = \frac{6!}{3! 4!}.

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

Notation de Neveu[modifier | modifier le code]

Article détaillé : Notation de Neveu.
Notation de Neveu pour les sommets d'un arbre planaire

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[3]. 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 \scriptstyle\emptyset\ ). 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

\{\emptyset,1,11,12\},~\{\emptyset,1,2,3\},~\{\emptyset,1,2,21\},~\{\emptyset,1,11,111\}~\text{et}~\{\emptyset,1,11,2\}.

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.

Arbre et décomposition[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. Plus généralement, les graphes non orientés acycliques, qui sont des réunions d'arbres disjoints, s'appellent des forêts.
  2. En fait, on plonge les graphes planaires dans la sphère, vue comme le plan plus un point à l'infini, et on discute l'existence d'homéomorphismes de la sphère envoyant un plongement sur l'autre plongement.
  3. J. Neveu, « Arbres et processus de Galton-Watson », Ann. de l'IHP, vol. 22, no 2,‎ 1986 (lire en ligne) (section 2)

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

(en) Martin Aigner et Günter M. Ziegler, Proofs from THE BOOK, Springer,‎ 2003, 3e éd., 240 p. (ISBN 3540404600), p. 141-146