DS 8 (MP2I 2021-2022) — Graphes d'intervalles et coloration¶

Devoir surveillé · MP2I · 2021-2022 · concours blanc · partie II du DS 8 (4 h au total)

Cours : Graphes non orientés · Algorithmes gloutons

Autres parties : I. Plus longue sous-suite commune

Corrigé

Pas de corrigé disponible pour ce sujet.

I. Graphes d'intervalles¶

On considère le problème concret suivant : certains cours doivent avoir lieu dans un intervalle de temps précis (par exemple de 8h à 9h50) et on cherche à attribuer une salle à chaque cours. On souhaite évidemment qu'à tout moment une salle ne puisse pas être attribuée à deux cours différents et on aimerait utiliser le plus petit nombre de salles possible.

Ce problème d'allocation de ressources (ici les salles) en fonction de besoins fixes (ici les horaires des cours) intervient dans de nombreuses situations très diverses (allocation de pistes d'atterrissage aux avions, répartition de la charge de travail sur plusieurs machines, etc.).

Représentation du problème¶

On modélise le problème ainsi :

chaque besoin est représenté par un segment \([a, b]\) où \(a,b\in \N\) et \(a\leq b\) ;
deux besoins \(I\) et \(J\) sont en conflit quand \(I\cap J\neq \emptyset\).

La donnée du problème est une suite finie \((I_0,\dots,I_{n-1})\) de \(n\) segments où \(n\in \N\).

Question 8

Dans le problème \((b)\) quels sont les intervalles en conflit avec \(I_5\) ?

On représente un segment en OCaml par un couple d'entiers, la donnée du problème est représentée par un tableau d'intervalles, de type (int * int) array. Dans toute la suite, on supposera toujours que les intervalles sont des segments bien formés et donc que si (a, b) : int * int représente un intervalle alors on a a <= b et cela représente toujours le segment \([a, b]\).

Le problème \((a)\) de la figure 1 est ainsi représenté par le tableau

[|(0, 3); (1, 3); (2, 5); (4, 7);
  (6, 10); (8, 9); (11, 12)|]

On cherche à écrire une fonction conflit de type int * int -> int * int -> bool qui renvoie true si et seulement si deux segments passés en paramètres sont en conflit. Voici plusieurs versions proposées par plusieurs élèves.

let conflit1 (a, b) (c, d) = (a <= c) && (c <= b)
let conflit2 (a, b) (c, d) = (a < d) && (c < b)
let conflit3 (a, b) (c, d) = not ((b < c) || (d < a))
let conflit4 (a, b) (c, d) =
  ((a <= c) && (d <= b)) || ((c <= a) && (b <= d))

Question 9

Une seule de ces versions est correcte. Laquelle ?

On suppose par la suite disposer de la version correcte de cette fonction conflit : int * int -> int * int -> bool.

Graphe simple non orienté¶

On rappelle qu'un graphe simple non orienté, que l'on appellera par la suite simplement graphe, est un couple \(G = (S, A)\) où

\(S\) est un ensemble fini dont les éléments sont appelés les sommets du graphe (ici \(S\) peut être vide) ;
\(A\) est un ensemble de paires (donc d'éléments distincts) de \(S\). Lorsque \(\{x,y\}\in A\) on dit que \(x\) et \(y\) sont reliés dans \(G\) et \(\{x,y\}\) est appelée une arête de \(G\). Les sommets reliés à un sommet \(x\) sont appelés les voisins de \(x\).

Étant donnée une énumération de \(S\) sous la forme d'une suite \((x_0,\dots,x_{n-1})\) on représente l'ensemble \(A\) en OCaml par un élément de type aretes : int list array. Ainsi pour \(i\in \{0,\dots,n-1\}\), la liste aretes.(i) contient les indices \(j\) tels que \(x_i\) soit relié à \(x_j\) dans \(G\).

Question 10

Comment s'appelle cette représentation d'un graphe ?

On représente graphiquement le graphe \(G\) par un diagramme où les arêtes sont représentées par des traits entre les sommets représentés par des cercles.

Les arêtes du graphe dont une représentation graphique est donnée à la figure 3 sont représentées en Caml par le tableau :

[|[1; 2; 3]; [0; 2; 3]; [0; 1; 3; 4]; [0; 1; 2]; [2]|]

Un tel tableau de listes d'arêtes suffit pour déterminer un graphe lorsque l'énumération des sommets est connue car on peut alors identifier un sommet à son indice. Dans la suite de ce problème on identifiera ainsi un graphe à son tableau de listes d'arêtes.

Graphe d'intervalles¶

Soit \(\overline{I}=(I_0,\dots,I_{n-1})\) une suite finie de segments, on appelle graphe d'intervalles associé à \(\overline{I}\) le graphe \(G(\overline{I})\)

dont les sommets sont les segments \(I_0,\dots,I_{n-1}\)
et où, pour \(i,j\in \{0,\dots,n-1\}\), avec \(i\neq j\) les sommets \(I_i\) et \(I_j\) sont reliés si et seulement s'ils sont en conflit.

Par exemple, le graphe d'intervalles qui correspond au problème (a) de la figure 1 admet la représentation graphique de la figure 4.

Figure 4 — Graphe d'intervalles associé au problème (a)

Question 11

Donner une représentation graphique du graphe d'intervalles pour le problème \((b)\) de la figure 2.

Question 12

Écrire en OCaml une fonction construit_graphe de type (int * int) array -> int list array qui étant donné un tableau segments des segments \(\overline{I}=(I_0,\dots,I_{n-1})\), énumérés dans cet ordre, renvoie la représentation des arêtes de \(G\). Quelle est sa complexité ?

II. Coloration d'un graphe¶

Soit \(G = (S, A)\) un graphe simple non orienté dont les sommets sont donnés par une énumération \(x_0,\dots,x_{n-1}\). On appelle coloration de \(G\) (associée à cette énumération) une suite finie d'entiers naturels \((c_0,\dots,c_{n-1})\) telle que

\[ \forall (i,j)\in \{0,\dots,n-1\}^2,\ \{x_i,x_j\}\in A\Rightarrow c_i\neq c_j \]

L'entier \(c_i\) est appelé la couleur du sommet \(x_i\) et la condition se comprend ainsi : deux sommets reliés ont des couleurs distinctes. Dorénavant, le terme couleur sera synonyme d'entier naturel. Par exemple, la suite finie \((0, 1, 2, 3, 0)\) est une coloration du graphe de la figure 3, utilisant \(4\) couleurs.

Lorsqu'une coloration utilise le plus petit nombre de couleurs distinctes possibles, on dit qu'elle est optimale. On note alors \(\chi(G)\) ce nombre minimum de couleurs, appelé le nombre chromatique de \(G\).

Remarque

En associant une salle à chaque couleur, on peut répondre au problème initial à l'aide d'une coloration de son graphe d'intervalles associé.

Question 13

Déterminer \(\chi(G)\) pour les deux graphes d'intervalles associés aux problèmes \((a)\) de la figure 1 et \((b)\) de la figure 2. Justifier rigoureusement.

Couleurs disponibles¶

Question 14

Quelle est la complexité temporelle de la fonction List.mem ?

Question 15

Écrire en OCaml une fonction plus_petit_absent : int list -> int telle que l'appel plus_petit_absent liste sur une liste d'entiers naturels liste renvoie le plus petit entier naturel non présent dans liste. Justifier que cette fonction termine. Une fonction de complexité quadratique en la taille de la liste dans le pire cas convient ici.

Question 16

Expliquer précisément comment on pourrait réaliser la fonction précédente avec une complexité linéaire en la taille de la liste dans le pire cas. On ne demande pas d'écrire la fonction en OCaml mais d'en décrire précisément l'idée.

Par la suite on suppose que la fonction plus_petit_absent réalise cette complexité linéaire dans le pire cas.

On considère une coloration progressive des sommets d'un graphe. Pour cela, une coloration partielle est un tableau couleurs : int array tel que couleurs.(i) contient la couleur de \(i\) s'il est coloré et \(-1\) sinon, ce qui ne pose pas de problème car les couleurs sont toujours positives.

Question 17

Écrire en OCaml une fonction couleurs_voisins de signature int list array -> int array -> int -> int list telle que l'appel couleurs_voisins aretes couleurs i renvoie, avec les doublons éventuels et dans un ordre quelconque, la liste des couleurs des voisins colorés du sommet d'indice \(i\) dans le graphe décrit par aretes où le tableau couleurs décrit une coloration partielle. Quelle est sa complexité ?

Question 18

En déduire une fonction couleur_disponible : int list array -> int array -> int -> int de telle manière à ce que l'appel de fonction couleur_disponible aretes couleurs i renvoie la plus petite couleur pouvant être attribuée au sommet \(i\) afin qu'il n'ait la couleur d'aucun de ses voisins dans le graphe décrit par aretes. Quelle est sa complexité ?

Colorations et cliques¶

Soit \(G = (S, A)\) un graphe. Un sous-ensemble \(C \subseteq S\) est appelé une clique de \(G\) lorsqu'il vérifie

\[ \forall x,y\in C,\ x\neq y\Rightarrow \{x,y\}\in A \]

La taille d'une clique est son nombre d'éléments. La taille de la plus grande clique de \(G\) (celle qui possède le plus d'éléments) est notée \(\omega(G)\).

Question 19

Déterminer, sans justifier, \(\chi(G)\) et \(\omega(G)\) pour un graphe \(G = (S, A)\) avec \(|S| = n > 0\) lorsque

(a) \(G\) ne possède pas d'arête (tous les sommets sont isolés) ;
(b) \(G\) est un graphe complet à \(n\) sommets ;
(c) \(G\) est un cycle à \(n\) sommets.

Question 20

Comparer \(\chi(G)\) et \(\omega(G)\) pour un graphe \(G\) quelconque. Justifier.

III. Algorithme glouton pour la coloration d'intervalles¶

Étant donnée une liste de segments \(\overline{I}=(I_0,\dots,I_{n-1})\) de longueur \(n\geq 1\), on se propose de déterminer une coloration optimale de son graphe d'intervalles associé. On appelle coloration de \(\overline{I}\) une suite finie d'entiers naturels \((c_0,\dots,c_{n-1})\) telle que

\[ \forall (i,j)\in \{0,\dots,n-1\}^2, \ I_i\cap I_j\neq \emptyset\Rightarrow c_i\neq c_j \]

On suppose dans cette partie que les segments \(I_k=[a_k,b_k]\), pour \(k\in \{0,\dots,n-1\}\), sont énumérés dans l'ordre croissant de leurs extrémités gauches, c'est-à-dire que

\[ a_0\leq a_1\leq \dots\leq a_{n-1} \]

On propose l'algorithme suivant :

Pour \(k\) variant de \(0\) à \(n-1\), colorer l'intervalle \(I_k\) avec la plus petite couleur non encore utilisée dans la coloration des intervalles \(I_j\), avec \(0\leq j<k\), qui ont une intersection non vide avec \(I_k\).

Ainsi, l'intervalle \(I_0\) est toujours coloré avec la couleur 0, l'intervalle \(I_1\) reçoit la couleur \(0\) si \(I_0\cap I_1=\emptyset\), et la couleur \(1\) sinon, etc.

L'algorithme sur un exemple¶

Question 21

Déterminer la coloration renvoyée par cet algorithme pour le problème \((b)\) décrit sur la figure 2, pour l'énumération des intervalles indiquée (qui respecte bien la contrainte demandée).

Coloration¶

Question 22

Écrire en OCaml une fonction coloration : int list array -> int array telle que l'appel coloration aretes, où aretes représente les arêtes du graphe d'intervalles associé à une liste de segments triés par ordre croissant de leurs extrémités gauches, renvoie la coloration obtenue avec l'algorithme ci-dessus.

Question 23

Déterminer très soigneusement la complexité de la fonction précédente en fonction du nombre \(n\) d'intervalles et du nombre \(m\) d'arêtes du graphe d'intervalles associé à la liste \(\overline{I}\).

Preuve de l'algorithme¶

On se propose maintenant de démontrer que l'algorithme ci-dessus fournit une coloration optimale de l'ensemble des segments. Soit \(k\) un entier entre \(0\) et \(n-1\). On suppose qu'à la \(k\)-ième étape de l'algorithme, le segment \(I_k = [a_k, b_k]\) reçoit la couleur \(c\).

Question 24

Montrer que \(I_k\) a au moins \(c\) voisins d'indices inférieurs à \(k\), c'est-à-dire parmi \(I_0,\dots,I_{k-1}\).

Question 25

Montrer que l'ensemble constitué de \(I_k\) et de ses voisins d'indice inférieur à \(k\) constitue une clique de taille au moins \(c+1\) dans le graphe d'intervalles associé. On pourra raisonner sur l'extrémité gauche \(a_k\) du segment \(I_k\).

Question 26

En déduire que le nombre de couleurs nécessaires à une coloration de l'ensemble des segments est au moins égal à \(c+1\).

Question 27

Conclure.

IV. Coloration gloutonne¶

L'algorithme de coloration étudié dans la partie précédente s'applique plus généralement à tout graphe étant donné une énumération \((x_0,\dots,x_{n-1})\) des sommets :

pour \(i\) allant de \(0\) à \(n-1\), on colore \(x_i\) avec la plus petite couleur qui ne soit pas utilisée par un de ses voisins déjà colorés.

On appelle coloration gloutonne d'un graphe \(G = (S, A)\) une coloration obtenue par application de l'algorithme ci-dessus, ce qui dépend uniquement de l'énumération des sommets choisie. Ainsi, si \(|S| = n\), chacune des \(n!\) façons d'ordonner les sommets du graphe induit une coloration gloutonne des sommets du graphe.

Question 28

Montrer qu'une coloration gloutonne n'est pas toujours optimale. On donnera un contre-exemple sous la forme d'un graphe, d'une énumération de ses sommets, de la coloration gloutonne associée et du nombre chromatique de ce graphe (qui ne sera donc pas le même que le nombre de couleurs utilisées par la coloration gloutonne).

Question 29

Montrer qu'il existe des colorations optimales qui ne sont pas des colorations gloutonnes. On donnera à nouveau un contre-exemple sous la forme d'un graphe et d'une coloration associée et on justifiera rapidement que cette coloration ne saurait être une coloration gloutonne.

L'algorithme de coloration glouton pour une énumération des sommets ne donne pas, en général, une solution optimale. Cependant, il existe toujours une énumération des sommets qui fournit une coloration gloutonne optimale.

Propriété

Soit un graphe \(G = (S, A)\). Il existe une énumération \((x_0,\dots,x_{n-1})\) des sommets de \(G\) telle que la coloration gloutonne calculée à partir de cet ordre soit optimale.

On se propose de démontrer cette proposition. Considérons une coloration valide du graphe \(G\) utilisant \(k\) couleurs numérotées de \(0\) à \(k - 1\) et notons, pour \(i \in \{0, \dots, k - 1\}\), \(C_i\) l'ensemble des sommets de \(G\) auxquels a été affectée la couleur \(i\) dans cette coloration. Considérons une énumération des sommets de \(G\) qui respecte l'ordre sur les classes \(C_i\), c'est-à-dire telle que si \(0 \leq i < j \leq k - 1\), tout sommet de couleur \(i\) est classé avant tout sommet de couleur \(j\). Considérons maintenant la coloration gloutonne obtenue avec cet ordre.

Question 30

Montrer que, pour \(i \in \{0, \dots, k - 1\}\), lorsque l'algorithme glouton affecte une couleur \(c\) à un sommet \(x\) de la classe \(C_i\), cette couleur \(c\) ne peut être qu'inférieure ou égale à \(i\).

Question 31

Montrer que cette coloration gloutonne utilise au plus \(k\) couleurs.

Question 32

Conclure.

Il suffit donc de calculer les colorations gloutonnes associées à toutes les énumérations possibles des sommets pour trouver le nombre chromatique d'un graphe.

Question 33

Que pensez-vous de cette approche ?

Trouver un ordre sur les sommets d'un graphe tel que la coloration gloutonne associée à cet ordre soit optimale est un problème difficile que l'on ne sait pas résoudre de manière efficace, du moins dans le cas général.

V. Graphes munis d'un ordre d'élimination parfait¶

On introduit ici la notion d'ordre d'élimination parfait, dont on montre qu'il existe toujours pour un graphe d'intervalles, et pour lequel l'algorithme glouton donne toujours une solution optimale.

Figure 5 — Un exemple de graphe admettant un ordre d'élimination parfait

Soient \(G = (S, A)\) un graphe et \((x_0,\dots,x_{n-1})\) une énumération des sommets de \(G\). Pour tout \(i\in \{0,\dots,n-1\}\), on note \(G_i=(S_i,A_i)\) où \(S_i=\{x_0,\dots,x_i\}\) et

\[ \forall k,l\in \{0,\dots,n-1\},\ \{x_k,x_l\}\in A_i\iff (k,l\leq i\ \text{ et }\ \{x_k,x_l\}\in A) \]

\(G_i\) est ainsi le graphe déduit de \(G\) en se restreignant aux sommets de \(x_0\) à \(x_i\).

Une énumération \((x_0,\dots,x_{n-1})\) des sommets de \(G\) est appelée un ordre d'élimination parfait si pour tout \(i\in \{0,\dots,n-1\}\), les voisins de \(x_i\) d'indices inférieurs à \(i\) (c'est-à-dire apparaissant avant \(i\) dans l'énumération) forment une clique (c'est-à-dire sont tous reliés).

Par exemple, dans la figure 5, l'énumération \((a,b,c,d,e,f)\) est bien un ordre d'élimination parfait alors que \((b,c,e,d,f,a)\) ne l'est pas puisque \(d\) y est précédé de \(e\) et \(c\) qui sont tous deux voisins de \(d\) sans être reliés.

Un exemple¶

Figure 6 — Graphe dont on demande dans la question suivante de déterminer des ordres d'élimination parfaits

Question 34

Déterminer, sans justifier, parmi les exemples proposés lesquels sont bien des ordres d'élimination parfaits pour le graphe \(G\) donné par la figure 6 :

(a) \((a,b,c,d,e,f,g,h)\).
(b) \((a,c,b,d,f,g,h,e)\).
(c) \((a,b,e,c,f,h,g,d)\).
(d) \((b,c,e,f,a,g,d,h)\).

Question 35

Montrer qu'il existe des graphes qui n'admettent aucun ordre d'élimination parfait. On donnera un contre-exemple sous la forme d'un graphe et l'on justifiera rapidement.

Validation d'un ordre d'élimination parfait¶

Dans cette partie, les fonctions devront être écrites en C. Pour cela, un graphe à \(n\) sommets et de degré maximum \(d\) sera représenté par un tableau statique g à \(n\) lignes et \(d+1\) colonnes où chaque ligne i du tableau g est un tableau g[i] contenant dans sa première case g[i][0] le degré \(d_i\) du sommet \(i\), puis, dans les cases indices \(1\) à \(d_i\), et dans un ordre arbitraire, les indices des voisins de \(i\). On n'accèdera donc pas aux cases d'indices strictement supérieurs à \(d_i\) pour un sommet \(i\), qui peuvent contenir une valeur non initialisée.

Par exemple, le graphe de la figure 3 peut être représenté par :

int g[5][4] = {
    {3, 1, 2, 3},
    {3, 0, 3, 2},
    {3, 0, 1, 3},
    {3, 0, 1, 2},
    {1, 2}
};

On remarquera qu'ici encore, une fois que la représentation d'un graphe est choisie, elle implique une énumération des sommets dont on cherchera ici à déterminer si elle correspond ou non à un ordre d'élimination parfait.

Étant donné un graphe \(G = (S ,A)\) et un ensemble \(S'\subseteq S\) de sommets de \(G\), le sous-graphe de \(G\) induit par \(S'\) est le graphe \(H = (S',A')\) où \(A'\subseteq A\) est l'ensemble des arêtes de \(G\) dont les extrémités appartiennent à \(S'\). On pourra identifier le sous-graphe \(H = (S',A')\) avec l'ensemble de sommets \(S'\).

Un graphe \(G = (S, A)\) à \(|S| = n\) sommets est représenté en C par un tableau bidimensionnel g. On représente en C un sous-graphe induit \(H = (S',A')\) d'un graphe \(G = (S, A)\) possédant \(n\) sommets par la donnée du graphe d'origine g et d'un tableau de booléens sommets à \(n\) cases dont la case \(i\) vaut true si et seulement si le sommet d'indice \(i\) est un sommet du sous-graphe induit et false sinon. On représente de même un sous-ensemble \(S' \subseteq S\) de sommets du graphe par un tableau de booléens de taille \(n\) indiquant pour chaque sommet de \(S\) sa présence dans \(S'\) ou non.

Attention

Dans toute cette partie \(n\) et \(d\) seront des constantes globales.

Question 36

Écrire en C une fonction de type void voisins_inferieurs(int g[n][d + 1], int x, bool voisins_inf[n]) telle que l'appel voisins_inferieurs(g, x, voisins_inf) met à jour le tableau de booléens voisins_inf pour qu'il représente l'ensemble des voisins du sommet x d'indices strictement inférieurs à celui de x. On ne présupposera rien sur le remplissage initial du tableau voisins_inf. On garantira une complexité linéaire en \(|S| = n\).

Question 37

Écrire en C une fonction de type bool est_clique(int g[n][d + 1], bool sommets[n]) telle que l'appel est_clique(g, sommets) renvoie true si et seulement si l'ensemble de sommets représenté par le tableau de booléens sommets forme une clique de g, c'est-à-dire que le sous-graphe de g engendré par ces sommets est complet. On garantira une complexité linéaire en \(|S| + |A|\). Indication : calculer en temps linéaire la taille et le nombre d'arêtes du sous-graphe.

Question 38

Écrire en C une fonction de signature bool est_ordre_parfait(int g[n][d + 1]) telle que est_ordre_parfait(g) renvoie true si et seulement si l'énumération associée au graphe représenté par g est un ordre d'élimination parfait. Quelle est sa complexité ?

Ordre d'élimination parfait pour un graphe d'intervalles¶

Question 39

Justifier rapidement qu'un graphe d'intervalles admet un ordre d'élimination parfait. Indication : on en a explicité un dans la partie III.

Ordre d'élimination parfait¶

Un sommet \(v\) d'un graphe \(G\) est dit simplicial lorsque l'ensemble des voisins de \(v\) dans \(G\) est une clique.

Question 40

Quels sont les sommets simpliciaux du graphe de la figure 5 ?

Question 41

Écrire une fonction de type bool simplicial(int g[n][d + 1], bool sg[n], int k) telle que l'appel simplicial(g, sg, k), où le sommet d'indice \(k\) est supposé appartenir au sous-graphe induit \(H\) décrit par (g, sg), renvoie true si le sommet d'indice \(k\) est simplicial dans \(H\) et false sinon. Déterminer la complexité de la fonction simplicial.

Question 42

Écrire une fonction int trouver_simplicial(int g[n][d + 1], bool sg[n]) telle que trouver_simplicial(g, sg) renvoie, s'il en existe, un sommet simplicial du sous-graphe induit décrit par (g, sg) et sinon renvoie l'entier relatif \(-1\). Déterminer la complexité de cette fonction.

Question 43

Montrer que si un graphe \(G = (S, A)\) possède un ordre d'élimination parfait, alors pour tout sommet simplicial \(x\) de \(G\), le sous-graphe \(H = (S', A')\) engendré par \(S' = S \setminus \{x\}\) en possède également un.

Question 44

Écrire une fonction int *ordre_parfait(int g[n][d + 1]) telle que l'appel ordre_parfait(g) renvoie un ordre d'élimination parfait du graphe décrit par g, s'il en existe un et NULL sinon. Déterminer la complexité de la fonction ordre_parfait.