Graphe cop-win
En théorie des graphes, un graphe cop-win est un graphe non orienté sur lequel le gendarme (cop) peut toujours gagner (win) une partie de course-poursuite contre le voleur, les joueurs jouant à tour de rôle, et pouvant choisir de se déplacer le long d'une arête du graphe ou de rester sur place, jusqu'à ce que le gendarme arrive sur le sommet du voleur[1]. Les graphes cop-win finis sont également appelés graphes démontables ou graphes constructibles, car ils peuvent être démantelés en supprimant à plusieurs reprises un sommet dominé (dont le voisinage fermé est un sous-ensemble du voisinage d'un autre sommet) ou construits en ajoutant à plusieurs reprises un tel sommet.
Les graphes cop-win peuvent être reconnus en temps polynomial par un algorithme glouton qui construit un ordre de démantèlement. Ils incluent les graphes cordaux et les graphes qui contiennent un sommet universel.
Histoire
La version du jeu avec un seul gendarme et les graphes cop-win définis à partir de celle-ci ont été introduits par Quilliot (1978)[2] - [3]. Nowakowski et Winkler (1983) ont également commencé à travailler très tôt sur ces graphes, qui leur ont été présentés par G. Gabor[3] - [4]. La version du jeu avec plusieurs gendarmes et le cop number défini à partir de celle-ci ont d'abord été étudiés par Aigner et Fromme (1984)[3] - [5].
Définitions
Course-poursuite
Les graphes cop-win peuvent être définis par un jeu de course-poursuite dans lequel deux joueurs, un gendarme et un voleur, sont positionnés à différents sommets d'un graphe non orienté donné. Le gendarme choisit d'abord sommet son sommet de départ, puis le voleur choisit le sien. Ensuite, ils jouent à tour de rôle, toujours avec le gendarme en premier.
À chaque tour, le joueur peut soit se déplacer vers un sommet adjacent, soit rester sur place. Le jeu se termine et le gendarme gagne si le gendarme peut terminer un tour sur le même sommet que le voleur. Le voleur gagne en évitant indéfiniment le gendarme. Un graphe cop-win est un graphe pour lequel le gendarme admet une stratégie (déterministe) gagnante, c'est-à-dire que le gendarme peut à chaque tour choisir un coup de sorte qu'il gagne quelle que soit la façon de jouer du voleur. Si un graphe n'est pas cop-win, on le dit robber-win[4].
Démantèlement
Le voisinage fermé N[v] d'un sommet v dans un graphe donné est l'ensemble de sommets constitués de v lui-même et de tous les autres sommets adjacents à v. Le sommet v est dit dominé par un autre sommet w lorsque N[v] ⊂ N[w] . Autrement dit, v et w sont adjacents, et tout autre voisin de v est également un voisin de w[6].
Un « ordre de démantèlement » ou d'« élimination de la domination » d'un graphe donné est un ordre des sommets tel que, si les sommets sont supprimés un par un dans cet ordre, chaque sommet (sauf le dernier) est dominé au moment où il est supprimé. Un graphe est démontable si et seulement s'il a un ordre de démontage[4] - [6].
Équivalence entre cop-win et démontabilité
Tout graphe démontable fini est cop-win. Cela peut être prouvé par récurrence, avec un graphe à un sommet (trivialement gagné par le gendarme) comme cas de base. Pour un graphe plus grand, soit v un sommet dominé. Par l'hypothèse de récurrence, le gendarme a une stratégie gagnante sur le graphe formé en supprimant v, et peut suivre la même stratégie sur le graphe original faisant comme si le voleur était sur le sommet qui domine v chaque fois que le voleur est sur v. En suivant cette stratégie, soit le gendarme gagne, soit le jeu arrive dans une situation où le voleur est sur v, le gendarme est sur le sommet dominant v et c'est au voleur de jouer, et alors le gendarme pourra gagner en un coup quel que soit le coup du voleur[4] - [3]. Un gendarme suivant cette stratégie récursive sur un graphe à n sommets prend au plus n coups pour gagner, quelle que soit la position de départ. En choisissant soigneusement la position de départ du gendarme, on peut utiliser la même idée pour prouver que, dans un graphe à n sommets, le gendarme peut forcer une victoire en au plus n − 4 coups[3] - [7] - [8].
Inversement, chaque graphe cop-win a un sommet dominé. Car, dans un graphe sans sommets dominés, si le voleur n'a pas déjà perdu, il peut se déplacer vers une position non adjacente au gendarme, où y rester si c'est déjà le cas (sinon le sommet sur lequel il se trouve est dominé), et le voleur peut continuer le jeu indéfiniment en jouant un de ces mouvements sûrs à chaque tour[4] - [3]. De plus, si v est un sommet dominé dans un graphe cop-win, alors en supprimant v on obtient un autre graphe cop-win, sinon le voleur pourrait jouer dans ce sous-graphe, en prétendant que le gendarme est sur le sommet qui domine v chaque fois qu'il est réellement sur v, et le voleur ne se fera jamais attraper. Il s'ensuit par récurrence que tout graphe cop-win fini est démontable[4] - [3].
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cop-win graph » (voir la liste des auteurs).
- (en) Anthony Bonato et Richard J. Nowakowski, The Game of Cops and Robbers on Graphs, t. 61, Providence, RI, American Mathematical Society, coll. « Student Mathematical Library », (ISBN 978-0-8218-5347-4, DOI 10.1090/stml/061, MR 2830217).
- Alain Quilliot, Jeux et pointes fixes sur les graphes, Paris, Université Pierre-et-Marie-Curie, coll. « Thèse de 3ème cycle », , pp. 131–145
- Bonato et Nowakowski (2011).
- (en) Richard J. Nowakowski et Peter Winkler, « Vertex-to-vertex pursuit in a graph », Discrete Mathematics, vol. 43, , pp. 235-239 (DOI 10.1016/0012-365X(83)90160-7, MR 685631, lire en ligne).
- (en) M. Aigner et M. Fromme, « A Game of Cops and Robbers », Discrete Applied Mathematics, vol. 8, no 1, , pp. 1–11 (DOI 10.1016/0166-218X(84)90073-8, MR 739593, lire en ligne).
- (en) Victor Chepoi, « On distance-preserving and domination elimination orderings », SIAM Journal on Discrete Mathematics, no 3, , pp. 414-436 (DOI 10.1137/S0895480195291230, MR 1628110).
- (en) A. Bonato, P. Golovach, G. Hahn et J. Kratochíl, « The capture time of a graph », Discrete Mathematics, vol. 309, no 18, , pp. 5588–5595 (DOI 10.1016/j.disc.2008.04.004, MR 2567962, lire en ligne).
- (en) Tomáš Gavenčiak, « Cop-win Graphs with Maximum Capture-time », Discrete Mathematics, vol. 310, nos 10-11, , pp. 1557–1563 (DOI 10.1016/j.disc.2010.01.015, MR 2601265, lire en ligne).
Liens externes
- Graphes démontables, Système d'information sur les classes de graphes et leurs inclusions