Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 3 - Graphes connexes,
arbres

 

B - Enumération des arbres étiquetés. Le théorème de Cayley

L'énumération des graphes a pour objectif de calculer le nombre de graphes non isomorphes possédant une certaine propriété. L'étude de ce sujet a été lancée dans les années 1850 par le mathématicien anglais Cayley, qui l'appliqua plus tard à l'énumération des alcanes CnH2n+2 possédant un nombre donné d'atomes de carbone.

On connaît de nombreux résultats. On sait combien il y a de graphes, de graphes bi-chromatiques, de graphes connexes, de graphes eulériens et d'arbres possédant un nombre donné de sommets et d'arêtes. Le résultat n'est pas connu, en revanche, pour les graphes planaires et hamiltoniens. Mais, même dans les cas où il est connu, il est rare que les nombres trouvés s'expriment par des formules simples.

Dans ce paragraphe, nous nous intéressons à une des questions pour lesquelles, justement, existe une réponse simple. On appelle graphe étiqueté tout graphe G possédant n sommets et dont les sommets ont été numérotés de 1 à n de telle sorte que les numéros de deux sommets distincts soient eux aussi distincts. Il faut noter que n'importe quel graphe possède n! étiquetages, correspondant à toutes les manières de numéroter un ensemble à n éléments. Nous dirons que deux graphes étiquetés G1 et G2 sont isomorphes s'il existe entre eux un isomorphisme f préservant la numérotation, c'est-à-dire tel que f(vk) = wk (dans ces conditions, on dira que f est un isomorphisme de graphes étiquetés).

Par exemple, dans la figure ci-dessous, les deux premiers graphes sont isomorphes, mais aucun n'est isomorphe au troisième.

Il y a, en fait, douze manières d'étiqueter cet arbre à isomorphisme près. Il y a, de manière analogue, quatre façons d'étiqueter le graphe ci-dessous à isomorphisme près.

Théorème - (Cayley, 1889) Il y a nn-2 classes d'isomorphisme d'arbres étiquettés à n sommets.

Remarque -  les arbres à quatre sommets étant forcément de l'un des deux types ci-dessus, on trouve bien 16 = 42 classes.

Démonstration - nous allons établir l'existence d'une correspondance bijective entre l'ensemble des classes de graphes étiquetés à n sommets et l'ensemble des (n-2)-uplets (a1, , an), où chaque ai est un entier compris entre 1 et n. Comme il y a nn-2 tels (n-2)-uplets, ceci démontrera le théorème. Nous supposons n 3 (le résultat est évident pour n 2).

Soit A un arbre à n sommets. Il possède un certain nombre de sommets pendants (qui auront les mêmes numéros pour un autre arbre isomorphe). Parmi ces sommets pendants, il en existe un qui a le plus petit numéro. Soit a1 le numéro du sommet adjacent à celui-ci. Puis nous supprimons ce sommet pendant ``minimal'' et l'arête qui y aboutissait. Il nous reste un arbre à n - 1 sommets, pour lequel nous recommençons l'opération. Nous aboutissons finalement, lorsqu'il ne reste plus que deux sommets, à un (n-2)-uplet (a1, , an-2).

Par exemple, si A est l'arbre étiqueté de la figure ci-contre, vérifiez que le 5-uplet correspondant est (6,5,6,5,1).

L'animation proposée vous permettra de tester votre maîtrise de l'algorithme. Essayez de deviner quelles sont les arêtes successives enlevées à l'arbre (cliquez sur le bouton pour mettre en évidence chaque nouvelle arête supprimée au fur et à mesure du déroulement de l'algorithme).

On notera que les numéros des sommets pendants du graphe ne peuvent apparaître dans le (n-2)-uplet. En effet, ces sommets ne sont, à aucun moment de la procédure, adjacents à un sommet pendant, sinon le graphe ne serait pas connexe.

D'autre part, soit vk un sommet non pendant. S'il est, à un moment, effacé, c'est qu'il vient de devenir le plus petit sommet pendant. Il y a donc eu un moment où il est devenu pendant. A ce moment, on a placé k dans le (n-2)-uplet et on a effacé l'arête pendante qui aboutissait à vk. S'il n'est pas effacé, le même raisonnement reste valable puisque les deux sommets restants sont tous les deux pendants.

Il en résulte que les nombres qui figurent dans le (n-2)-uplet sont exactement les numéros des sommets non pendants (et on vérifierait que le nombre de fois où ils apparaissent est égal à leur degré diminué de 1). Soit alors (a1, , an-2) un (n-2)-uplet. Soit b1 le plus petit nombre entre 1 et n qui ne figure pas dans ce (n-2)-uplet. C'est le numéro du plus petit sommet pendant et nous savons que celui-ci est relié à a1. Parmi les éléments de {1, , n} distincts de b1, le plus petit qui ne figure pas dans (a2, , an-2) est le numéro du deuxième sommet enlevé : nous le relions à a2. On reconstruit ainsi le graphe arête par arête. A la fin, on a construit n-2 arêtes : b1a1, b2a2, , bn-2an-2. Les sommets b1, , bn-2, an-2 sont deux à deux distincts. Il reste donc un unique numéro entre 1 et n différent de ceux-ci. On le relie à an-2 pour obtenir la dernière arête.

Nous avons associé à toute classe d'arbres étiquetés un (n-2)-uplet et montré comment retrouver, à partir du (n-2)-uplet, l'arbre étiqueté de départ. Ceci prouve que la correspondance ainsi construite est bijective et achève la démonstration du théorème.

Exemple -  testez vous en cherchant le le graphe associé à (1,5,5,5,1) : l'animation ci-dessous vous guide pour le début de la recherche.