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).