Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2011-04-15  10:45-11:45
TitreHypergraphes sur des surfaces: dualité et largeur arborescente  
RésuméLe dual d'un graphe planaire G est obtenu en plaçant un sommet par face de G et en ajoutant pour toute arête e de G une arête qui relie les centres des faces incidente à e. Cette notion classique s'étend sans problème aux plongements cellulaires sur des surfaces quelconques. Elle se généralise aussi aux hyper cartes qui sont des plongements d'hypergraphes sur des surfaces orientables. Par ailleurs, les travaux de Bruno Courcelle ont montré que la largeur arborescente peut servir de mesure de "complexité" des graphes. Comme il semblerait curieux que la "complexité" d'un plongement et cette de son dual soit très différente, on s'attend à ce que la largeur arborescente d'un plongement et celle de son dual soit proche. Dans cet exposé, montrerai comment définir une dualité pour les hypergraphes plongés dans des surfaces quelconques et comment j'ai utilisé cette extension pour obtenir un lien entre la largeur arborescente d'un plongement et celle de son dual.  
Lieusalle 76 
OrateurFrédéric Mazoit  



Aucun document lié à cet événement.

Retour
Retour à l'index