Intitulé:   
Exploration de graphes et décompositions arborescentes
du groupe Séminaire-Ecole sur les décompositions des graphes

Date 2007-02-08  15:45-17:15
TitreExploration de graphes et décompositions arborescentes 
RésuméÉtant donné un graphe fini G, on peut définir un jeu de gendarmes et de voleurs sur les sommets de G. À chaque tour, les gendarmes peuvent placer un nouveau gendarme ou retirer un gendarme d'un sommet du graphe. Le voleur peut se déplacer sur n'importe quel sommet accessible depuis sa position actuelle sans rencontrer de gendarme. Si on cherche une stratégie gagnante pour les gendarmes, on cherche le nombre minimal de gendarmes nécessaires pour attraper le voleur. Or ce nombre est lié à la largeur arborescente du graphe. Inversement, si on cherche une stratégie pour le voleur, on obtient une obstruction à l'existence d'une décomposition arborescente: les enchevêtrements. Cette obstruction permet de démontrer simplement que la largeur arborescente d'une grille nxn est n.  
LieuAMPHI Labri 
OrateurF. MAZOIT 
Emailmazoit@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Fermer la fenetre