Combinatorics of maps and the Tutte polynomial

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'en physique ( surfaces aléatoires de la physique statique 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 structurells 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 de bijections entre plusieurs structures (arbres couvrants, suites de degrés, configurations du tas de sable) comptées par le polynôme de Tutte.BORDEAUX1-BU Sciences-Talence (335222101) / SudocBORDEAUX1-Bib Rech. Maths-Info (335222209) / SudocSudocFranceF