68
4 Permutations, partitions, et graphes
ν = lim
n→∞
n
i=1
d n,i (d n,i − 1)
n
j=1 d n,j
=
1
μ
∞
k=1
k(k − 1)p k < ∞,
alors on peut établir que la probabilité que M n soit un graphe tend vers
e
−
1
2 ν−
1
4 ν
2 quand n → ∞. Ainsi la méthode de simulation par rejet du théorème 4.6 du modèle des configurations reste raisonnable si n 1.
La structure d’arbre, bien que cas particulier de la structure de graphe,
est très riche. On trouvera des panoramas dans les livres de Donald Knuth
[Knu05, Volume 4A] et de Michael Drmota [Drm09]. L’algorithme de David
Arnold et Ronan Sleep se trouve dans l’article [AS80], ainsi que dans l’article
de survol de Jarmo Siltaneva et Erkki Mäkinen [SM02] sur les algorithmes
de simulation d’arbres binaires aléatoires. La loi uniforme sur l’ensemble des
arbres binaires plans T n peut également être simulée grâce à un algorithme
récursif séduisant dû à Jean-Luc Rémy [Ré85] : partant d’un élément de T n−1 ,
on fabrique un élément de T n en choisissant aléatoirement uniformément un
sommet dans l’arbre, si c’est une feuille on lui attribue deux enfants qui seront
donc des feuilles, sinon ce sommet est remplacé par un nouveau sommet dont
un des enfants est une feuille et l’autre enfant est le sommet d’origine. Toujours
à propos d’arbres aléatoires, on peut évoquer l’algorithme de David Wilson
[Wil96] pour générer un arbre couvrant de loi uniforme, l’algorithme de Luc
Devroye [Dev12] pour simuler un arbre de Galton-Watson conditionné à avoir
une taille fixe, etc. On pourra consulter avec profit le livre de Russel Lyons et
Yuval Peres [LP15] sur les probabilités sur les arbres et les réseaux.
4 Permutations, partitions, et graphes
ν = lim
n→∞
n
i=1
d n,i (d n,i − 1)
n
j=1 d n,j
=
1
μ
∞
k=1
k(k − 1)p k < ∞,
alors on peut établir que la probabilité que M n soit un graphe tend vers
e
−
1
2 ν−
1
4 ν
2 quand n → ∞. Ainsi la méthode de simulation par rejet du théorème 4.6 du modèle des configurations reste raisonnable si n 1.
La structure d’arbre, bien que cas particulier de la structure de graphe,
est très riche. On trouvera des panoramas dans les livres de Donald Knuth
[Knu05, Volume 4A] et de Michael Drmota [Drm09]. L’algorithme de David
Arnold et Ronan Sleep se trouve dans l’article [AS80], ainsi que dans l’article
de survol de Jarmo Siltaneva et Erkki Mäkinen [SM02] sur les algorithmes
de simulation d’arbres binaires aléatoires. La loi uniforme sur l’ensemble des
arbres binaires plans T n peut également être simulée grâce à un algorithme
récursif séduisant dû à Jean-Luc Rémy [Ré85] : partant d’un élément de T n−1 ,
on fabrique un élément de T n en choisissant aléatoirement uniformément un
sommet dans l’arbre, si c’est une feuille on lui attribue deux enfants qui seront
donc des feuilles, sinon ce sommet est remplacé par un nouveau sommet dont
un des enfants est une feuille et l’autre enfant est le sommet d’origine. Toujours
à propos d’arbres aléatoires, on peut évoquer l’algorithme de David Wilson
[Wil96] pour générer un arbre couvrant de loi uniforme, l’algorithme de Luc
Devroye [Dev12] pour simuler un arbre de Galton-Watson conditionné à avoir
une taille fixe, etc. On pourra consulter avec profit le livre de Russel Lyons et
Yuval Peres [LP15] sur les probabilités sur les arbres et les réseaux.