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 |
Titre | Exploration 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.
|
Lieu | AMPHI Labri |
Orateur | F. MAZOIT |
Email | mazoit@labri.fr |
Url | LaBRI |
Aucun document lié à cet événement.
Fermer la fenetre |