modif algo euclide

[cours-maths-dis.git] / graphes / coloration.tex

\section{Présentation du problème}

\subsection{Un problème historique}

Une question datant de la mi-XIX\textsuperscript{e}, reliée à la coloration de graphes planaires, est devenue célèbre sous le nom de problème des quatre couleurs : suffit{}-il de quatre couleurs pour dessiner n'importe quelle carte géographique ?

\begin{center}
\includegraphics[scale=0.7]{graphes/europe}
\end{center}

\begin{Exo}
Prenez une feuille de papier. Tracez une droite quelconque qui traverse la feuille de part en part. Recommencez l'opération n fois.
Démontrez que la "carte" ainsi obtenue peut être colorée en deux couleurs.
\end{Exo}

\subsection{Formulation en théorie des graphes}

Ce problème a une formulation dans le langage des graphes : y a{}-t{}-il toujours, dans un graphe planaire, une application de l'ensemble $S$ des sommets vers un ensemble de cardinal 4, telle que deux sommets \og adjacents \fg{} admettent toujours des images distinctes ?


\begin{Th}[Théorème des quatre couleurs]
On peut colorer les sommets d'un graphe planaire (sans boucles) en utilisant au plus quatre couleurs de telle sorte que toutes les arêtes aient des extrémités de couleurs différentes.
\end{Th}


Cette conjecture a été formulée pour la première fois par l'Écossais Francis Guthrie en 1852. Il était alors question de coloration de carte de géographie (voir exercice ci-dessous).

La preuve de ce théorème n'arriva qu'en... 1976, grâce à Kenneth Appel et Wolfgang Haken. La démonstration fit grand bruit car c'est le premier théorème de l'histoire des mathématiques qui a nécessité l'usage systématique de l'ordinateur. Le résultat de Appel et Haken est donc délicat à prouver. 

La communauté mathématique se divisa alors en deux camps : ceux pour qui le théorème des quatre couleurs était définitivement démontré, et ceux pour qui tout restait à faire.



S'il n'est pas question ici de démontrer le théorème des quatre couleurs, on verra quand même, dans les prochaines sections, qu'un certain nombre de résultats sur le nombre de couleurs nécessaires à la coloration des sommets d'un graphe peuvent s'obtenir sans trop de difficultés. Le problème de la coloration des arêtes sera lui aussi introduit.


\section{Coloration des sommets}

Afin d'obtenir des encadrements du nombre de couleurs nécessaires à la coloration des sommets d'un graphe, il nous faut exprimer rigoureusement le problème de coloration en termes issus de notre théorie des graphes...

\subsection{Rappels sur la notion de stable}

On rappelle que l'on appelle stable d'un graphe $G = (S, A)$ tout sous-graphe sans arête obtenu en enlevant des sommets à $G$ (ce qui entraîne de fait la suppression de leurs arêtes incidentes).

\begin{Ex}
Dans le graphe suivant, on peut obtenir un stable en enlevant les sommets \{1, 2, 4\} : le graphe résultant est sans arête.
\end{Ex}

\begin{center}
\includegraphics[scale=0.7]{graphes/colo1.eps}
\end{center}


\begin{Def}[Nombre de stabilité]
Le cardinal du plus grand stable est le \emph{nombre de stabilité}\index{nombre!de stabilité} de $G$
\end{Def}

\begin{Notation}
On le note $a(G)$.
\end{Notation}

\subsection{Le problème de coloration}

\begin{Def}[Coloration des sommets d'un graphe]
La \emph{coloration des sommets}\index{coloration!des sommets} d'un gra\-phe consiste à affecter à tous les sommets de ce graphe une couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur.
\end{Def}

\begin{Th}
Une coloration avec $k$ couleurs est une partition de l'ensemble des sommets $S$ en $k$ stables.
\end{Th}


\begin{Def}[Nombre chromatique]
Le \emph{nombre chromatique}\index{nombre!chromatique} du graphe $G$ est le plus petit entier $k$ pour lequel il existe une partition de $V$ en $k$ sous-ensembles stables. C'est le nombre de couleurs minimal pour colorier un graphe.
\end{Def}

\begin{Notation}
Ce nombre chromatique est noté $g(G)$.
\end{Notation}

\begin{Exo}
Dans ce qui précède, on suppose que le nombre chromatique existe toujours. Pourquoi ?
\end{Exo}

\begin{Ex}
Sur le graphe ci-dessous, on a eu besoin de trois couleurs pour colorer les sommets de sorte que deux sommets adjacents ont des couleurs différentes.
\begin{center}
\includegraphics[scale=0.7]{graphes/colo1.eps}
\end{center}
\end{Ex}


\begin{Rem}
La coloration minimale n'est pas forcément unique. Par exemple, ci-dessus, le sommet 2 aurait aussi pu être vert.
\end{Rem}


\subsection{Encadrement du nombre chromatique}

\subsubsection{Majoration}

On donne, dans les deux propriétés suivantes, deux majorations pour le nombre chromatique. 

\begin{Th}
$g(G) \leqslant r + 1$, où $r$ est le plus grand degré de ses sommets.
\end{Th}

\begin{Pre}
Soit un graphe et $r$ le degré maximum de ses sommets. Donnons-nous une palette de ($r + 1$) couleurs. Pour chaque sommet du graphe on peut tenir le raisonnement suivant :
\begin{itemize}
\item ce sommet est adjacent à $r$ sommets au plus,
\item le nombre de couleurs déjà utilisées pour colorer ces sommets est donc inférieur ou égal à $r$.
\end{itemize}
Il reste donc au moins une couleur non utilisée dans la palette, avec laquelle nous pouvons colorer notre sommet.
\end{Pre}

\begin{Th}
$g(G) \leqslant n + 1 - a(G)$
\end{Th}

\begin{Pre}
Considérons $S$ un stable de $V$ de cardinal $a(G)$ : une coloration possible des sommets consiste à colorer les sommets de $S$ d'une même couleur et les $n-a(G)$ autres sommets de couleurs toutes différentes.

On en déduit que $g(G) \leqslant 1+(n-a(G))$.
\end{Pre}

\subsubsection{Minoration}
On a d'autres résultats, concernant la minoration...

\begin{Th}
Le nombre chromatique d'un graphe est supérieur ou égal à celui de chacun de ses sous-graphes.
\end{Th}

\begin{Pre}
Ce résultat découle de la définition même du nombre chromatique.
\end{Pre}


\begin{Th}
$g(G) \geqslant w(G)$, où $w(G)$ désigne l'ordre de la plus grande clique de $G$.
\end{Th}

\begin{Pre}
Puisque, par définition, dans une clique d'ordre $m$, tous les sommets sont adjacents entre eux, il faudra $m$ couleurs pour colorier ce sous-graphe. Donc, forcément, le nombre chromatique du graphe sera supérieur ou égal à l'ordre de sa plus grande clique.
\end{Pre}


\begin{Ex}
Dans le graphe précédant, on a utilisé trois couleurs :
\begin{center}
\includegraphics[scale=0.7]{graphes/colo1.eps}
\end{center}

On ne peut faire mieux, à cause des cliques 1-4-5 et 1-3-4.
\end{Ex}

\begin{Rem}
On peut déduire de la propriété précédente que tout graphe possédant un triangle ne peut être colorié en moins de trois couleurs.
\end{Rem}

\begin{Exo}
Que dire du nombre chromatique d'un graphe contenant un carré ? Un polygone régulier avec n sommets ?
\end{Exo}

\noindent\textbf{\textit{\underline{Réponse : }}} Il faut au minimum deux couleurs quand le nombre de sommets est pair, et trois quand il est impair. 

\begin{Exo}
Soit $G$ un graphe contenant $K_n$. Donner un minimum au nombre de couleurs nécessaires à la coloration de ses sommets.
\end{Exo}



\begin{Exo}
Déterminez un encadrement pour le nombre chromatique du graphe :
\begin{center}
\includegraphics[scale=0.7]{graphes/colo3.eps}
\end{center}

On vérifiera que ce graphe possède une clique d'ordre 4, et on en tirera les conséquences.
\end{Exo}


\subsection{Algorithme de coloration de Welsh et Powell}

Cet algorithme couramment utilisé permet d'obtenir une assez bonne coloration d'un graphe, c'est-à-dire une coloration n'utilisant pas un trop grand nombre de couleurs. Cependant il n'assure pas que le nombre de couleurs utilisé soit minimum (et donc égal au nombre chromatique du graphe).

\begin{description}
\item[Étape 1 ]

Classer les sommets du graphe dans l'ordre décroissant de leur degré.

\item[Étape 2]

En parcourant la liste dans l'ordre, attribuer une couleur libre au premier sommet $s$ sans couleur, et attribuer cette même couleur à chaque sommet qui n'est pas adjacent à $s$ (et qui n'est pas encore coloré).

\item[Étape 3]

S'il reste des sommets sans couleur, revenir à l'étape 2.
\end{description}


\begin{Exo}
Appliquer l'algorithme de Welsh et Powell pour colorier le graphe :
\begin{center}
\includegraphics[scale=0.7]{graphes/colo3.eps}
\end{center}
\end{Exo}

\subsection{Exercices}
\begin{Exo}
On a vu que tout graphe contenant un triangle ($K_3$) ne peut pas être coloré en moins de trois couleurs.

\begin{enumerate}
\item Construire un graphe sans $K_3$ qui nécessite également trois couleurs.
\item Comment, à partir du graphe précédent, construire un graphe sans $K_4$ nécessitant 4 couleurs ?
\item Un graphe sans $K_5$ nécessitant 5 couleurs ?
\end{enumerate}
\end{Exo}

\noindent\textbf{\textit{\underline{Réponse : }}} Un carré. Puis, rajouter une diagonale contenant un sommet à ce carré. Enfin, rajouter n diagonales contenant chacune un sommet.




\begin{Exo}
Comment ramener la résolution d'un carré latin à un problème de coloration de graphes ? L'algorithme de Welsh et Powell permet-il de le résoudre pour une taille 3 ? pour une taille 4 ? 
\end{Exo}

\begin{Exo}
Trouver un lien entre la résolution d'un Sudoku et un problème de coloration de graphes.
\end{Exo}




\begin{Exo}
Sept élèves, désignés par A, B, C, D, E, F et G, se sont rendus en salle machine. Le tableau suivant, construit à partir des logs, précise «qui a joué avec qui (en réseau) ».\\


\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
l'élève & A & B & C & D & E & F & G\\
\hline
a rencontré & D,E & D,E,F,G & E,G & A,B,E & A,B,C,D,F,G & B,E,G & B,C,E,F\\
\hline
\end{tabular}

\medskip
Sachant que chaque individu a trouvé un ordinateur libre pour travailler, que pouvez-vous dire du nombre minimum d'ordinateurs ?
\end{Exo}


\begin{Exo}
A, B, C, D, E, F, G et H désignent huit poissons. Dans le tableau ci-dessous, une croix signifie que les poissons ne peuvent pas cohabiter dans un même aquarium :\\
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
  & A & B & C & D & E & F & G & H \\
\hline
A &   & $\times$ & $\times$ & $\times$ &   &   & $\times$ & $\times$ \\
\hline
B & $\times$ &   &   &   & $\times$ & $\times$ & $\times$ &   \\
\hline
C & $\times$ &   &   & $\times$ &   & $\times$ & $\times$ & $\times$ \\
\hline
D & $\times$ &   & $\times$ &   & $\times$ &   &   & $\times$ \\
\hline
E &   & $\times$ &   & $\times$ &   & $\times$ & $\times$ & \\
\hline
F &   & $\times$ & $\times$ &   & $\times$ &   &   & \\
\hline
G & $\times$ & $\times$ & $\times$ &   & $\times$ &   &   & \\
\hline
H & $\times$ &   & $\times$ & $\times$ &   &   &   & \\
\hline
\end{tabular}
\end{center}

Quel nombre minimum d'aquariums faut-il?
\end{Exo}


\begin{Exo}
Un lycée doit organiser les horaires des examens. 

On suppose qu'il y a 7 épreuves à planifier, correspondant aux cours numérotés de 1 à 7, et que les paires de cours suivantes ont des étudiants communs: 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et 7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enfin 6 et 7.

Comment organiser ces épreuves de façon qu'aucun étudiant n'ait à passer deux épreuves en même temps, et cela sur une durée miminale?
\end{Exo}


\begin{Exo}
Sept agences de voyage romaines proposent des visites de monuments et lieux touristiques: le Colisée, le Forum romain, le musée du Vatican et les thermes de Caracalas. Un même lieu ne peut être visité par plusieurs groupes de compagnies différentes le même jour.

La première Compagnie fait visiter uniquement le Colisée; la seconde le Colisée et le musée du Vatican; la troisième les thermes de Caracalas; la quatrième le musée du Vatican et les thermes de Caracalas; la cinquième le Colisée et le Forum romain; la sixième le Forum romain et les thermes de Caracalas; la septième le musée du Vatican et le forum romain.

Ces agences peuvent-elles organiser les visites sur les trois premiers jours de la semaine?
\end{Exo}





\section{Coloration des arêtes}

\subsection{Présentation du problème}

La coloration des arêtes d'un graphe consiste à affecter à toutes les arêtes de ce graphe une couleur de telle sorte que deux arêtes adjacentes ne portent pas la même couleur.

\begin{Def}[Indice chromatique]
L'indice chromatique du graphe $G$ est le plus petit entier $k$ pour lequel il existe une coloration des arêtes.
\end{Def}


\begin{Notation}
On le note $c(G)$.
\end{Notation}

\begin{Ex}
Sur le graphe ci-dessous, on a eu besoin de trois couleurs pour colorer les arêtes de sorte que deux arêtes adjacentes ont des couleurs différentes.
\begin{center}
\includegraphics[scale=0.7]{graphes/coloaretes.eps}
\end{center}
\end{Ex}


\subsection{Lien avec la coloration des sommets}

\subsubsection{Présentation}

Pour colorer les arêtes d'un graphe, on peut se ramener au problème de la coloration des sommets. Il suffit pour cela de travailler non pas sur le graphe lui-même, mais sur le graphe adjoint, noté G', et que l'on définit ainsi:
\begin{itemize}
\item à chaque arête de G = (V, E) correspond un sommet de G' = (E, F)
\item deux sommets de G' sont reliés par une arête si les deux arêtes correspondantes de G sont adjacentes.
\end{itemize}

On peut ensuite appliquer par exemple l'algorithme de Welsh et Powell sur le graphe G' pour colorer ses sommets. Une fois cela fait, on colorera les arêtes de G de la même couleur que les sommets correspondants de G'.


\subsubsection{Exemple de coloration d'arêtes}
\begin{enumerate}
\item Un graphe G :
\begin{center}
\includegraphics[scale=0.7]{graphes/arete1.eps}
\end{center}


\item Son graphe adjoint G'
\begin{center}
\includegraphics[scale=0.7]{graphes/arete2.eps}
\end{center}


\item Coloration des sommets de G'
\begin{center}
\includegraphics[scale=0.7]{graphes/arete3.eps}
\end{center}

\item Coloration des arêtes de G
\begin{center}
\includegraphics[scale=0.7]{graphes/arete4.eps}
\end{center}
\end{enumerate}

\subsection{Exercice}
\begin{Exo}
Dans un tournoi d'échecs, chaque engagé doit rencontrer tous les autres. Chaque partie dure une heure.

Déterminer la durée minimum du tournoi dans le cas où le nombre d'engagés est 3, 4, 5 ou 6.
\end{Exo}


\gsaut
\centerline{\x{Fin du Chapitre}}