\documentclass{article}

\usepackage{tikz}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{phaistos}
\usepackage{ccicons}
\newcommand{\chien}{\PHcaptive}
\newcommand{\tang}{\PHpedestrian}

\begin{document}
\renewcommand{\labelitemi}{\tikz{\shade[shading=ball, ball color=green] (0,0) circle (.1)}}

\begin{center}
\textbf{\LARGE{Graphes à l'école}}
\end{center}

\par{La collection de graphes de l'IREM de La Réunion peut être utilisée de diverses manières en classe, selon l'âge et les centres d'intérêt des élèves. L'activité la plus simple consistant à colorier les sommets d'un graphe, est à la portée d'un élève de petite section. Des problèmes de coloriage plus complexes peuvent être abordés en cycle 3 voire au-delà, avec notamment le jeu de \emph{Col} qui se joue à deux joueurs, chacun muni d'un crayon à colorier, et un graphe. Mais on va présenter d'abord des activités qui ne sont pas basées sur le coloriage, et qui permettent de réutiliser le graphe après le jeu, contrairement aux activités de coloriage. On va donc aborder successivement
\begin{itemize}
\item Le jeu des gendarmes et du voleur
\item Les problèmes de coloration
\item Le jeu de Col (à deux joueurs)
\item La théorie mathématique des graphes
\end{itemize}
à ceci près que le quatrième point est une plaisanterie, la théorie mathématique pouvant être réservée à beaucoup plus tard !
}
\par{Mais avant les trois parties restantes, quelques définitions pour savoir de quoi on parle :
}

\bigskip


\begin{Large}
\textbf{Définitions}
\end{Large}

\par{Un \emph{graphe} est composé d'un certain nombre de \emph{sommets} reliés ou non par des \emph{arêtes}\footnote{Le vocabulaire a varié selon les auteurs; en particulier Édouard Lucas, spécialiste des mathématiques récréatives de la fin du XIXe siècle, parlait de \emph{carrefours} pour les sommets, et de \emph{routes} pour les arêtes; il assimilait donc les graphes à des cartes routières. Les arêtes rectilignes omniprésentes ci-dessous permettent donc d'éviter les sorties de route dans les virages, et surtout, on peut visualiser les jeux sur la carte routière représentée; avec la limite d'un seul personnage maximum (représenté par un pion) par carrefour.}. Chaque sommet est représenté par un cercle, chaque arête par un trait. Lorsqu'une arête joint deux sommets, ceux-ci sont dits \emph{adjacents}. Un graphe est dit \emph{planaire} s'il est possible de le dessiner sans que jamais deux arêtes ne se croisent. Par exemple le graphe suivant, appelé $K_4$, est planaire :
}

\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {};
\path (a1) edge (a2); \path (a1) edge (a3); \path (a1) edge (a4);
\path (a2) edge (a3); \path (a2) edge (a4); \path (a3) edge (a4);
\end{tikzpicture}
\end{center}

\par{Pourquoi ? Parce qu'on peut déplacer les sommets, sans casser les arêtes (supposées élastiques) de manière à obtenir cette représentation du \emph{même graphe} :}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[above of=a1] {};
\node (a3)[below left of=a1] {};
\node (a4)[below right of=a1] {};
\path (a1) edge (a2); \path (a1) edge (a3); \path (a1) edge (a4);
\path (a2) edge (a3); \path (a2) edge (a4); \path (a3) edge (a4);
\end{tikzpicture}
\end{center}

\par{Les croisements étant parfois assez mal perçus même par des adolescents, on ne traitera que de graphes planaires, sans préciser qu'ils sont planaires. Dans ce cas il est souvent possible de dessiner les arêtes sous forme de traits droits, comme dans le cas du graphe du cube ci-dessous :
}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {};
\node (b1)[above left of=a1] {};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {};
\node (b4)[below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\par{Ce graphe est constitué de 8 sommets et 12 arêtes, comme un cube, d'où son nom. En fait il s'agit d'un dessin en perspective d'un cube.}

\section{Gendarmes et voleur}

\subsection{Règle du jeu}

\par{Le pays du cube, dont on a vu ci-dessus qu'il est constitué de 8 emplacements (les sommets du graphe), a été l'objet d'un vol. On sait qui est le coupable, c'est ce hardi personnage à la démarche rapide: \tang. Trois gendarmes sont chargés de l'encercler sur un des sommets du graphe afin de l'immobiliser et ainsi, de l'empêcher de nuire. Voici donc la brigade de gendarmerie au complet: \chien \chien \chien\footnote{Ces dessins proviennent du disque de Phaistos où ils semblent avoir servi comme hiéroglyphes.}.
} 

\par{L'un des deux joueurs joue le voleur, il déplace son pion depuis le sommet où il est vers un des sommets adjacents (si possible). Mais si un sommet est occupé par un personnage, voleur ou gendarme\footnote{On propose de représenter le voleur par un jeton rouge (de honte) et chaque gendarme par un jeton bleu (comme son uniforme), les jetons pouvant servir aux problèmes de coloriage comme le jeu de Col par la suite.}, on ne peut y accéder, les sommets étant trop exigus pour permettre de placer plus d'un personnage.
}

\par{L'autre joueur a les trois gendarmes pour lui mais n'en déplace qu'un seul lorsque c'est à son tour de jouer. Un tour de jeu consiste à déplacer un pion sur une arête et pas plus. On ne peut donc pas bouger un pion en diagonale.
}

\par{Voici une position gagnante pour les gendarmes, le voleur ne pouvant plus bouger :}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {\chien};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {};
\node (b1)[above left of=a1] {\tang};
\node (b2)[above right of=a2] {\chien};
\node (b3)[below right of=a3] {};
\node (b4)[below left of=a4] {\chien};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\newpage

\par{Voici en exemple de partie :}

\begin{enumerate}
\item Position initiale; au voleur de jouer :

\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {\tang};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {\chien};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\item Aux gendarmes de jouer


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {\tang};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {\chien};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\newpage
\item Au voleur :


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {\tang};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {\chien};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\item Aux gendarmes :


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {\tang};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {\chien};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\newpage
\item Au voleur :


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {\tang};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {};
\node (b2)[above right of=a2] {\chien};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\item Les gendarmes gagnent en un coup:


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {\tang};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {};
\node (b2)[above right of=a2] {\chien};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\newpage
\item En effet le voleur ne peut plus bouger à ce stade :


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {};
\node (a2)[right of=a1] {\chien};
\node (a3)[below of=a2] {\tang};
\node (a4)[below of=a1] {\chien};
\node (b1)[above left of=a1] {};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {\chien};
\node (b4)[below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}


\end{enumerate}

\par{Des activités diverses peuvent être proposées :
\begin{itemize}
\item Dès la petite section les enfants adorent tout simplement bouger les pions, et apprennent à voir les lignes (y compris obliques) et à placer un seul pion par case.
\item Voir où placer les gendarmes et le voleur\footnote{Sur ce graphe, il y a 280 manières de placer un voleur et trois gendarmes mais certaines se ressemblent beaucoup} pour qu'il y ait une stratégie gagnante pour l'un des joueurs, et voir lequel.
\item Est-il possible de gagner ce jeu si on ne dispose que de deux gendarmes ?
\item Essayer le jeu avec d'autres graphes comme celui du dodécaèdre.
\item Classer les graphes par nombre minimum de gendarmes qui donnent une stratégie gagnante. Par exemple sur les graphes de Hajos et du Poisson, deux gendarmes suffisent pour gagner à coup sûr.
\item À quoi ressemble un graphe sur lequel un seul gendarme suffit ?
\item Même avec zéro gendarme, on peut faire un jeu à un seul joueur\footnote{commercialisé sous le nom de \textit{icosian game}, traduit en français par \og le jeu icosien d'Hamilton \fg{}, par l'astronome irlandais Rowan Hamilton, vers 1850; il s'agissait alors du graphe du dodécaèdre, comportant 20 sommets, d'où l'adjectif \emph{icosien} qui en grec signifie 20.}. Le seul pion qui reste est un voleur chargé de cambrioler les 8 sommets l'un après l'autre mais sans perdre de temps à revisiter un sommet déjà cambriolé. Un tel parcours s'appelle \emph{hamiltonien} en hommage à Rowan Hamilton qui a été un des premiers à formaliser ce genre de recherche. Voici un parcours hamiltonien sur le graphe du cube : 


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[->, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) {\tang};
\node (a2)[right of=a1] {};
\node (a3)[below of=a2] {};
\node (a4)[below of=a1] {};
\node (b1)[above left of=a1] {};
\node (b2)[above right of=a2] {};
\node (b3)[below right of=a3] {};
\node (b4)[below left of=a4] {};
\path (a1) edge (a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge[-, thick] (a4); \path (a1) edge[-,thick] (b1); \path (a2) edge[-,thick] (b2);
\path (b2) edge (b1); \path (b3) edge (b2); \path (b4) edge (b3);
\path (b1) edge[-, thick] (b4); \path (a3) edge[-,thick] (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\item Pour continuer à jouer à ce jeu, en explorant d'autres graphes, il devient vite nécessaire de \emph{créer} ses graphes. Voici un exemple de graphe créé par une élève de cycle 2\footnote{Ce n'était pas pour jouer à \og gendarmes et voleur \fg{} mais pour le \og jeu des deux parkings \fg{} dont elle est l'auteur. Voir sur le site de l'IREM pour en savoir plus sur ce jeu.} :


\begin{center}
\begin{tikzpicture}[node distance=24mm, minimum size=1.25cm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle]
\node (c) {};
\node (b1)[above left of=c] {}; \node (b2)[above right of=c] {};
\node (b3)[below right of=c] {}; \node (b4)[below left of=c] {};
\node (m1)[above of=c] {}; \node (m2)[right of=c] {};
\node (m3)[below of=c] {}; \node (m4)[left of=c] {};
\node (a1)[above left of=b1] {}; \node (a2)[above right of=b2] {};
\node (a3)[below right of=b3] {}; \node (a4)[below left of=b4] {};
\path (c) edge (b1); \path (c) edge (b2); \path (c) edge (b3); \path (c) edge (b4);
\path (c) edge (m1); \path (c) edge (m2); \path (c) edge (m3); \path (c) edge (m4);
\path (b1) edge (a1); \path (b2) edge (a2); \path (b3) edge (a3); \path (b4) edge (a4); 
\path (a1) edge (m1); \path (a2) edge (m2); \path (a3) edge (m3); \path (a4) edge (m4); 
\path (a2) edge (m1); \path (a3) edge (m2); \path (a4) edge (m3); \path (a1) edge (m4); 
\end{tikzpicture}
\end{center}


\end{itemize}
}
\newpage
\section{Coloration}

\par{Colorier un graphe, c'est colorier ses sommets (uniquement les sommets). Dans les problèmes de coloration de graphe, on s'interdit de colorier dans la même couleur, deux sommets adjacents. Alors si à l'école maternelle on peut se contenter de s'entraîner à ne pas déborder du cercle\footnote{les enfants de petite et moyenne section semblent mieux voir les sommets que les arêtes, peut-être parce que les premiers sont ronds}, ensuite on a besoin de plusieurs couleurs, par exemple 2 pour le graphe du cube :
}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1)[fill=blue!25] {};
\node (a2)[fill=red!25, right of=a1] {};
\node (a3)[fill=blue!25, below of=a2] {};
\node (a4)[fill=red!25, below of=a1] {};
\node (b1)[fill=red!25, above left of=a1] {};
\node (b2)[fill=blue!25, above right of=a2] {};
\node (b3)[fill=red!25, below right of=a3] {};
\node (b4)[fill=blue!25, below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\par{On remarque qu'il est possible de \og colorier \fg{} un sommet de façon réversible, en posant dessus un jeton ou une pastille de la couleur voulue. Ci-dessus on a utilisé 4 jetons bleus et 4 jetons rouges.
}

\par{Il est facile de colorier un graphe sans que jamais deux sommets adjacents soient de la même couleur, il suffit de \og tricher \fg{} en coloriant chaque sommet d'une couleur unique :
}


\begin{center}
\begin{tikzpicture}[node distance=16mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=8mm]
\node (a1)[fill=blue!25] {};
\node (a2)[fill=red!25, right of=a1] {};
\node (a3)[fill=green!25, below of=a2] {};
\node (a4)[fill=cyan!25, below of=a1] {};
\node (b1)[fill=magenta!25, above left of=a1] {};
\node (b2)[fill=yellow!25, above right of=a2] {};
\node (b3)[fill=black!25, below right of=a3] {};
\node (b4)[fill=gray!25, below left of=a4] {};
\path (a1) edge(a2); \path (a2) edge (a3); \path (a3) edge (a4);
\path (a1) edge(a4); \path (a1) edge (b1); \path (a2) edge (b2);
\path (b1) edge(b2); \path (b2) edge (b3); \path (b3) edge (b4);
\path (b1) edge(b4); \path (a3) edge (b3); \path (a4) edge (b4);
\end{tikzpicture}
\end{center}

\par{Les jeux de coloration de graphe deviennent donc intéressants lorsqu'on essaye de minimiser le nombre de couleurs nécessaires. Certains graphes comme celui du cube ou celui de Herschel sont particuliers de par le fait qu'il suffit de deux couleurs, si on s'y prend bien, pour les colorier correctement. On dit que leur \emph{nombre chromatique} est 2, ou qu'ils sont \emph{bipartites}. Ces graphes sont importants pour découvrir les notions de fonction, ensemble de départ et ensemble d'arrivée. Mais ils sont moins intéressants pour le jeu de Col ci-dessous, dont le principe est l'impossibilité de colorier avec seulement deux couleurs. 
}

\par{Le graphe du poisson est de nombre chromatique 3 ce qui veut dire qu'avec seulement trois couleurs, on peut colorier ses 6 sommets. C'est le cas pour la plupart des graphes planaires, une exception notable est le graphe de Goldner-Harary. Le plus petit graphe nécessitant au moins 4 couleurs est le graphe $K_4$:
}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (a1) [fill=red!25] {};
\node (a2)[fill=blue!25, above of=a1] {};
\node (a3)[fill=green!25, below left of=a1] {};
\node (a4)[fill=yellow!25, below right of=a1] {};
\path (a1) edge (a2); \path (a1) edge (a3); \path (a1) edge (a4);
\path (a2) edge (a3); \path (a2) edge (a4); \path (a3) edge (a4);
\end{tikzpicture}
\end{center}

\par{Le célèbre\footnote{parce que c'est le premier théorème qui a nécessité l'usage intensif d'un ordinateur pour sa démonstration} \emph{théorème des quatre couleurs} dit que tout graphe planaire peut être coloré à l'aide de 4 couleurs maximum, sans jamais colorier deux sommets adjacents de la même couleur.
}



\section{Col}

\par{Le jeu de \emph{Col} est dû à Colin Vout, d'où le nom du jeu qui est à la fois le début du nom de son auteur, et celui du mot \emph{coloriage}; il s'agit en effet d'un jeu basé sur le coloriage. Le principe est simple: On prend un graphe de nombre chromatique 3 ou 4 et les joueurs\footnote{Il est d'usage d'appeler les deux joueurs respectivement \emph{Bleu} et \emph{Rouge}.} colorient les sommets chacun son tour, chacun dans sa propre couleur. Mais on n'a pas le droit de colorier deux sommets de la même couleur s'ils sont adjacents, et il arrive un moment dans le jeu où tous les sommets restants sont adjacents à un sommet bleu et à un sommet rouge: Le premier joueur qui ne peut plus jouer est le perdant.
}
\newpage
\par{Voici une partie de jeu de Col sur le graphe de Hajos :
}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m) {};
\node (b)[left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[above right of=m] {};
\node (a)[above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Bleu colorie en haut :


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m) {};
\node (b)[left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[above right of=m] {};
\node (a)[fill=blue!25, above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}

\item Rouge riposte en bas à gauche (on verra plus bas pourquoi) :


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m) {};
\node (b)[fill=red!25, left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[above right of=m] {};
\node (a)[fill=blue!25, above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}
\newpage
\item Bleu joue alors en bas au milieu, de toute façon il s'est interdit lui-même de jouer ailleurs qu'en bas:


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m)[fill=blue!25] {};
\node (b)[fill=red!25, left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[above right of=m] {};
\node (a)[fill=blue!25, above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}

\item Rouge joue ceci:


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m)[fill=blue!25] {};
\node (b)[fill=red!25, left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[fill=red!25, above right of=m] {};
\node (a)[fill=blue!25, above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}


\item et gagne, puisque les deux sommets non encore coloriés sont voisins de sommets bleus.

\end{enumerate}
\newpage
\par{Noter que sur ce graphe, une partie de Col peut être beaucoup plus courte, par exemple si Bleu joue ceci\footnote{Du fait que le degré du sommet joué par Bleu est élevé, celui-ci s'est bloqué beaucoup de sommets. C'est une mauvaise idée en général, et la recherche d'une stratégie gagnante à Col est facilitée par le calcul des degrés des sommets. Ce qui permet d'introduire cette notion de façon ludique: \emph{Le degré d'un sommet est le nombre d'arêtes qui se joignent en ce sommet}. Cette notion est fondamentale en théorie des graphes.} :}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m) [fill=blue!25] {};
\node (b)[left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[above right of=m] {};
\node (a)[above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}


\par{Rouge peut alors gagner en un coup, en jouant cela :}


\begin{center}
\begin{tikzpicture}[node distance=24mm]
\tikzstyle{every path}=[-, ultra thick]
\tikzstyle{every node}=[draw=black, thick, circle, minimum size=1.25cm]
\node (m) [fill=blue!25] {};
\node (b)[left of=m] {};
\node (c)[right of=m] {};
\node (p)[above right of=b] {};
\node (n)[above right of=m] {};
\node (a)[fill=red!25, above right of=p] {};
\path (a) edge (n);\path (a) edge (p);\path (b) edge (p);
\path (b) edge (m);\path (c) edge (m);\path (c) edge (n);
\path (m) edge (n);\path (n) edge (p);\path (m) edge (p);
\end{tikzpicture}
\end{center}

\par{Chaque sommet restant est en effet voisin du sommet bleu.}

\par{En résumé, il existe une stratégie gagnante pour Rouge au jeu de Col sur le graphe de Hajos: Colorier un sommet du triangle au premier coup. 
}

\vfill

\par{Pour le jeu de Col sur le graphe du poisson, il y a aussi une stratégie gagnante pour Rouge.}

\newpage

\par{Comme précédemment, il y a beaucoup à explorer sur les jeux de Col sur d'autres graphes, et cela aussi peut mener à la création de graphes originaux, rien que pour pouvoir jouer à Col sur ces graphes. C'est le concept de \emph{jeu sérieux} qui est en œuvre là-dessus: On apprend (à voir les lignes, à percevoir les liaisons et les couleurs, à réifier les graphes) sans s'en rendre compte, en jouant.
}

\par{De plus, à la fin d'un jeu de Col, en assimilant le blanc à une troisième couleur, il semble que le graphe obtenu soit souvent correctement colorié en trois couleurs bleu-blanc-rouge, et la partie de Col peut alors être assimilée à un travail collaboratif de coloration d'un graphe, problème qui est considéré comme complexe en informatique théorique.
}
\vfill

\begin{flushright}
Alain Busser


I.R.E.M. La Réunion, 2018


\ccbysa
\end{flushright}




\end{document} 
