Gilles Schaeffer, LaBRI, Universit\'e Bordeaux 1
Conjugaison d'arbres et cartes combinatoires aléatoires
Quelques mots sur les arbres et les cartes planaires me permettront
d'illustrer le lien entre énumération, codage et génération aléatoire.
Je présenterai une analogie que je trouve amusante : de même que
les arbres plans sont des classes de conjugaison de mots, ma
conviction est que les cartes planaires sont des classes de
conjugaison d'arbres.
- Pour commencer, cette idée permet de comprendre
l'existence de formules closes simples pour l'énumération de
différentes familles de cartes (les formules de Tutte) et d'en
découvrir d'autres.
- Puis elle se traduit par la définition
de nouvelles familles d'arbres couvrants canoniques des
cartes, qui donnent des codages optimaux en
espace pour certaines familles.
- Enfin le décodage de ces arbres, associé à d'autres
techniques telles que l'extraction de noyaux
fournit des algorithmes de génération aléatoire
efficaces pour toutes sortes de cartes planaires (simples,
biparties, 2-, 3-, ou 4-connexes, triangulations,...). La preuve
de l'efficacité de ces algorithmes fait appel à des techniques de
combinatoire analytique.
À l'aide d'un exemple, je montrerai comment ces quelques idées
permettent de conjecturer des propriétés statistiques des graphes
planaires maximaux ou des graphes de polyèdres convexes.
(Résumé détaillé à paraître dans les actes de STOC'99).