Sujet de stage Master 2 Recherche.
Décompositions arborescentes et stratégies d'encerclement.
Responsables :
Stéphane Bessy
Stéphan Thomassé
Prérequis :
UMINR316: Algorithmique Combinatoire ou une connaissance des thèmes abordés.
Descriptif :
Un jeu de capture sur un réseau (ici, un graphe
non-orienté) oppose un certain nombre d'agents
à un fugitif. Les protagonistes sont placés sur
les noeuds du réseau et peuvent se déplacer à
chaque tour. Le but pour les agents est d'encercler le fugitif,
c'est-à-dire d'occuper tous les voisins du noeud sur lequel est
il est placé, et le but pour le fugitif est de ne pas se
laisser encercler.
Diverses variantes de ce jeu sont obtenues
selon que le fugitif est visible/invisible, rapide/lent, etc...
L'étude de décompositions arborescentes de
graphes fournit des bornes sur le nombre d'agents à placer
pour obtenir une stratégie gagnante (du point de vue des
agents), ainsi que cette stratégie. Par exemple,
la tree-width du graphe sous-jacent est exactement le nombre
d'agents nécessaires pour capturer le fugitif lorsque celui-ci
est visible. A contrario, la path-width du graphe est
exactement le nombre d'agents nécessaires
lorsque le fugitif n'est pas visible par les agents.
Le travail demandé est d'abord un
état de l'art sur le lien entre décompositions de
graphes et jeux de capture. Dans un second temps, on pourra se pencher
sur un certain nombre de questions ouvertes du domaine. Notamment
dans le cas d'un réseau sous-jacent orienté,
l'existence d'une stratégie monotone pour les agents,
c'est-à-dire réduisant à chaque tour l'espace de
déplacement possible pour le fugitif, n'est pas connue.
Suivant la motivation et les qualités du candidat, le
stage pourra être poursuivi et déboucher sur une
inscription en thèse.
Bibliographie :
R. Diestel, Graph Theory. Pour les définitions de base.
P. Seymour et R. Thomas Graph searching, and a min-max theorem for tree-width. L'article fondateur.
N. Nisse, Transparents.
Un exposé de presentation du jeu.
P. Hunter, Transparents.
Un exposé de presentation du jeu dans le cas des graphes orientés.