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. 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. 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). 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. 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). 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.