Afficher la notice abrégée

dc.contributor.authorBERNARDI, Olivier
dc.date2006-09-07
dc.date.accessioned2021-01-13T14:03:20Z
dc.date.available2021-01-13T14:03:20Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/25274
dc.description.abstractLes 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.
dc.description.abstractEnA map is a graph together with a particular (proper) embedding in a surface. Maps are a natural way of representing discrete surfaces and as such they appear both in computer science (encoding of visual data) and in physics (random lattices of statistical physics and quantum gravity). We establish enumerative results for new classes of maps. Moreover, we define several bijections between maps and simpler combinatorial classes (planar walks, pairs of trees). These bijections highlight some important structural properties and allows one to count, sample randomly and encode maps efficiently. Lastly, we give a new characterization of an important graph invariant, the Tutte polynomial, by making use of maps. This characterization allows us to establish bijections between several structures (spanning trees, sandpile configurations, outdegree sequences) counted by the Tutte polynomial.
dc.formatapplication/pdf
dc.languagefr
dc.rightsfree
dc.subjectInformatique
dc.subjectcartes planaire
dc.subjectgraphe
dc.subjecttriangulation
dc.subjecténumération
dc.subjectbijection
dc.subjectpolynôme de Tutte
dc.subjectarbres couvrants
dc.titleCombinatoire des cartes et polynome de Tutte
dc.typeThèses de doctorat
bordeaux.hal.laboratoriesThèses Bordeaux 1 Ori-Oai*
bordeaux.institutionUniversité de Bordeaux
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Combinatoire%20des%20cartes%20et%20polynome%20de%20Tutte&rft.atitle=Combinatoire%20des%20cartes%20et%20polynome%20de%20Tutte&rft.au=BERNARDI,%20Olivier&rft.genre=unknown


Fichier(s) constituant ce document

Thumbnail

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée