64
4 Permutations, partitions, et graphes
de degrés prescrits d 1 , . . . , d n . Soit σ ∈ A 2n un appariement de 2n points. On
construit un élément M σ ∈ M d1,...,dn à partir de σ comme suit :
— pour tout 1 k n, on dispose d k demi-arêtes sur le sommet k, soit
au total 2(d 1 + · · · + d n ) demi-arêtes numérotées ;
— on associe les 2n demi-arêtes en utilisant l’appariement σ.
Soit G d1,...,dn ⊂ M d1,...,dn l’ensemble des graphes de M d1,...,dn . L’algorithme
des configurations permet de simuler la loi uniforme sur G d1,...,dn en utilisant
le multigraphe M σ pour un appariement aléatoire σ, et la méthode du rejet.
Théorème 4.6 (Algorithme des configurations de Bollobás). Si (σ k ) k1 est
une suite d’appariements aléatoires de loi uniforme sur A 2n , et si T est le
plus petit entier k 1 tel que M σ k ∈ G d1,...,dn c’est-à-dire que le multigraphe
M σ k n’a ni arêtes multiples ni boucles, alors T est fini presque sûrement et
suit une loi géométrique, et M σ T suit la loi uniforme sur G d1,...,dn .
On dit que le multigraphe aléatoire M σ1 est le modèle des configurations
à degrés prescrits. Les appariements aléatoires de loi uniforme peuvent être
obtenus en utilisant le théorème 4.3.
Idée de la preuve. Tout d’abord P(M σ1 ∈ G d1,...,dn ) > 0 car le support de la
loi de M σ1 est M d1,...,dn . L’algorithme du rejet stoppe en un temps géométrique T fini presque sûrement.
On peut montrer que M → P(M σ1 = M ) est constante sur G d1,...,dn . Ainsi
la loi conditionnelle de M σ1 sachant {M σ1 ∈ G d1,...,dn } est la loi uniforme sur
G d1,...,dn . Or cette loi conditionnelle est la loi de M σ T (méthode du rejet).
Notons que M σ1 ne suit pas la loi uniforme sur M d1,...,dn car l’application
M → P(M σ1 = M ) n’est pas constante sur M d1,...,dn : si deux multigraphes
ne différent que par le nombre d’arêtes multiples entre deux sommets précis alors ils n’ont pas la même probabilité d’apparaître car ces arêtes sont
indistinguables donc permutables (idem pour les boucles).
4.5 Arbres aléatoires
Une structure d’arbre très courante est celle d’arbre binaire : chaque sommet possède 0 ou 2 enfants, c’est-à-dire 1 ou 3 voisins si l’arbre est vu comme
un graphe. On s’intéresse à des arbres enracinés : il y a donc un nombre impair
de sommets. On s’intéresse à des arbres planaires : on numérote les sommets
de gauche à droite pour des individus d’une même génération, en partant de
la racine, numérotée 1 et figurée en bas, comme sur la figure 4.2. On note T n
l’ensemble des arbres numérotés de ce type possédant 2n + 1 sommets.
Il est possible de coder chaque élément de T n par une trajectoire de la
marche aléatoire simple. Plus précisément, étant donné un élément de T n , soit
x
(i) le nombre d’enfants du sommet i et u i = x
(i)
− 1 pour 1 i 2n + 1.
On pose s 0 = 0 et s i+1 = s i + u i+1 pour tout 0 i 2n. La figure 4.2 donne
4 Permutations, partitions, et graphes
de degrés prescrits d 1 , . . . , d n . Soit σ ∈ A 2n un appariement de 2n points. On
construit un élément M σ ∈ M d1,...,dn à partir de σ comme suit :
— pour tout 1 k n, on dispose d k demi-arêtes sur le sommet k, soit
au total 2(d 1 + · · · + d n ) demi-arêtes numérotées ;
— on associe les 2n demi-arêtes en utilisant l’appariement σ.
Soit G d1,...,dn ⊂ M d1,...,dn l’ensemble des graphes de M d1,...,dn . L’algorithme
des configurations permet de simuler la loi uniforme sur G d1,...,dn en utilisant
le multigraphe M σ pour un appariement aléatoire σ, et la méthode du rejet.
Théorème 4.6 (Algorithme des configurations de Bollobás). Si (σ k ) k1 est
une suite d’appariements aléatoires de loi uniforme sur A 2n , et si T est le
plus petit entier k 1 tel que M σ k ∈ G d1,...,dn c’est-à-dire que le multigraphe
M σ k n’a ni arêtes multiples ni boucles, alors T est fini presque sûrement et
suit une loi géométrique, et M σ T suit la loi uniforme sur G d1,...,dn .
On dit que le multigraphe aléatoire M σ1 est le modèle des configurations
à degrés prescrits. Les appariements aléatoires de loi uniforme peuvent être
obtenus en utilisant le théorème 4.3.
Idée de la preuve. Tout d’abord P(M σ1 ∈ G d1,...,dn ) > 0 car le support de la
loi de M σ1 est M d1,...,dn . L’algorithme du rejet stoppe en un temps géométrique T fini presque sûrement.
On peut montrer que M → P(M σ1 = M ) est constante sur G d1,...,dn . Ainsi
la loi conditionnelle de M σ1 sachant {M σ1 ∈ G d1,...,dn } est la loi uniforme sur
G d1,...,dn . Or cette loi conditionnelle est la loi de M σ T (méthode du rejet).
Notons que M σ1 ne suit pas la loi uniforme sur M d1,...,dn car l’application
M → P(M σ1 = M ) n’est pas constante sur M d1,...,dn : si deux multigraphes
ne différent que par le nombre d’arêtes multiples entre deux sommets précis alors ils n’ont pas la même probabilité d’apparaître car ces arêtes sont
indistinguables donc permutables (idem pour les boucles).
4.5 Arbres aléatoires
Une structure d’arbre très courante est celle d’arbre binaire : chaque sommet possède 0 ou 2 enfants, c’est-à-dire 1 ou 3 voisins si l’arbre est vu comme
un graphe. On s’intéresse à des arbres enracinés : il y a donc un nombre impair
de sommets. On s’intéresse à des arbres planaires : on numérote les sommets
de gauche à droite pour des individus d’une même génération, en partant de
la racine, numérotée 1 et figurée en bas, comme sur la figure 4.2. On note T n
l’ensemble des arbres numérotés de ce type possédant 2n + 1 sommets.
Il est possible de coder chaque élément de T n par une trajectoire de la
marche aléatoire simple. Plus précisément, étant donné un élément de T n , soit
x
(i) le nombre d’enfants du sommet i et u i = x
(i)
− 1 pour 1 i 2n + 1.
On pose s 0 = 0 et s i+1 = s i + u i+1 pour tout 0 i 2n. La figure 4.2 donne