|
Sujet : Cartes combinatoires et algorithmes de génération aléatoire Mes recherches m'ont donné l'occasion d'utiliser et de développer des techniques qui s'apparentent à différents domaines dont les principaux sont :
Ces thèmes interagissent largement dans tous les travaux que j'ai mené. Dans ce résumé figurent les travaux qui concernent les cartes combinatoires (ie les plongements de graphes) et qui constituent ma thèse de doctorat. Les cartes sont les représentations combinatoires naturelles des plongements de graphes dans une surface, telle que le plan, la sphère ou une surface de genre supérieur. Je développe des techniques d'énumération constructive et des algorithmes de génération aléatoire pour ces objets. Les applications visées sont l'étude expérimentale et théorique des propriétés statistiques de ces cartes et de l'efficacité des algorithmes qui les utilisent (plongement, dessin, coloration...). Cartes planaires et énumération La théorie énumérative des cartes planaires a été développée par W.T. Tutte dans les années soixante. Celui-ci a mis en évidence des formules énumératives closes particulièrement élégantes à l'issu de calculs très complexes. Avec R. Cori et B. Jacquard, nous avons introduit la notion d'arbre de description, pour coder de manière uniforme les décompositions récursives de W.T. Tutte. Cette approche nous a permis d'extraire un ensemble d'opérations élémentaires qui unifient et clarifient les méthodes de Tutte. Méthodes bijectives et algorithmes de codage Une des contributions les plus importantes de ma thèse est l'introduction d'une nouvelle famille d'arbres couvrants des cartes, associée à une méthode bijective la conjugaison d'arbres. Ces ingrédients permettent pour commencer de donner une explication intuitive directe des formules de Tutte et d'expliquer des identités observées par différents auteurs et restées incomprises jusque là. De plus ces arbres couvrants fournissent des codages compacts de plusieurs familles de cartes planaires, codages dont la compacité est similaire aux meilleurs résultats connus mais qui sont significativement plus simples à obtenir. La conjugaison d'arbres permet quant à elle d'utiliser les codages pour écrire des algorithmes de génération aléatoire uniforme de ces même familles de cartes. Ces algorithmes sont de complexité linéaire et permettent le contrôle de certains paramètres (degré des sommets...), alors que les algorithmes connus jusqu'ici étaient de complexité au moins quadratique et ne permettaient aucun raffinement. Enfin avec M. Bousquet-Mélou, nous avons pu étendre l'utilisation de mes méthodes au domaine, beaucoup plus ancien, de l'énumération des revêtements de la sphère par elle-même. Ces résultats unifient de manière surprenante le travail de Tutte sur les cartes avec l'approche d'Hurwitz pour les revêtements. Nous avons ainsi été amenés à mettre à jour de nouvelles formules énumératives remarquablement simples dans un domaine pourtant étudié depuis le début du siècle et qui connaît un gros regain d'activité depuis une dizaine d'années. Nos résultats sont utilisés pour la classification algorithmique effective des revêtements (travaux de S. Zvonkin et al.). Algorithmes de génération aléatoire, polyèdres convexes, triangulations Afin de rendre accessible une plus grande variété de familles de cartes, j'ai proposé une méthode de rejet particulière baptisée l'extraction/rejet. En particulier sont ainsi traités les cas des graphes de polyèdres convexes et des graphes planaires maximaux pour lesquels il n'existait aucun algorithme. Ces résultats ont fait l'objet d'un exposé au 31ème congrès annuel d'informatique théorique de l'ACM (STOC'99). Les algorithmes d'extraction/rejet sont probabilistes et l'étude de leur complexité fait appel à des méthodes d'analyse asymptotique des structures. Après avoir obtenu dans ma thèse les résultats nécessaires à la détermination de la complexité de mes générateurs, j'ai entamé en collaboration avec Ph. Flajolet et M. Soria l'étude détaillée des schémas de composition apparaissant. Les résultats que nous obtenons mettent en jeu des propriétés fines d'analyse de cols coalescents. Enfin comme premier exemple significatif d'application expérimentale de mes générateurs, j'ai présenté une conjecture sur le diamètre des graphes planaires maximaux aléatoires : la mesure expérimentale de ce diamètre fait en effet apparaître une loi limite et un comportement asymptotique pour les graphes à n-sommets. Ce comportement est surprenant comme pour un maillage régulier de la sphère). Cette contradiction apparente est très intéressante car elle suggère que le modèle de cartes planaires aléatoires, couramment utilisé en physique statistique comme approximation discrète des modèles continus de surface, n'est pas de nature géométrique. Un de mes objectifs actuels est de comprendre ce phénomène, dans le cadre de l'action de recherche coopérative inria alcophys réunissant des informaticiens et des physiciens statisticiens. Outre l'étude expérimentale des statistiques, les générateurs aléatoires permettent de construire des jeux de tests représentatifs de grande taille. Mes algorithmes sur les objets planaires sont particulièrement intéressants dans le contexte du dessin de graphe, pour observer le comportement des algorithmes sur des entrées non triviales aléatoires de grande taille. C'est ce qui motive l'intégration en préparation de mes programmes à la bibliothèque d'algorithmes de dessin de graphes Pigale développée par P. Rosenstiehl, H. de Frayssex et P. Ossona de Mendez.
Cartes de genre supérieur Les problématiques abordées sur les cartes planaires s'étendent naturellement aux plongements dans les surfaces de genres supérieurs, où beaucoup moins de résultats sont disponibles. Avec M. Marcus, j'ai obtenu une bijection permettant de coder ces cartes à l'aide de diagrammes de cordes. Une partie de ma thèse est alors consacrée à obtenir différents résultats d'énumération, qui unifient les résultats connus pour ces objets (avec A. Goupil et D. Poulalhon. Ces résultats, obtenus en introduisant des méthodes bijectives dans un contexte algébrique sont les premiers de ce type à dépasser significativement le cas planaire.
Nous illustrons l'efficacité des nouveaux algorithmes de propagation sur un ensemble de problèmes combinatoires.
Sujet : Complexité algorithmique des systèmes dynamiques
continus et hybrides |