Dans ce sujet, on s'intéresse à un jeu à deux joueurs qui se joue sur des graphes, le jeu des gendarmes et du voleur. Le sujet est organisé comme suit :

La partie 1 introduit les notions élémentaires de théorie des graphes et l'implémentation des graphes utilisées dans le sujet.
La partie 2 définit formellement le jeu des gendarmes et du voleur : on y établit les premiers résultats sur le jeu et notamment sur le nombre de gendarmes nécessaire ou suffisant pour que les gendarmes soient assurés de gagner le jeu sur certains graphes.
La partie 3 étudie le jeu dans le cas où il n'y a qu'un seul gendarme : elle propose d'établir une caractérisation des graphes où le gendarme possède une stratégie gagnante.
La partie 4 étudie les graphes planaires extérieurs : elle propose de démontrer que, pour cette classe de graphes, deux gendarmes possèdent toujours une stratégie gagnante.
La partie 5 étudie le cas général : elle propose de démontrer l'existence de graphes connexes nécessitant un nombre de gendarmes arbitrairement grand pour leur garantir une stratégie gagnante.

1 Rappels et définitions préliminaires

Graphes. Un graphe simple fini non-orienté

(on dit simplement graphe dans la suite) est la donnée d'un ensemble fini de sommets (ou nouds),

, et d'un ensemble d'arêtes,

, les arêtes étant des paires non-orientées de sommets. Deux sommets

sont dits adjacents dans

lorsque

. On note

l'ensemble des voisins d'un sommet

, et on note

. On généralise ces notions à des ensembles de sommets : ainsi, pour

Représentations d'un graphe dans le plan. Une représentation d'un graphe

est la donnée, dans le plan, d'un ensemble de points de même cardinal que

, reliés deux à deux par des lignes du plan lorsque les sommets correspondants du graphe sont adjacents.

Une représentation d'un graphe est dite planaire lorsque les courbes correspondant aux arêtes ne se croisent pas, hormis en leurs extrémités. Un graphe est dit planaire s'il admet une représentation planaire.

Chemins et cycles. Un chemin dans un graphe

est une suite de sommets

, avec

telle que

. On dit que

est la longueur de

; les sommets

sont appelés les extrémités de

(on dit alors que le chemin relie

). Un chemin est dit simple lorsque chaque arête du graphe y est utilisée au plus une fois. Un cycle dans un graphe

est un chemin simple

tel que

. Un cycle de longueur

est appelé un

-cycle.

(i)

(ii)

(iii)

Figure 1 - Exemples de graphes : (i)

, le cycle de longueur 5, (ii)

, le graphe complet à 5 sommets et (iii)

, le graphe de Petersen

Connexité, acyclicité. Un graphe est connexe si toute paire de sommets distincts est reliée par un chemin. Un graphe peut être partitionné en sous-graphes connexes maximaux, ses composantes connexes. Un graphe acyclique est un graphe ne contenant pas de cycle tandis qu'un arbre est un graphe acyclique et connexe.

Implémentation des graphes. On considérera des graphes représentés en Caml sous forme de listes d'adjacence :

type sommet = int;;
type graphe = (sommet * sommet list) list;;

Dans les fonctions Caml des questions à venir, on pourra utiliser les fonctions usuelles sur les listes comme List.map ou List.mem. On dit de g: graphe qu'il représente un graphe si

pour tout : sommet, contient au plus un élément de la forme ( ,voisins) et n'est pas membre de la liste voisins;
pour tout u: sommet, si u est un élément de voisins' pour un élément (v,voisins') de , alors a un élément de la forme ( ,voisins) et est un élément de voisins.
Le graphe représenté par a alors pour sommets les : sommet tels que contient un élément de la forme (u,voisins), et a une arête reliant et si et seulement si voisins contient .

Question 1.1. Donner une fonction Caml est_graphe: graphe -> bool qui vérifie que son entrée représente un graphe.

Question 1.2. Donner une fonction Caml retire_sommet: graphe -> sommet -> graphe telle que retire_sommet g u retourne un graphe obtenu en retirant de g le sommet u s'il fait partie de

(et les arêtes qui lui sont adjacentes) et retourne

sinon.

2 Le jeu des gendarmes et du voleur

Le jeu est joué sur un graphe

par deux (équipes de) joueurs : d'un côté un ensemble de

gendarmes et de l'autre un unique voleur. Informellement, le jeu se déroule comme suit :

Les gendarmes commencent par occuper chacun un sommet (plusieurs gendarmes peuvent choisir d'occuper le même sommet). Le voleur choisit ensuite un sommet à occuper.
Les deux (équipes de) joueurs jouent ensuite alternativement : (i) un coup des gendarmes consiste à ce que chaque gendarme se déplace, le long d'une arête, vers un sommet adjacent ou reste sur le même sommet ; (ii) le voleur joue ensuite de manière similaire : il peut se déplacer vers un sommet adjacent ou rester sur place.

Les gendarmes gagnent le jeu si l'un des gendarmes occupe le même sommet que le voleur après un nombre fini de coups (on dit alors que ce gendarme capture le voleur); sinon, le voleur gagne. Ci-dessous, on définit plus formellement le jeu à partir des notions suivantes de positions, coups, parties et stratégies.

Positions. Chaque position, désignant l'état du jeu à un moment donné, appartient à l'un des deux joueurs, ce qui est rendu explicite par une étiquette

marquant quel joueur doit jouer dans cette position.

Une position des gendarmes est une paire d'un (

)-uplet de sommets et de l'étiquette G , ce que l'on note dans la suite:

, dont

représente le sommet occupé par le voleur et les

les sommets occupés par les gendarmes.

Une position du voleur peut être de l'une des deux formes suivantes : soit il s'agit d'une paire d'un

-uplet de sommets et de l'étiquette

, notée

(les

représentant les nœuds occupés par les gendarmes au début du jeu), soit il s'agit d'une paire d'un (

)-uplet de sommets et de l'étiquette V , notée

, dont

représente le sommet occupé par le voleur et les

les sommets occupés par les gendarmes.

Coups. On considère trois types de coups : coups initiaux, coups des gendarmes et coups du voleur.

L'ensemble des coups initiaux, aussi appelés positionnements des gendarmes, est l'ensemble

. Il s'agit d'un ensemble de positions étiquetées d'un V puisque, dans ces positions, c'est au voleur de jouer. On verra dans la suite

comme un prédicat unaire et on notera

pour

Les coups des gendarmes sont un ensemble de paires d'une position des gendarmes et d'une position du voleur, décrit par la relation

définie comme suit :

avec

Les coups du voleur sont un ensemble de paires d'une position du voleur et d'une position des gendarmes, décrit par la relation

définie comme suit :

avec

ou bien si

où

L'ensemble des coups du jeu est donc la donnée de

.
Parties et gain. Une partie finie est une suite (finie et potentiellement vide) de positions

, satisfaisant les conditions suivantes:

Positionnement des gendarmes. Si la partie finie est non vide, elle débute par un coup initial de positionnement des gendarmes :

.
Coup du voleur. Si

, on a

.
Coup des gendarmes. Si

, on a

.
Capture. Une partie finie ne peut contenir un coup de la forme

avec

, que s'il s'agit du dernier coup,

, de la partie finie.
La longueur d'une partie finie est le nombre total de coups (ou, de manière équivalente, de positions).

Figure 2 - Un début de partie sur le graphe de Petersen

Une

-partie (ou partie infinie) est une suite infinie de positions dont tout préfixe fini est une partie finie. On note

l'ensemble contenant les parties finies et les

-parties, collectivement appelées parties.

Une partie finie est dite gagnée par les gendarmes si sa dernière position est une capture. Une

-partie est dite gagnée par le voleur.

Représentation graphique d'une position du jeu. On représente le sommet occupé par le voleur avec un (V), les sommets occupés par les gendarmes avec des (G) et les sommets inoccupés avec des • Le début d'une partie sur le graphe de Petersen (un graphe classique représenté en figure 1) est représenté en figure 2. On ne représente pas dans la figure le prochain joueur qui doit jouer puisque l'alternance des coups suffit à le déduire.

Question 2.1. On considère le jeu sur le graphe

(voir figure 1) impliquant un gendarme et un voleur. Justifier que le voleur peut éviter d'être capturé.

Question 2.2. Continuer la partie de la figure 2 de telle sorte que les gendarmes réalisent la capture du voleur quoi que joue le voleur. On décrira les positions grâce aux noms des sommets donnés dans la partie gauche de la figure 2 en complétant les lignes du tableau suivant :

Stratégies. Une stratégie pour le voleur est une application

des positions des voleurs dans les positions des gendarmes telle que, pour toute position des voleurs

. Une stratégie pour les gendarmes est la donnée d'une position initiale

et d'une application

des positions des gendarmes dans les positions des voleurs telle que, pour toute position des gendarmes

et (

) sont respectivement des stratégies pour le voleur et les gendarmes et

est une partie (avec

), on dit que

est jouée selon

et (

) si

est impair, et

est pair.

Une stratégie

pour les gendarmes est gagnante si, pour toute stratégie

du voleur, la partie jouée selon

est finie. Une stratégie

pour le voleur est gagnante si, pour toute stratégie

des gendarmes, la partie jouée selon

est infinie.

On notera

l'ensemble des graphes pour lesquels

gendarmes (cops en anglais) possèdent une stratégie gagnante et

l'ensemble des graphes pour lesquels le voleur (robber en anglais) possède une stratégie gagnante face à

gendarmes.

Un résultat classique de théorie des jeux (que l'on admettra) assure que pour tout graphe et tout entier

, il existe une stratégie gagnante soit pour les gendarmes, soit pour le voleur. En conséquence, pour tout

constitue une partition de l'ensemble des graphes.

(i)

(ii)

(iii)

Figure 3 - Exemples de graphes : un cycle, un arbre et une maison

Remarque importante : Dans la suite, de nombreuses questions demanderont d'établir l'existence d'une stratégie gagnante. Lorsque la question demandera de justifier de l'existence d'une stratégie gagnante, on attendra simplement que les candidates et candidats expliquent informellement, mais précisément et de manière convaincante, comment la stratégie existe. Lorsque la question demandera de montrer l'existence d'une telle stratégie, on attendra une démonstration de l'existence d'une telle stratégie dans le formalisme introduit ci-dessus.

Question 2.3. Pour chacun des trois graphes de la figure 3, indiquer, en le justifiant, si le graphe est dans

pour

Question 2.4. Exhiber un graphe connexe le plus petit possible (pour la taille donnée par la somme du nombre de sommets et d'arêtes) pour lequel un gendarme unique ne suffit pas à assurer la capture. Justifier.

Question 2.5. Justifier que pour tout graphe il existe un certain entier

tel que

gendarmes suffisent à capturer le voleur.

La question précédente justifie l'existence du copnumber, qui est le plus petit nombre

tel que

gendarmes possèdent une stratégie gagnante.

Question 2.6. Exprimer le copnumber d'un graphe non-connexe en fonction de ceux de ses composantes connexes. Justifier.

La relation obtenue dans la question précédente justifie que, dans la suite du sujet, on ne travaillera plus qu'avec des graphes connexes, sauf mention explicite du contraire.

3 Cas d'un unique gendarme ( )

Dans cette partie, on va caractériser les graphes pour lesquels un gendarme unique possède une stratégie gagnante. On commence par introduire quelques notions supplémentaires de théorie des graphes.

Sous-graphe induit. Soit

un graphe et

, on notera

et on appellera sous-graphe de

(induit par

) le graphe (

) où

est l'ensemble des arêtes de

dont les deux extrémités sont dans

(c'est-à-dire

Degré d'un graphe. Étant donné un graphe

, le degré d'un sommet

est noté

et défini comme le cardinal de

. Il s'agit donc du nombre d'arêtes qui ont

pour extrémité (ou du nombre des voisins de

). Le degré d'un graphe

, noté

, est le degré minimal de ses sommets :

Quelques familles de graphes usuelles. Un graphe

est complet lorsque

. Un exemple de graphe complet est

en figure 1 .

Un graphe biparti est un graphe dont l'ensemble des sommets peut être partitionné en deux ensembles

de telle sorte que toute arête intersecte chacun de ces ensembles.

Un graphe

-régulier est un graphe dont tous les sommets ont même degré

.
Question 3.1. Justifier que tout graphe biparti de degré supérieur ou égal à 2 est dans

.
Question 3.2. Justifier que tout graphe

-régulier non complet est dans

, pour

.
Morphismes et rétractions. Un morphisme de graphe de

dans

est une fonction

dans

telle que pour tout

Une rétraction est un morphisme

d'un graphe

sur l'un de ses sous-graphes

tel que la restriction de

est l'identité. Un rétract de

est un sous-graphe

tel qu'il existe une rétraction de

dans

Question 3.3. Montrer que si

est un rétract de

, alors

est un graphe de

. En déduire que si

est un graphe de

est un rétract de

, alors

Lorsqu'il existe une paire de sommets

telle que

, on dit que

domine

et on appelle le sommet

un écueil.

Question 3.4. Montrer qu'un graphe ayant au moins deux sommets et qui n'a pas d'écueil est dans

. (Pour cela, on pourra par exemple considérer une partie de longueur au moins trois gagnée par le gendarme

et pour laquelle on suppose que le voleur joue

de manière optimale

et montrer que

domine

Question 3.5. Montrer que si

est un graphe et

un écueil de

, alors le graphe

obtenu en retirant

des sommets de

, ainsi que toutes les arêtes qui lui sont adjacentes, est dans

si, et seulement si,

Question 3.6. Montrer que

si, et seulement si, en retirant successivement des écueils (dans n'importe quel ordre), on arrive à un graphe singleton.

Figure 4 - Graphe hexagonal

Question 3.7. Montrer que le graphe hexagonal de la figure 4 est dans

, en se référant aux numéros des sommets indiqués dans la figure.

Question 3.8. Définir une fonction Caml retire_ecueil: graphe

(graphe * bool), qui prend en entrée un graphe et retourne la paire du graphe d'entrée et du booléen faux si le graphe ne contient pas d'écueil et la paire d'un graphe obtenu en retirant un écueil du graphe d'entrée et du booléen vrai, si un tel sommet existe.

Question 3.9. Donner une fonction Caml is_G1: graphe -> bool, qui prend en entrée un graphe et retourne un booléen vrai si, et seulement si, l'entrée est dans

4 Capture avec deux gendarmes : le cas des graphes planaires extérieurs

Un résultat classique dû à Aignier et Fromme assure que : dans tout graphe planaire, trois gendarmes possèdent toujours une stratégie gagnante. La présente partie établit un résultat plus accessible : on démontre que pour une sous-classe des graphes planaires, les graphes planaires extérieurs, il suffit en fait de deux gendarmes pour capturer un voleur.

Graphes planaires extérieurs. Un graphe

est un graphe planaire extérieur (GPE) s'il admet une représentation planaire telle que (i) tous les sommets sont disposés sur un cercle et que (ii) les arêtes sont représentées par des segments de droites. Une telle représentation sera appelée représentation planaire extérieure du graphe. La figure 5 fournit trois exemples de graphes planaires extérieurs. (On notera que les arcs de cercle ne font pas partie des graphes représentés.)

Question 4.1. Un sommet universel est un sommet adjacent à tous les autres sommets du graphe. Montrer que, si on ajoute un sommet universel à un graphe planaire extérieur, on obtient un graphe planaire.

Figure 5 - Trois exemples de graphes planaires extérieurs, représentés sur des cercles

Coloration des graphes planaires extérieurs

Une coloration d'un graphe est une fonction des sommets du graphe dans un ensemble fini (les couleurs) telle qu'à deux sommets adjacents on associe des couleurs distinctes. Un graphe est

-coloriable s'il existe une coloration de ce graphe avec

couleurs.

On commence par étudier une propriété de colorabilité des GPE : tout GPE est 3-coloriable.

Question 4.2. En admettant le théorème des quatre couleurs, montrer que tout GPE est 3coloriable. (Le théorème des quatre couleurs affirme que tout graphe planaire est 4-coloriable.)

Le théorème des quatre couleurs est un résultat très fort, il est donc naturel de vouloir établir la 3-colorabilité des GPE sans reposer sur un résultat aussi fort; c'est le but des questions suivantes.

Dans la question suivante, on considère un

et on fixe une représentation planaire extérieure de

. Une corde est une arête de

qui relie deux sommets non consécutifs sur le cercle. Si deux sommets

sont reliés par une corde

, on appelle longueur de

le nombre minimal de sommets sur le cercle rencontrés en allant de

(une corde est donc de longueur au moins 1).

Question 4.3. En raisonnant sur la longueur des cordes, montrer que tout graphe planaire extérieur possède un sommet de degré au plus deux.

Question 4.4. En déduire que tout graphe planaire extérieur est 3-coloriable.

Capture dans un graphe planaire extérieur

On en vient maintenant au résultat principal de cette partie : deux gendarmes suffisent à capturer un voleur dans un GPE. On commence par introduire des notions de théorie des graphes importantes dans les questions qui suivent :

Point d'articulation, biconnexité. Un point d'articulation dans un graphe

est un sommet dont le retrait augmente le nombre de composantes connexes du graphe, c'est-à-dire un sommet

tel que

a au moins une composante connexe de plus que

. Un graphe sans point d'articulation est appelé biconnexe; tout graphe peut être décomposé en ses composantes biconnexes, c'est-à-dire en ses sous-graphes maximaux biconnexes (mais il ne s'agit pas d'une partition des sommets du graphe en général).

Question 4.5. Indiquer les points d'articulation et décrire les composantes biconnexes des graphes de la figure 3.

Question 4.6. Montrer qu'un GPE est biconnexe si, et seulement si, dans toutes ses représentations planaires extérieures, deux sommets consécutifs sur le cercle sont adjacents.

Question 4.7. Montrer que tout graphe planaire extérieur biconnexe est dans

. Pour cela, (i) on distinguera le cas où tous les sommets sont de degré 2 du cas où il y a des sommets de degré au moins 3 et (ii) on exhibera une stratégie gagnante pour deux gendarmes dont la position initiale place les deux gendarmes sur un même sommet, et on identifiera une région (c'est-à-dire un ensemble de sommets) gardée par les gendarmes que chaque coup des gendarmes fera grandir.

Question 4.8. Montrer que, pour tout

, si les graphes planaires extérieurs possédant au plus

points d'articulation sont dans

alors les graphes planaires extérieurs à

points d'articulation sont également dans

. En déduire que tout GPE est dans

5 Étude du cas de plusieurs gendarmes

L'objectif de cette partie est de démontrer que, pour tout

est non vide : il existe des graphes de copnumber arbitrairement grand. On donnera deux démonstrations du résultat, l'une reposant sur l'existence de plans projectifs arbitrairement grands, l'autre sur une construction explicite de graphes de copnumber arbitraire.

Relation entre degré et copnumber pour les graphes sans 3 ni 4-cycles

Un ensemble S de sommets d'un graphe

est dit dominant si

est l'ensemble de tous les sommets de

. Dans la suite, on admettra et on utilisera la proposition suivante :

Proposition. Soient un graphe

sans 3-cycles ni 4-cycles, un sommet

et un ensemble de sommets

tels que

. On a

Question 5.1. Soit

un graphe sans 3 -cycles ni 4 -cycles. Montrer qu'un ensemble dominant contient au moins

sommets.

Question 5.2. Soit

un graphe sans 3 -cycles ni 4 -cycles. Montrer que pour tout ensemble

de (strictement) moins de

sommets, si

, il existe

tel que

Question 5.3. Déduire de la question précédente que, si

est un graphe sans 3 -cycles ni 4 -cycles, il faut, pour que les gendarmes puissent avoir une stratégie gagnante, que le nombre de gendarmes soit supérieur ou égal au degré du graphe.

Dans la suite de cette partie, on va établir de deux manières le résultat suivant :
Théorème. Il existe des graphes n-réguliers sans 3- ou 4-cycles pour n arbitrairement grand.

Plans projectifs

En vue d'établir qu'il existe des graphes nécessitant un nombre arbitraire de gendarmes, on introduit la notion de plans projectifs dont on va admettre certaines propriétés.

Un plan projectif est donné par un ensemble de points et de droites projectives satisfaisant les axiomes suivants :

(P1) Il existe une unique droite projective incidente à chaque paire de points distincts. (ou : Par deux points distincts passe une droite (projective) et une seule.)
(P2) Il existe un unique point incident à chaque paire de droites projectives distinctes. (ou: Deux droites (projectives) distinctes se coupent en un et un seul point.)
(P3) Il existe quatre points tels qu'aucune droite projective ne soit incidente à plus que deux de ces points à la fois.

On donne en figure 6 l'exemple du plan de Fano, plan projectif à sept points et sept droites projectives.

Figure 6 - Plan projectif de Fano, à 7 points et 7 droites projectives

On admet les deux résultats suivants, classiques de la théorie des plans projectifs :
Théorème (A). Étant donné un plan projectif

, il existe un entier q tel que (i)

points, (ii)

droites, (iii) il y a

points sur chaque droite projective et (iv) par chaque point il passe

droites projectives. On appelle

l'ordre du plan projectif

Théorème (B). Il existe des plans projectifs d'ordre

pour tout

puissance d'un nombre premier.

Question 5.4. Décrire chacune des sept droites projectives en utilisant les noms des points auxquels elles sont incidentes. Vérifier le théorème (A) sur le plan projectif de Fano et fournir l'ordre de ce plan projectif.

Question 5.5. En utilisant les définitions et résultats ci-dessus, montrer qu'il existe des graphes (

)-réguliers sans 3 -cycles ni 4 -cycles pour tout entier

qui est puissance d'un nombre premier. En déduire l'existence de graphes de copnumber arbitraires.

Construction directe de graphes n-réguliers, 3-coloriables, sans 3-cycles ou 4-cycles

La question précédente assure qu'il existe des graphes possédant des copnumbers arbitrairement grands mais repose sur des résultats extérieurs à la théorie des graphes (géométrie projective et théorie des corps finis). Dans les questions suivantes, on propose de démontrer le même résultat sans admettre de résultats externes.

Pour cela, on va réaliser une construction inductive (par récurrence). Il sera nécessaire de surcharger notre hypothèse de récurrence : on va non seulement construire des graphes sans 3- ou 4-cycles de degrés croissants, mais on va en outre imposer (i) leur régularité et (ii) leur 3 -colorabilité qui serviront pour montrer que la propriété est héréditaire.

Figure 7 - Un graphe 3-régulier et 3-coloriable

Question 5.6. Vérifier que le graphe

(voir figure 1) est 2-régulier, sans 3-cycles ni 4-cycles et qu'il est 3-coloriable.

Question 5.7. Le graphe de la figure 7 est 3 -régulier et 3 -coloriable. (Par convention et pour faciliter les explications, dans les raisonnements la couleur associée aux disques noirs sera 0 , la couleur associée aux disques blancs sera 1 et la couleur associée aux carrés blancs sera 2.)

En étudiant la structure du graphe, de sa 3 -coloration, et comment ce graphe est obtenu à partir de

, justifier qu'il ne possède ni 3-cycle ni 4-cycle.

Question 5.8. Montrer à partir des deux questions précédentes que pour tout

il existe des graphes

-réguliers sans 3 -cycles ni 4 -cycles qui sont 3 -coloriables et en déduire qu'il existe des graphes de copnumber arbitrairement grand.

1. La suite vide sera notée . Une suite de positions sera notée . Si est une suite de longueur et une position, on notera la suite de longueur dont le premier élément est et dont le $è$ élément est le $è$ élément de et on notera la suite dont les premiers éléments sont les éléments de , dans l'ordre, et le $è$ élément est .