COMBINATOIRE ANALYSE

Construction de correspondances

Dans la première partie, nous avons passé en revue tous les ensembles finis qu'il était aisé de dénombrer en faisant usage des deux règles de la somme et du produit. Ces techniques élémentaires s'appliquent plus difficilement lorsqu'on veut dénombrer d'autres structures finies plus élaborées comme celles des arbres ou certains types de graphes. Le plus souvent on est conduit à chercher une correspondance biunivoque entre ces structures et les ensembles finis considérés dans la première partie. Jusqu'ici, il n'existe pas de théorie pour construire ces correspondances, tout est une question d'ingéniosité et de patience. À titre d'exemple, on peut décrire ci-dessous une telle correspondance entre les arbres de n sommets et les (n − 2)-uples (x₁, x₂, ..., x_n-2), où les x_i sont des entiers compris entre 1 et n.

Arbre de sept sommets - crédits : Encyclopædia Universalis France — Arbre de sept sommets
Encyclopædia Universalis France

Un graphe est la donnée d'un ensemble X – ses éléments sont les sommets du graphe – et d'une classe U de sous-ensembles de X à deux éléments, appelés arêtes. Si l'on a x, y ∈ X et {x, y} ∈ U, on dit que x et y sont adjacents. Une chaîne du graphe {X, U} est une suite {x₁, y₁}, {x₂, y₂}, ..., {x_n, y_n} d'arêtes distinctes telle que, lorsque n > 1, on ait :

pour i = 1, 2, ..., n − 1. Si de plus, on a n > 1 et

on dit que la chaîne est un cycle. Un graphe est dit connexe si, pour tout couple de sommets distincts (x, y), il existe une chaîne {x₁, y₁}, {x₂, y₂}, ..., {x_n, y_n} telle que x₁ = x et y_n = y. Un arbre de n sommets est alors défini comme un graphe de n sommets qui est connexe et sans cycles. On a l'habitude de représenter un graphe fini de n sommets comme un ensemble de n points du plan numérotés de 1 à n où les sommets i et j sont reliés entre eux si et seulement si l'on a {i, j} ∈ U. Considérons par exemple le graphe de la figure ci-dessus. C'est un arbre de sept sommets, numérotés de 1 à 7.

Soit A_n l'ensemble de tous les arbres possibles de n sommets numérotés 1, 2, ..., n. Cayley fut le premier à démontrer que l'on a |A_n| = n^n-2. Or ce nombre est précisément le cardinal de l'ensemble H_n de tous les (n − 2)-uples (x₁, x₂, ..., x_n-2) où les x_i sont pris dans X = {1, 2, ..., n} (formule (11) de la première partie). Pour démontrer la formule |A_n| = n^n-2, il suffit donc de construire une bijection Φ de A_n sur H_n. Nous donnons ici la construction d'une telle correspondance due à Prüfer. Celle-ci fait usage des deux propriétés suivantes sur les arbres, faciles à vérifier. D'abord, un arbre a toujours (au moins) un sommet pendant, c'est-à-dire un sommet qui n'est adjacent qu'à un seul autre sommet. Ensuite, si l'on « efface » un sommet pendant d'un arbre de n sommets, et l'arête qui le contient, on obtient un arbre de (n − 1) sommets. La construction de Prüfer est alors la suivante : pour un arbre de A_n donné, on efface le plus petit sommet pendant et l'on désigne par x₁ l'unique sommet qui était adjacent à ce sommet pendant. On répète cette opération avec l'arbre restant de (n − 1) sommets et l'on détermine x₂ et ainsi de suite. On s'arrête lorsqu'il ne reste plus que deux sommets (adjacents). Par exemple, à l'arbre de la figure on fait correspondre la suite (1, 7, 1, 7, 7). Les sommets pendants qu'on a successivement effacés sont 2, 3, 4, 1, 5 et il est resté l'arbre formé par les deux sommets 6 et 7. On vérifie que l'application Φ de A_n sur H_n ainsi construite est bien bijective. D'où l'on déduit |A_n| = |H_n| = n^n-2.

La suite de cet article est accessible aux abonnés

Des contenus variés, complets et fiables
Accessible sur tous les écrans
Pas de publicité

Découvrez nos offres

Déjà abonné ? Se connecter

Écrit par

Dominique FOATA : professeur à la faculté des sciences de Strasbourg.

Carte mentale
Élargissez votre recherche dans Universalis

Classification

Médias

Nombres de Stirling - crédits : Encyclopædia Universalis France — Nombres de Stirling

Encyclopædia Universalis France

Autres références

ALGORITHMIQUE
- Écrit par Philippe COLLARD et Philippe FLAJOLET
- 6 652 mots
- 3 médias
Entrent dans la catégorie des problèmes combinatoires, en informatique, les problèmes qui consistent à déterminer, pour une donnée d, si est satisfaite une condition :
où : (a) S(d) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de ...
ERDÖS PAUL (1913-1996)
- Écrit par Jean-Louis NICOLAS
- 945 mots
Mathématicien brillant et hors du commun, lauréat du prix Wolf en 1983.
Né le 26 mars 1913 à Budapest et décédé le 20 septembre 1996 à Varsovie, Paul Erdös fut un enfant prodige et, à l'âge de quatre ans, il savait déjà compter avec des nombres de trois chiffres et avait redécouvert les nombres négatifs....
FERMAT PIERRE DE (1601-1665)
- Écrit par Encyclopædia Universalis , Catherine GOLDSTEIN et Jean ITARD
- 4 103 mots
Dans le domaine voisin de l'analyse combinatoire, il avait, avant 1636, bien avant Pascal, donné la formule multiplicative du nombre des combinaisons :
ISLAM (La civilisation islamique) - Les mathématiques et les autres sciences
- Écrit par Georges C. ANAWATI , Encyclopædia Universalis et Roshdi RASHED
- 22 273 mots
- 2 médias
L'activité combinatoire a commencé par se manifester comme telle, mais d'une manière dispersée, chez les linguistes, d'une part, et chez les algébristes, d'autre part. Ce n'est que plus tard que se fera la liaison entre les deux courants, et que l'analyse combinatoire se présentera comme un instrument...
Afficher les 9 références

COMBINATOIRE ANALYSE

Construction de correspondances

ALGORITHMIQUE

ERDÖS PAUL (1913-1996)

FERMAT PIERRE DE (1601-1665)

ISLAM (La civilisation islamique) - Les mathématiques et les autres sciences