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é G (on dit simplement graphe dans la suite) est la donnée d'un ensemble fini de sommets (ou nouds), S_G, et d'un ensemble d'arêtes, A_G ⊆ {a ∈ P(S_G), |a| = 2}, les arêtes étant des paires non-orientées de sommets. Deux sommets v, w ∈ S_G sont dits adjacents dans G lorsque {v, w} ∈ A_G. On note V_G(v) l'ensemble des voisins d'un sommet v : V_G(v) = {w ∈ A_G|{v, w} ∈ A_G}, et on note V_G^⋆(v) = V_G(v) ∪ {v}. On généralise ces notions à des ensembles de sommets : ainsi, pour V ⊆ S_G, V_G^⋆(V) = ⋃_(v ∈ V)V_G^⋆(v).
Représentations d'un graphe dans le plan. Une représentation d'un graphe G est la donnée, dans le plan, d'un ensemble de points de même cardinal que S_G, 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 G est une suite de sommets c = (s_i)_(0 ⩽ i ⩽ n), avec n ⩾ 1 telle que ∀0 ⩽ i < n, {s_i, s_(i + 1)} ∈ A_G. On dit que n est la longueur de c; les sommets s_0 et s_n sont appelés les extrémités de c (on dit alors que le chemin relie s_0 et s_n ). Un chemin est dit simple lorsque chaque arête du graphe y est utilisée au plus une fois. Un cycle dans un graphe G est un chemin simple c = (s_i)_(0 ⩽ i ⩽ n) tel que s_0 = s_n. Un cycle de longueur n est appelé un n-cycle.
(i) C_5 :
(ii) K_5 :
(iii) P :
Figure 1 - Exemples de graphes : (i) C_5, le cycle de longueur 5, (ii) K_5, le graphe complet à 5 sommets et (iii) P, 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 u : sommet, g contient au plus un élément de la forme ( u,voisins) et u 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 g, alors g a un élément de la forme ( u,voisins) et v est un élément de voisins.
Le graphe G représenté par g a alors pour sommets les u : sommet tels que g contient un élément de la forme (u,voisins), et G a une arête reliant u et v si et seulement si voisins contient v.
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 g (et les arêtes qui lui sont adjacentes) et retourne g sinon.
2 Le jeu des gendarmes et du voleur
Le jeu est joué sur un graphe G par deux (équipes de) joueurs : d'un côté un ensemble de k > 0 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 λ ∈ {G, V} marquant quel joueur doit jouer dans cette position.
Une position des gendarmes est une paire d'un ( k + 1 )-uplet de sommets et de l'étiquette G , ce que l'on note dans la suite: (v, γ_1, …, γ_k)^G, dont v représente le sommet occupé par le voleur et les γ_i 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 k-uplet de sommets et de l'étiquette V, notée (γ_1, …, γ_k)^V (les γ_i représentant les nœuds occupés par les gendarmes au début du jeu), soit il s'agit d'une paire d'un ( k + 1 )-uplet de sommets et de l'étiquette V , notée (v, γ_1, …, γ_k)^V, dont v représente le sommet occupé par le voleur et les γ_i 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 ⊢_i = {(γ_1, …, γ_k)^V, γ_j ∈ S_G}. 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 ⊢_i comme un prédicat unaire et on notera ⊢_i(γ_1, …, γ_k)^V pour (γ_1, …, γ_k)^V ∈ ⊢_i.
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 ⊢_G définie comme suit : (v, γ_1, …, γ_k)^G⊢_G(v, γ_1^′, …, γ_k^′)^V avec v, γ_j, γ_j^′ ∈ S_G et ∀1 ⩽ i ⩽ k, γ_i^′ ∈ V_G^⋆(γ_i).
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 ⊢_V définie comme suit : P⊢_V P^′ si P = (γ_1, …, γ_k)^V, P^′ = (v, γ_1, …, γ_k)^G avec v ∈ S_G ou bien si P = (v, γ_1, …, γ_k)^V, P^′ = (v^′, γ_1, …, γ_k)^G où v^′ ∈ V_G^⋆(v).
L'ensemble des coups du jeu est donc la donnée de ⊢_i ∪ ⊢_G ∪ ⊢_V.
Parties et gain. Une partie finie est une suite (finie et potentiellement vide) de positions ^1 σ = κ_0 ⋅ κ_1⋯κ_n, 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 : ⊢_i κ_0.
Coup du voleur. Si 0 ⩽ 2p < n, on a κ_(2p)⊢_V κ_(2p + 1).
Coup des gendarmes. Si 2 ⩽ 2p ⩽ n, on a κ_(2p − 1)⊢_G κ_(2p).
Capture. Une partie finie ne peut contenir un coup de la forme (v, γ_1, …, γ_k)^λ(λ ∈ {G, V}) avec v ∈ {γ_1, …, γ_k}, que s'il s'agit du dernier coup, κ_n, 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 P 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 C_5 (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 :
v
γ_1
γ_2
γ_3
A_1
A_3
A_5
B_4
A_1
A_3
A_5
B_4
A_3
B_3
A_5
A_4
A_3
B_3
A_5
A_4
A_1
B_4
B_5
⋮
⋮
⋮
⋮
Stratégies. Une stratégie pour le voleur est une application φ^V des positions des voleurs dans les positions des gendarmes telle que, pour toute position des voleurs κ, κ⊢_V φ^V(κ). Une stratégie pour les gendarmes est la donnée d'une position initiale κ_i ∈ ⊢_i et d'une application ψ^G des positions des gendarmes dans les positions des voleurs telle que, pour toute position des gendarmes κ, κ⊢_G ψ^G(κ).
Si φ^V et ( κ_i, ψ^G ) sont respectivement des stratégies pour le voleur et les gendarmes et σ = (κ_j)_(j ∈ I) est une partie (avec I = ℕ ou I = [ [0, n] ] ), on dit que σ est jouée selon φ^V et ( κ_i, ψ^G ) si κ_0 = κ_i et ∀j ∈ I∖{0}, κ_j = φ^V(κ_(j − 1)) si j est impair, et κ_j = ψ^G(κ_(j − 1)) si j est pair.
Une stratégie ψ^G pour les gendarmes est gagnante si, pour toute stratégie φ^V du voleur, la partie jouée selon φ^V et ψ^G est finie. Une stratégie φ^V pour le voleur est gagnante si, pour toute stratégie ψ^G des gendarmes, la partie jouée selon φ^V et ψ^G est infinie.
On notera 𝒞_k l'ensemble des graphes pour lesquels k gendarmes (cops en anglais) possèdent une stratégie gagnante et ℛ_k l'ensemble des graphes pour lesquels le voleur (robber en anglais) possède une stratégie gagnante face à k gendarmes.
Un résultat classique de théorie des jeux (que l'on admettra) assure que pour tout graphe et tout entier k, il existe une stratégie gagnante soit pour les gendarmes, soit pour le voleur. En conséquence, pour tout k, (𝒞_k, ℛ_k) 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 ≪j 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 𝒞_k pour k ∈ {1, 2}.
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 k tel que k gendarmes suffisent à capturer le voleur.
La question précédente justifie l'existence du copnumber, qui est le plus petit nombre k tel que k 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 ( k = 1 )
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 G = (S_G, A_G) un graphe et S ⊆ S_G, on notera G_(|S) et on appellera sous-graphe de G (induit par S ) le graphe ( S, A ) où A est l'ensemble des arêtes de G dont les deux extrémités sont dans S (c'est-à-dire A = {a ∈ A_G|a ⊆ S} ).
Degré d'un graphe. Étant donné un graphe G, le degré d'un sommet s ∈ S_G est noté d(s) et défini comme le cardinal de {t ∈ S_G, {s, t} ∈ A_G}. Il s'agit donc du nombre d'arêtes qui ont s pour extrémité (ou du nombre des voisins de s ). Le degré d'un graphe G, noté d(G), est le degré minimal de ses sommets : d(G) = min_(s ∈ S_G)d(s).
Quelques familles de graphes usuelles. Un graphe G = (S_G, A_G) est complet lorsque A_G = {a ∈ P(S_G), |a| = 2}. Un exemple de graphe complet est K_5 en figure 1 .
Un graphe biparti est un graphe dont l'ensemble des sommets peut être partitionné en deux ensembles A et B de telle sorte que toute arête intersecte chacun de ces ensembles.
Un graphe k-régulier est un graphe dont tous les sommets ont même degré k.
Question 3.1. Justifier que tout graphe biparti de degré supérieur ou égal à 2 est dans ℛ_1.
Question 3.2. Justifier que tout graphe n-régulier non complet est dans ℛ_1, pour n ⩾ 4.
Morphismes et rétractions. Un morphisme de graphe de G dans G^′ est une fonction Φ de S_G dans S_(G^′) telle que pour tout {v, w} ∈ A_G, Φ(v) = Φ(w) ou {Φ(v), Φ(w)} ∈ A_(G^′).
Une rétraction est un morphisme Φ d'un graphe G sur l'un de ses sous-graphes G^′ tel que la restriction de Φ à S_(G^′) est l'identité. Un rétract de G est un sous-graphe G^′ tel qu'il existe une rétraction de G dans G^′.
Question 3.3. Montrer que si H est un rétract de G et H ∈ ℛ_1, alors G est un graphe de ℛ_1. En déduire que si G est un graphe de 𝒞_1 et H est un rétract de G, alors H ∈ 𝒞_1.
Lorsqu'il existe une paire de sommets (e, d) telle que V_G^⋆(e) ⊆ V_G^⋆(d), on dit que d domine e et on appelle le sommet e un écueil.
Question 3.4. Montrer qu'un graphe ayant au moins deux sommets et qui n'a pas d'écueil est dans ℛ_1. (Pour cela, on pourra par exemple considérer une partie de longueur au moins trois gagnée par le gendarme σ = κ_0 ⋅ ((v_(2i − 1), g_(2i − 1))^G ⋅ (v_(2i), g_(2i))^V)_(i ∈ [ [1, n] ]) et pour laquelle on suppose que le voleur joue ≪ de manière optimale ≫ et montrer que g_(2n − 2) domine v_(2n − 2).)
Question 3.5. Montrer que si G est un graphe et e un écueil de G, alors le graphe G^′ obtenu en retirant e des sommets de G, ainsi que toutes les arêtes qui lui sont adjacentes, est dans 𝒞_1 si, et seulement si, G ∈ 𝒞_1.
Question 3.6. Montrer que G ∈ 𝒞_1 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 𝒞_1, 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 𝒞_1.
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 G 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 k-coloriable s'il existe une coloration de ce graphe avec k 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 GPEG et on fixe une représentation planaire extérieure de G. Une corde est une arête de G qui relie deux sommets non consécutifs sur le cercle. Si deux sommets a et b sont reliés par une corde C, on appelle longueur de C le nombre minimal de sommets sur le cercle rencontrés en allant de a à b (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 G est un sommet dont le retrait augmente le nombre de composantes connexes du graphe, c'est-à-dire un sommet v ∈ S_G tel que G_(|S_G∖{v}) a au moins une composante connexe de plus que G. 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 𝒞_2. 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 n, si les graphes planaires extérieurs possédant au plus n points d'articulation sont dans 𝒞_2 alors les graphes planaires extérieurs à n + 1 points d'articulation sont également dans 𝒞_2. En déduire que tout GPE est dans 𝒞_2.
5 Étude du cas de plusieurs gendarmes
L'objectif de cette partie est de démontrer que, pour tout k, ℛ_k 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 G est dit dominant si V_G^⋆(S) est l'ensemble de tous les sommets de G. Dans la suite, on admettra et on utilisera la proposition suivante :
Proposition. Soient un graphe G sans 3-cycles ni 4-cycles, un sommet u ∈ S_G et un ensemble de sommets R ⊆ S_G tels que u ∉ R et V_G(u) ⊆ V_G^⋆(R). On a |R∖V_G(u)| ⩾ |V_G(u)∖R|.
Question 5.1. Soit G un graphe sans 3 -cycles ni 4 -cycles. Montrer qu'un ensemble dominant contient au moins d(G) sommets.
Question 5.2. Soit G un graphe sans 3 -cycles ni 4 -cycles. Montrer que pour tout ensemble R de (strictement) moins de d(G) sommets, si v ∉ R, il existe v^′ ∈ V_G^⋆(v) tel que v^′ ∉ V_G^⋆(R).
Question 5.3. Déduire de la question précédente que, si G 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 P, il existe un entier q tel que (i) P a q^2 + q + 1 points, (ii) P a q^2 + q + 1 droites, (iii) il y a q + 1 points sur chaque droite projective et (iv) par chaque point il passe q + 1 droites projectives. On appelle q l'ordre du plan projectif P.
Théorème (B). Il existe des plans projectifs d'ordre q pour tout q 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 ( q + 1 )-réguliers sans 3 -cycles ni 4 -cycles pour tout entier q 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 C_5 (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 C_5, 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 n ∈ ℕ il existe des graphes n-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.
La suite vide sera notée ε. Une suite de n + 1 positions κ_0, κ_1, …, κ_n sera notée κ_0 ⋅ κ_1⋯κ_n. Si σ est une suite de longueur n et κ une position, on notera κ ⋅ σ la suite de longueur n + 1 dont le premier élément est κ et dont le (i + 1)^(ème) élément est le i^(ème) élément de σ et on notera σ ⋅ κ la suite dont les n premiers éléments sont les éléments de σ, dans l'ordre, et le (n + 1)^(ème) élément est κ.
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)