Combinatoire des cartes et polynome de Tutte

Abstract

Les cartes sont les plongements, sans intersection d'arêtes, des graphes dans des surfaces. Les cartes constituent une discrétisation naturelle des surfaces et apparaissent aussi bien en informatique (codage d'informations visuelles) quén physique (surfaces aléatoires de la physique statistique et quantique). Nous établissons des résultats énumératifs pour de nouvelles familles de cartes. En outre, nous définissons des bijections entre les cartes et des classes combinatoires plus simples (chemins planaires, couples d'arbres). Ces bijections révèlent des propriétés structurelles importantes des cartes et permettent leur comptage, leur codage et leur génération aléatoire. Enfin, nous caractérisons un invariant fondamental de la théorie des graphes, le polynôme de Tutte, en nous appuyant sur les cartes. Cette caractérisation permet d'établir des bijections entre plusieurs structures (arbres cou- vrant, suites de degrés, configurations du tas de sable) comptées par le polynôme de Tutte.