Gendarmes, Voleurs et Topologie algébrique

David Ellison, RMIT, Australia
Jeudi 15 Juin 2017 à 11h, Salle 24-25/405, Campus Jussieu
Abstract
Le jeu du gendarme et du voleur, introduit par Alain Quilliot dans sa thèse en 1978, est un jeu à deux joueurs sur un graphe. Le gendarme commence en choisissant son point de départ sur un sommet du graphe ; puis le voleur choisit le sien. Ensuite, ils se déplacent chacun leur tour le long des arêtes du graphe. La question est de savoir si le gendarme a une stratégie qui lui permet d'attraper le voleur. Dans le cas contraire, la question devient : combien faut-il de gendarmes pour attraper le voleur ? Quilliot a démontré dans sa thèse qu'un seul gendarme suffit à attraper le voleur si et seulement si le graphe est démontable, c'est-à-dire si et seulement si on peut le réduire à un seul sommet en retirant successivement des sommets où le voleur peut être coincé. Il s'ensuit que les graphes démontables correspondent à la classe d'homotopie du point, et que certains invariants homotopiques, comme les groupes d'homologie, permettent de découvrir des propriétés structurelles des graphes où le gendarme peut attraper le voleur.
This entry was posted in Events