Gilles Schaeffer (LORIA Nancy)

Quelques mots, des arbres et des cartes planaires me permettront d’illustrer le lien entre énumeration, codage compact et géneration aléatoire uniforme.

Après avoir defini les cartes combinatoires (ou plongements de graphes dans le plan) et en particulier les triangulations et autres graphes de polyedres convexes, je presenterai deux algorithmes pour construire des triangulations aléatoires.

  • Le premier algorithme repose sur une construction élémentaire de certaines cartes, à partir de mots et d’arbres “conjugués”. On illustrera ainsi l’approche bijective : des objets comptes par une jolie formule doivent (devraient ?) être simples à construire.
  • Le second algorithme, l’extraction-rejet, est probabiliste et utilise quelques notions de théorie des graphes (composantes k-connexes). Cependant l’analyse de sa complexite se ramène à l’analyse de la distribution d’un paramètre dans un nouveau schéma de composition de séries génératrices. Ce sera l’occasion d’entrevoir une analyse de cols coalescents et la fonction d’Airy, chère a Ph. Flajolet.

Enfin, sur l’exemple du diamètre des polyedres convexes, je montrerai comment ces algorithmes permettent de conjecturer des propriétés statistiques.

(Voir aussi sur ma page, le résume étendu Random Sampling of Large Planar Maps and Convex Polyhedra STOC’99, Atlanta.)