On sait que le problème de coloration des graphes est difficile. Cependant, il existe certaines familles de graphes pour lequel le problème de coloration est polynomial. C’est le cas pour les graphes d’intervalles que nous étudions ici.
Exercice
On considère un ensemble d’intervalle fermé $\left(I_k\right)_{k \leq n}$. On appelle graphe d’intervalles associé, noté $G=(A,S)$, le graphe de $n$ sommets où chaque sommets représente un intervalle, et deux sommets $u$ et $v$ sont connectés par une arête si et seulement si $I_u \cap I_v \neq \emptyset$.
$1.$ On considère une clique de $G$. Que peut-on dire de l’intersection des intervalles associés ?
$2.$ Donner un algorithme de coloration d’un graphe d’intervalle et prouver son optimalité.
On dit que $\mathcal{H}$ est un sous-graphe induit d’un graphe $\mathcal{G}$, si l’ensemble des sommets de $\mathcal{H}$ est un sous-ensemble de l’ensemble des sommets de $\mathcal{G}$ et que $x$ et $y$ sont liés par une arête dans $\mathcal{H}$ si et seulement si ils sont liés par une arête dans $\mathcal{G}$.
On dit qu’un graphe est un graphe parfait si le nombre chromatique de chacun de ses sous-graphes induit, est égale à la taille de la plus grande clique du sous-graphe.
$3.$ Prouver que les graphes d’intervalles sont des graphes parfaits.
Correction
$1.$ L’intersection des intervalles associés à une clique de $G$ est non vide. En effet, soit $J_1, \ldots, J_k$ une clique de $G$. Si $\displaystyle \bigcap\limits_{i\leq k} J_i = \emptyset$ alors on a $l \geq 2$ tel que $\mathcal{J} = \displaystyle \bigcap\limits_{i \lt l} J_i \neq \emptyset$ et $\displaystyle \mathcal{J} \cup J_l = \emptyset$. Autrement dit, soit l’intervalle $J_l$ termine avant que $\mathcal{J}$ commence, soit l’inverse. Par symétrie, supposons que $J_l$ se termine en premier et notons $f$ sa date de fin. Notons $d$ la date de début de $\mathcal{J}$. On a $i \lt l$ tel que $i$ commence après $d$. En effet, s’ils commençaient tous strictement avant, la date de début de $\mathcal{J}$ seraient antérieur à $d$ ce qui est absurde. De ce fait, $J_l \cup J_i = \emptyset$ ce qui contredit l’hypothèse qu’ils soient dans la même clique.
De ce fait, l’intersection des intervalles associés à une clique de $G$ est non vide. Réciproquement, si l’intersection d’un ensemble d’intervalles de $G$ est non vide, alors ils forment une clique.
$2.$ On propose l’algorithme suivant : on trie les intervalles par dates de début, puis pour tous les intervalles on lui assigne la plus petite couleur non-utilisée par un intervalle visité précédemment et qui le chevauche.
On s’assure donc que deux intervalles voisins n’ont pas la même couleur. Il s’agit donc bien d’un algorithme de coloration. Montrons maintenat qu’il est optimal.
Pour montrer que notre algorithme précédent utilise le moins de couleurs possible, il suffit de remarquer que si on assigne la couleur $c$ à un sommet alors ce sommet fait partie d’une clique de taille au moins $c$.
En effet, le nombre chromatique d’un graphe est toujours supérieur à la taille de sa plus grande clique. Si on montre que la plus grande couleur utilisée est de la taille de la plus grande clique, on aura montré qu’on ne peut utiliser moins de couleurs.
Lorsqu’on assigne une couleur $c \geq 2$ à un intervalle $\mathcal{I} = [\,d\,;\,f\,]$, cela signifie que $c-1$ intervalles $J_1, \ldots, J_{c-1}$ ayant commencé avant $\mathcal{I}$ se terminent après $d$. Donc on a :
\[\{d\} \subset \left(\bigcup\limits_{i \leq c-1} J_i\right) \cup \mathcal{I} \]
Ainsi, $\mathcal{I}$ appartient à une clique de taille au moins $c$. Donc, notre algorithme de coloration est bien optimale.
$3.$ On a montré à la question précédente que le nombre chromatique d’un graphe d’intervalle est égale à la taille de sa plus grande clique. De plus, on note que le sous-graphe d’un graphe d’intervalle est toujours un graphe d’intervalle. Il en résulte que les graphes d’intervalles sont des graphes parfaits.
Exercices en lien
- Les graphes cordaux : Une sur-famille des graphes d’intervalles.
- Le problème des 3 couleurs.