\documentclass[a4paper, 11pt]{article}
\usepackage[utf8]{inputenc} 
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{graphicx}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{stmaryrd}
\usepackage{algpseudocode}
\usepackage{fullpage}
\usepackage{tikz}
\usepackage[trim]{tokenizer}
\usepackage{enumitem}
\usetikzlibrary{snakes,arrows,shapes}

\begin{document}

\title{Coloration de graphes}
\author{Paul Melotti}
\date{juin 2014}
\maketitle
Un \textit{graphe} $G$ est un couple $(V,E)$ où $V$ est un ensemble fini d'éléments appelés \textit{sommets}, et $E$ un ensemble de paires non ordonnées $(v,w)$ où $v,w \in V$ et $v \neq w$, appelées arêtes. Deux sommets sont dits \textit{adjacents} s'il existe une arête les reliant.

Le problème du coloriage de graphe consiste à assigner à chaque sommet une couleur, de façon à ce que deux sommets adjacents soient de couleurs différentes. Si c'est possible avec $k$ couleurs, on dit que le graphe est $k$\textit{-coloriable}.

\begin{enumerate}
\item Quelle structure informatique utiliser pour représenter un graphe ?
\end{enumerate}
\section{2-coloriages}
Le graphe $G$ est dit \textit{biparti} si $V$ se partitionne en deux ensembles $B$ et $W$, tels que toute arête de $E$ relie un sommet de $B$ à un sommet de $W$.
\begin{enumerate}[resume]
\item Montrer qu'un graphe est 2-coloriable si et seulement si il est biparti.
\item Donner un algorithme qui, lancé sur un graphe biparti, détermine une 2-coloration de ce graphe. Quelle est sa complexité ? La réponse peut dépendre de la structure de donnée considérée.
\item Montrer qu'un graphe est 2-coloriable si et seulement si il ne possède pas de cycle de longueur impaire.
\end{enumerate}

\section{Algorithme glouton}
Le problème du 2-coloriage est donc ``facile''. On va s'intéresser maintenant aux $n$-coloriages pour $n \geq 3$, ce qui est beaucoup plus difficile. Le problème consiste à colorier le graphe avec un nombre minimal de couleurs.

On représente les couleurs par les entiers $1,2,\dots,K,\dots$. On appelle \textit{degré} d'un sommet $v$ le nombre de ses voisins, et on le note $\delta (v)$. On appelle degré du graphe $G$ le maximum des $\delta(v)$ pour $v \in V$, et on le note $\Delta(G)$.

L'algorithme glouton consiste à trouver un coloriage du graphe de la façon suivante : on numérote les sommets $v_1, \dots, v_n$ de $G$, puis on les colorie dans cet ordre en attribuant à chaque sommet la plus petite couleur disponible (\textit{i.e.} non déjà utilisée par ses voisins). On appelle $gl(G)$ le nombre total de couleurs utilisées par cet algorithme.
\begin{enumerate}[resume]
\item Montrer que $gl(G) \leq \Delta(G) + 1$.
\item Montrer qu'on a en fait $gl(G) \leq \max_{i=1}^{n} \min (\delta(v_i) + 1, i)$.
\item Quelle numérotation des sommets cette inégalité suggère-t-elle d'utiliser ?
\end{enumerate}

L'algorithme glouton est optimal pour une famille de graphes, les \textit{graphes d'intervalles}. Étant donné une famille d'intervalles sur la droite réelle, on définit un graphe dont les sommets sont les intervalles et dont les arêtes relient les sommets représentant des intervalles qui s'intersectent. Exemple :
\begin{figure}[!h]
\centering
\includegraphics[scale=0.3]{interv.jpg}
\end{figure}

On numérote les sommets de ce graphe selon l'ordre donné par les extrémités gauches des intervalles. Dans notre exemple, cela donne $a,b,c,d,e,f,g$.
\begin{enumerate}[resume]
\item Faire tourner l'algorithme à la main sur cet exemple
\item Montrer que cet algorithme est optimal (\textit{i.e.} utilise le nombre minimal de couleurs) pour tout graphe d'intervalles.
\end{enumerate}

\section{Algorithme de Brelaz}
On propose ici une variante de l'algorithme précédent. À un moment quelconque de l'exécution de l'algorithme, on appelle \textit{degré-couleur} d'un sommet le nombre de couleurs déjà utilisées pour colorier ses voisins (attention, ce n'est pas le nombre de voisins déjà coloriés : certains peuvent avoir la même couleur). Initialement, le degré-couleur de chaque sommet est nul puis il évolue jusqu'à ce que le graphe soit colorié. Plus précisément, l'algorithme de Brelaz fonctionne de la façon suivante :

\textbf{Initialisation :} trier les sommets par degré décroissant. Choisir un sommet de degré maximal et lui assigner la couleur 1.

\textbf{Régime permanent :} tant qu'il reste des sommets non coloriés, choisir un sommet non colorié de degré-couleur maximal, et en cas d'égalité prendre parmi ceux-ci un sommet de degré maximal. Le colorier avec la plus petite couleur admissible.
\begin{enumerate}[resume]
\item Faire tourner l'algorithme à la main sur l'exemple suivant :
\begin{figure}[!h]
\centering
\includegraphics[scale=0.3]{graphe.jpg}
\end{figure}
\item Montrer que sur un graphe biparti, l'algorithme de Brelaz n'utilise que deux couleurs. Est-ce le cas de l'algorithme glouton vu précédemment ?
\end{enumerate}
\medskip

Les algorithmes que nous avons vus sont polynomiaux, mais ils peuvent utiliser un nombre non-optimal de couleurs. On ne connaît pas d'algorithme polynomial qui trouve un coloriage optimal dans le cas général, c'est un problème NP-complet.
\end{document}
