Centrale Informatique optionnelle MP 2015

Thème de l'épreuve Coloration d'un graphe d'intervalles
Principaux outils utilisés graphes, programmation, complexité

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Énoncé obtenu par reconnaissance optique des caractères


(. '» Option informatique ""

%, FI
_/ MPQ

cnucnuns EENTHHLE--SUFËLEE 4 heures Calculatrices autorisées N

Les candidats devront répondre aus: questions de programmation en utilisant le 
langage Caml. Ils devront donner
le type, ou la signature, de chaque fonction écrite, sauf lorsqu'il est indiqué 
par le sujet : dans ce cas la réponse
doit être d'un type compatible avec la signature proposée. Par eæemple, la 
fonction cons définie par

letconsxl=x:zl

est du type 'a --> 'a list --> 'a list qui est compatible avec la signature int 
--> int list --> int list.
L'énoncé indique la signature attendue, toute réponse de type compatible est 
acceptée.

I Graphes d'intervalles

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

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, ....)

I.A -- 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 EUR IN et a < b ;

-- deux besoins 1 et J sont en conflit quand 1 0 J % (b.

La donnée du problème est une suite finie (IO, ----,In_1) de n segments où n 
EUR IN*.

16 :_= Ï6 :_
Ï3 ° ° l4 _--
Ï2 Ï2 5--5 Ï5 _
Ï1: : : 5 ; :Ï5r--t ; ; Â): Ï :Ï3r--------F--+--f Ë Ë Ë% r--+--------
0123456789101112 0123456789101112131415
Problème a Problème b

Figure 1 Deux exemples de problèmes

On représente un segment en Caml par un couple d'entiers, la donnée du problème 
est une valeur du type
(int*int) vect. Le problème a de la figure 1 est représenté par le tableau

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

I.A.1) Écrire une fonction ayant pour signature

conflit : int * int --> int * int --> bool

telle que conflit I J renvoie true si et seulement si 1 et J sont en conflit.

I.B -- Graphe simple non orienté

On appelle graphe simple non orienté un couple G = (S, A) où

-- S est un ensemble fini dont les éléments sont appelés les sommets du graphe ;

-- A est un ensemble de paires d'éléments distincts de S . Lorsque {x,y} EUR A 
on dit que a: et y sont reliés
dans G et {as, y} est appelée une arête de G. Les sommets reliés à un sommet sc 
sont appelés les voisins de sc.

Étant donnée une énumération de S' sous la forme d'une suite finie (sc... ---, 
xn_1) on représente A en Caml par

un élément du type int list vect ainsi: pour i E {O, ---,n -- 1}, la liste A. 
(i) contient les j tels que a:,» soit

relié à % dans G.

On représente graphiquement le graphe G par un diagramme où les arêtes sont 
représentées par des traits entre

les sommets.

2015-03--16 13:26:27 Page 1/6

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

[I [1:2;31; [0:2;3]; [0;1;3;4]; E0;1;21; [2] |]

Une telle liste d'arêtes suffit pour déterminer un graphe lorsque l'énumération 
des sommets est connue car on
peut alors identifier un sommet a son indice. Dans la suite de ce problème on 
identifiera ainsi un graphe a sa
liste d'arêtes.

I. C' -- Graphe d 'intervalles

Soit Î = (IO, ..., In_1) une suite finie de segments, on appelle graphe 
d'intervalles associé à Î le graphe G(Î)

-- dont les sommets sont les segments IO, ...,In_1

-- et où, pour i, j E {O, ..., n-- 1}, avec i % j , les sommets I,-- et I, sont 
reliés si et seulement si ils sont en conflit.
Le graphe d'intervalles qui correspond au problème a de la figure 1 admet la 
représentation graphique de la
figure 3.

@
o'ee @@.

Figure 3

I.C.1) Donner une représentation graphique du graphe d'intervalles associé au 
problème b de la figure 1.

I.C.2) Écrire une fonction ayant pour signature
construit_graphe : (int * int) vect --> int list vect

qui étant donné le tableau des segments Î : (IO, ..., I

n_1), énumérés dans cet ordre, renvoie la représentation
des arêtes de G(I )

I. D -- Coloration

Soit G = (S', A) un graphe simple non orienté dont les sommets sont 950, 
...,xn_1. On appelle coloration de G
une suite finie d'entiers naturels (co, ..., cn_1) telle que

V(Z,j) EUR {0,...,n--1}2, {OE,,OEj} EURA=>C, #Cj

L'entier c, est appelé la couleur du sommet a:, et la condition se traduit 
ainsi: deux sommets reliés ont des
couleurs distinctes. Dorénavant, le terme couleur sera synonyme d'entier 
naturel.

La suite finie (O, 1, 2, 3,0) est une coloration du graphe de la figure 2.

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

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

I.D.l) Déterminer des colorations optimales pour les graphes d'intervalles 
associés aux deux problèmes de la
figure 1. On attribuera a chaque fois la couleur 0 a l'intervalle IO.

I.D.2) Couleur disponible

a ) Écrire une fonction de signature
appartient : int list --> int --> bool

telle que l'appel à appartient 1 X envoie true si et seulement si l'entier :c 
est présent dans la liste 1 .
b) Écrire une fonction de signature

plus_petit_absent : int list --> int

telle que l'appel à lus_ etit_absent l renvoie le plus petit entier naturel non 
présent dans 1.
P P

2015-03--16 13:26:27 Page 2/6

c ) On considère ici une coloration progressive des sommets d'un graphe. Pour 
cela, une coloration partielle est
un tableau couleurs : int vect 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.

Ecrire une fonction de signature
couleurs_voisins : int list vect --> int vect --> int --> int list

telle que l'appel à couleurs_voisins aretes couleurs i renvoie 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.

d) En déduire, une fonction de signature
couleur_disponible : int list vect --> int vect --> int --> int

telle que l'appel à couleur_disponible aretes couleurs i renvoie la plus petite 
couleur pouvant être attri--
buée au sommet i afin qu'il n'ait la couleur d'aucun de ses voisins dans le 
graphe décrit par aretes.

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

Voe,yEURG, x#y=>{oe,y}6A

Le nombre d'éléments de C est appelé sa taille. La taille de la plus grande 
(celle qui possède le plus grand
nombre d'éléments) clique de G est notée w(G).

I.E.1) Déterminer x(G) et w(G) lorsque

(1) G ne possède pas d'arête (c'est à dire A = (D).

(J) G est un graphe complet à n sommets, c'est à dire |S| : n et pour tous u,v 
EUR S distincts, {u,v} EUR A.
I.E.2) Comparer x(G) et w(G) pour un graphe G quelconque.

I.E.3) Écrire une fonction de signature

est_clique : int list vect --> int list --> bool

telle que est_clique aretes xs renvoie true si et seulement si la liste xs est 
une liste d'indices de sommets
formant une clique dans le graphe décrit par aretes.

II Algorithme glouton pour la coloration

Étant donnée une liste de segments Î = (10,11, ..., In_1) de longueur n > 1, on 
se p_ropose de déterminer une

coloration optimale de son graphe d'intervalles associé. On appelle coloration 
de 1 une suite finie d'entiers
naturels (c... ...,cn_1) telle que

On suppose dans cette partie que les segments I k = [a... bk], pour k E {O, 
...,n -- 1}, sont énumérés dans l'ordre
croissant de leur extrémités gauches, c'est-à-dire que

a() < (11 < < an_1

On propose l'algorithme suivant :

Pour k variant de 0 a n -- 1, colorer l'intervalle Ik avec la plus petite 
couleur non encore
utilisée dans la coloration des intervalles I], avec 0 < j < k, qui ont une 
intersection non
vide avec Ik.

Ainsi, l'intervalle Ï0 est toujours coloré avec la couleur 0, l'intervalle Il 
reçoit la couleur 0 si [0 0 Il : (Z), et la
couleur 1 sinon, etc.

II.A -- L'algorithme sur un eoeemple
Déterminer la coloration renvoyée par l'algorithme pour le problème b décrit 
sur la figure 1.

II .B -- Coloration

Ecrire une fonction de signature

coloration : (int * int) vect --> int list vect --> int vect

2015-03-16 13:26:27 Page 3/6

telle que l'appel coloration segments aretes, où segments est un tableau 
contenant des segments triés par
ordre croissant de leurs extrémités gauches et où aretes représente les arêtes 
du graphe d'intervalles associé à
ces segments, renvoie la coloration obtenue avec l'algorithme ci-dessus.

II.C -- Preuve de l'algorithme

On se propose maintenant de démontrer que l'algorithme ci-dessus fournit une 
coloration optimale de l'ensemble
de 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
reçoit la couleur c.

II.C.1) L'extrémité gauche du segment Ik appartient a un certain nombre de 
segments parmi 10,11, ...,Ik_1.
Combien au moins ?

II.C.2) Prouver 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é.

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

II.C.4) Conclure.

II .D -- Compleæité

Déterminer la complexité de la fonction coloration en fonction du nombre m 
d'arêtes du graphe d'intervalles
associé à la liste I.

III Graphes munis d'un ordre d'élimination parfait

On introduit ici la notion d'ordre d'élimination parfait, dont on montre qu'il 
eæiste toujours pour un graphe
d'intervalles, et qui permet de proposer un algorithme glouton pour le problème 
de la coloration d'un graphe.

Soient G = (S, A) un graphe et (930, ...,oen_1) une énumération des sommets de 
G. Pour tout i E {O, ..., n -- 1}
on note G,-- : (S,,A,) où S', : {as... ..,a:,} et

Vk,l EUR {O,...,n--1}, {oek,xl} EUR A,-- (=> k < i et l < i et {xk,xl} EUR A

G,» est ainsi le graphe déduit de G en se restreignant aux sommets de 930 a 
:c,--.

Une énumération (a:... ...,xn_1) des sommets de G est appelée un ordre 
d'élimination parfait si pour tout i E
{O, ..., n -- 1} les voisins de a:,-- d'indices inférieurs à i forment une 
clique.

III.A -- Un eoeemple
Déterminer un ordre d'élimination parfait pour le graphe G donné par la 
représentation de la figure 4.

III. B -- Vérification

III.B.1) Écrire une fonction de signature
voisins_inferieurs : int list vect --> int --> int list

telle que voisins_inferieurs aretes x renvoie la liste des voisins du sommet 
d'indice 93 dont l'indice est
strictement inférieur a a:.

III.B.2) Écrire une fonction de signature

est_ordre_parfait : int list vect --> bool

telle que est_ordre_parfait aretes renvoie true si et seulement si 
l'énumération associée au graphe représenté
par aretes est un ordre d'élimination parfait.

III.C -- Ordre d'élimination parfait pour un graphe d 'intervalles

Montrer que l'énumération des segments (IO, ..., In_1) obtenue en les triant 
par leurs extrémités gauches en ordre

croissant est un ordre d'élimination parfait de leur graphe d'intervalles.

III .D -- Coloration
On considère un graphe dont (a:... ..., oen_1) est une énumération des sommets.

2015-03--16 13:26:27 Page 4/6

On colore ce graphe à l'aide l'algorithme suivant :

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

III.D.1) Appliquer cet algorithme de coloration au graphe G de la figure 4 muni
a) de l'ordre (a:... ...,oe7) ;
b ) d'un ordre d'élimination parfait.

III.D.2) Écrire une fonction de signature

colore : int list vect --> int vect

telle que l'appel à colore aretes renvoie selon cet algorithme un tableau c 
représentant une coloration valide
du graphe décrit par aretes où la couleur du i-ème sommet est donnée par c. (i).

III.D.3) Soit (co, ..., cn_1) la coloration obtenue par cet algorithme pour un 
graphe G dont l'énumération des
sommets est un ordre d'élimination parfait.

a) Montrer que pour tout i E {O, ...,n -- 1} on a x(G) ; 1 + c,.
b ) En déduire que l'algorithme de coloration renvoie une coloration optimale.

IV Ordre d'élimination parfait pour un graphe cordal

On s'intéresse ici a une nouvelle condition sufiisante pour qu'un graphe 
admette un ordre d'élimination parfait,
qui s'exprime en considérant les cycles de longueur au moins égale à 4 du 
graphe considéré.

Un graphe G est dit cordal lorsque pour tout cycle G = (u0,u1, ...,un_1,v0) de 
G de longueur n > 4, il existe
i, j distincts entre 0 et n -- 1 tels que les sommets u, et uj soient reliés 
dans le graphe G mais non successifs
dans le cycle. Une telle arête {v,,uj} est appelée une corde du cycle G . 
Autrement dit, le graphe G est cordal
lorsque tout cycle de G de longueur supérieure ou égale à 4 possède une corde.

I V.A -- Cycles de longueur 4 dans un graphe d'intervalles

Soit G un graphe d'intervalles. Dans cette question, on se propose de démontrer 
par l'absurde que tout cycle
de longueur 4 de G possède une corde. On suppose a cet effet que G contient un 
4--cycle sans corde.

On dispose donc de 4 segments 10,11,12,13 tels que [0 0 Il % (0,11 0 12 % (0,12 
0 13 # (0,13 n 10 yé (Z), et
[O 0 12 = (I), Il 0 13 = @. On supposera pour simplifier que les extrémités des 
segments sont toutes distinctes.

IV.A.1) Montrer qu'aucun des segments Ik, k = O, 1, 2, 3 n'est inclus dans un 
autre de ces segments.

IV.A.2) On a donc par exemple minlO < min11 < maxlo < maxll. Montrer que min11 
< minI2 < maxll <
max]2 et de même pour 12 et 13.

IV.A.3) Conclure à une contradiction.

I V.B -- Cordalité des graphes d'intervalles
Montrer plus généralement que tout graphe d'intervalles est cordal.

I V.C -- Une enquête policière

Six personnes sont entrées dans la bibliothèque le jour où un livre rare y a 
été volé. Chacune d'entre elles est
entrée une seule fois dans la bibliothèque, y est restée un certain temps, puis 
elle en est sortie. Si deux personnes
étaient ensemble dans la bibliothèque à un instant donné, alors au moins l'une 
des deux a vu l'autre. À l'issue
de l'enquête, les témoignages recueillis sont les suivants: Albert dit qu'il a 
vu Bernard et Édouard dans la
bibliothèque. Bernard a vu Albert et Isabelle. Charlotte affirme avoir vu 
Didier et Isabelle. Didier dit qu'il a vu
Albert et Isabelle. Édouard certifie avoir vu Bernard et Charlotte. Isabelle 
dit avoir vu Charlotte et Édouard.
Seul le coupable a menti. Qui est-il ?

I V.D -- Ordre d'élimination parfait
Un sommet 11 d'un graphe G est dit simplicial lorsque l'ensemble des voisins de 
U dans G est une clique.

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

On représente en Caml un sous-graphe induit d'un graphe G possédant n sommets 
par le couple (aretes , sg)
de type int list vect * bool vect où aretes est une description du graphe G et 
sg est un tableau de taille
n tel que sg. (i) vaut true si le sommet d'indice i est un sommet du 
sous-graphe induit et false sinon.

IV.D.1) Écrire une fonction de signature

simplicial : (int list vect * bool vect) --> int --> bool

2015-03-16 13:26:27 Page 5/6

telle que l'appel à simplicial (aretes , sg) k, où le sommet d'indice k est 
supposé appartenir au sous-graphe
induit H décrit par (aretes, sg), renvoie true si le sommet d'indice k est 
simplicial dans H et false sinon.
Déterminer la complexité de la fonction simplicial.

IV.D.2) Écrire une fonction de signature
trouver_simplicial : (int list vect * bool vect) --> int

telle que l'appel à trouver_simplicial (aretes , sg) renvoie, s'il en existe, 
un sommet simplicial du sous-graphe
induit décrit par (aretes , sg). Déterminer la complexité de la fonction 
trouver_simplicial.

IV.D.3) Écrire une fonction de signature
ordre_parfait : int list vect --> int list

telle que l'appel à ordre_parfait aretes renvoie un ordre d'élimination parfait 
du graphe décrit par aretes,
s'il en existe un. Déterminer la complexité de la fonction ordre_parf ait.

I V.E -- Coupures minimales dans un graphe cordal

Étant donné un graphe G on appelle coupure de G tout ensemble G Q S' de sommets 
de G, de cardinal au moins

égal à 2, tel que certains sommets reliés par un chemin dans le graphe G ne le 
sont plus dans le sous-graphe H
de G induit par S \ G .

On se donne dans cette question un graphe cordal G = (S', A). Soit C une 
coupure de G de cardinal minimal
(supérieur ou égal à 2). Soit H le sous--graphe de G induit par S \ G . Soient 
a et b deux sommets de G
déconnectés par la coupure, et soient G1 et G2 les composantes connexes de a et 
b dans le graphe H. Soient
enfin a: et y deux sommets distincts de la coupure G .

IV.E.1) Montrer que $ est voisin dans le graphe G d'un sommet de G1 et d'un 
sommet de G2, et de même
pour y.

IV.E.2) Montrer qu'il existe un chemin P1 : (oe,a1,...,ap,y) dont tous les 
sommets hormis 95 et y sont des
sommets de G1 et un chemin P2 : (y,b1, ...,bq,oe) dont tous les sommets hormis 
a: et y sont des sommets de

G2.
IV.E.3) On prend deux tels chemins P1 et P2 de longueur minimale. En 
considérant un cycle formé à partir
des chemins P1 et P2, montrer que x et y sont reliés dans le graphe G.

IV.E.4) Montrer que G est une clique du graphe G.

I V.F -- Sommets simpliciauoe dans un graphe cordal

On se propose de montrer que tout graphe cordal G possède la propriété 
suivante, que l'on appellera la propriété
?(G) : G possède un sommet simplicial, et même deuæ sommets simpliciauæ non 
voisins si G n'est pas complet.
On se donne dans toute la question un graphe cordal G.

IV.F.1) Montrer que si G est complet alors tous ses sommets sont simpliciaux.
IV.F.2) Montrer que la propriété .'P(G) est vérifiée si G possède 1, 2 ou 3 
sommets.

IV.F.3) On suppose dans cette question que G n'est pas complet, possède au 
moins trois sommets et que la
propriété ?(G') est vérifiée pour tous les graphes cordaux G' ayant strictement 
moins de sommets que G. Soit
C une coupure de G de cardinal minimal. Soient a et b deux sommets de G 
déconnectés par la coupure G , et
G1 et G2 les composantes connexes de a et b dans le sous-graphe de G induit par 
S \ G . Soit 51 (resp: S2)
l'ensemble des sommets de G1 (resp : G2)- Soit enfin H1 (resp : H 2) le 
sous-graphe de G induit par 51 U C (resp
52 U C ).

a ) Justifier que le graphe H1 est cordal.

b) On suppose que H1 est complet. Montrer que 51 contient un sommet simplicial 
du graphe H1. Prouver que
ce sommet est en fait un sommet simplicial de G.

c) On suppose que H1 n'est pas complet. Montrer que 31 U C contient deux 
sommets simpliciaux non voisins
du graphe H1. Montrer que au moins l'un de ces deux sommets est dans 51 et que 
ce sommet est un sommet
simplicial de G.

d) Montrer que la propriété &" (G) est vérifiée.

I V.G -- Ordre d'élimination parfait dans un graphe cordal
Montrer que tout graphe cordal possède un ordre d'élimination parfait.

oooFlNooo

2015-03-16 13:26:27 Page 6/6

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique optionnelle MP 2015
Corrigé
Ce corrigé est proposé par Benjamin Monmege (Enseignant-chercheur à 
l'université) ; il a été relu par Charles-Pierre Astolfi (ENS Cachan) et 
Guillaume Batog
(Professeur en CPGE).

Ce sujet consiste en l'étude d'un problème d'allocation de ressources. Un 
ensemble
de tâches (cours, avion en phase d'atterrissage, requête d'un client 
informatique, etc.)
est modélisé par un ensemble d'intervalles correspondant au temps nécessaire à 
la
réalisation de chacune d'elles. Il s'agit alors d'allouer une ressource (salle, 
piste d'atterrissage, serveur informatique, etc.) à chaque tâche de sorte 
qu'une ressource ne soit
jamais utilisée au même instant par deux tâches différentes. On cherche par 
ailleurs
à minimiser le nombre de ressources nécessaires. Au long de quatre parties 
fortement
dépendantes, le sujet propose une solution grâce à l'étude de colorations de 
graphes
d'intervalles.
· La partie I introduit les graphes d'intervalles, qui permettent de représenter
à l'aide de graphes non orientés les contraintes d'intervalles d'un problème
d'allocation de ressources. Une allocation de ressources consiste alors en une
coloration du graphe, c'est-à-dire à l'étiquetage de chaque sommet par une
couleur de telle sorte que les sommets voisins ne soient jamais étiquetés avec
la même couleur. Un lien est établi entre le nombre chromatique d'un graphe,
c'est-à-dire le nombre minimal de couleurs nécessaire pour le colorier, et la 
taille
de la plus grande clique (sous-graphe complet) du graphe. Certaines fonctions
utiles pour la suite du sujet sont également implémentées.
· La partie II propose un algorithme glouton pour colorier un graphe 
d'intervalles.
Son implémentation, la preuve de sa correction et sa complexité sont étudiées.
· La partie III démontre que l'algorithme glouton précédent reste correct dans 
le
cas plus général de graphes munis d'un ordre d'élimination parfait, c'est-à-dire
une énumération de leurs sommets telle que, pour chaque sommet, ses voisins
énumérés avant lui forment une clique.
· La partie IV étudie finalement une condition suffisante pour qu'un graphe 
possède un ordre d'élimination parfait, à savoir que le graphe soit cordal : un 
graphe
est cordal si tout cycle de longueur supérieure à quatre possède une corde.
Les graphes cordaux sont couramment appelés graphes triangulés. Après avoir
montré que tout graphe d'intervalles est cordal, le sujet demande de résoudre
une énigme policière à l'aide de cet outil. Le reste du sujet implémente la 
recherche d'ordres d'élimination parfaits lorsqu'ils existent, puis prouve que 
tout
graphe cordal possède un ordre d'élimination parfait.
Les parties I à III du sujet sont des applications directes du cours, où l'on 
manipule des graphes représentés par des listes d'adjacence. L'énigme 
policière, ainsi que
les questions d'implémentation et de complexité de la partie IV, sont nettement 
plus
difficiles et discriminantes : elles permettent d'évaluer la créativité et la 
compréhension globale des parties précédentes. Enfin, les trois dernières 
sections de la partie IV
proposent une preuve élégante de théorie des graphes.

Indications
I.C.2 Utiliser la fonction conflit de la question I.A.1 afin de construire 
itérativement le tableau de listes de voisins de G(I0 , . . . , In-1 ).
I.E.2 Montrer que (G) 6 (G).
I.E.3 Remarquer que tester si un ensemble {x0 , . . . , xp-1 }  S de sommets 
est une
clique de G consiste à vérifier que, pour tout 0 6 q < p, tous les sommets
de {xq+1 , . . . , xp-1 } sont voisins avec xq . Utiliser la fonction appartient
de la question I.D.2.a.
II.B Employer la fonction couleur_disponible de la question I.D.2.d.
II.C.1 Les intervalles sont énumérés dans l'ordre croissant de leurs extrémités
gauches.
II.C.3 Utiliser l'inégalité trouvée à la question I.E.2.
II.D Déterminer dans un premier temps la complexité des fonctions des questions
de la partie I.D.2.
III.B.2 Utiliser la fonction est_clique de la question I.E.3 ainsi que la 
fonction
voisins_inferieurs de la question III.B.1.
III.C Appliquer le résultat de la question II.C.2.
III.D.3 Remarquer la ressemblance de cette partie avec la partie II.C.
IV.A.2 Grâce à la question I.A.1, expliciter le fait que I1 et I2 ont une 
intersection
non vide et que I0 et I2 ont une intersection vide.
IV.A.3 Utiliser la caractérisation de la question I.A.1 pour contredire le fait 
que
I0  I3 6= .
IV.B Procéder par récurrence, en remarquant qu'un cycle de longueur n + 1 > 5
dans un graphe d'intervalles peut se réduire en un cycle de longueur n dans
un graphe d'intervalles obtenu en fusionnant deux sommets.
IV.C Construire le graphe d'intervalles G résumant les informations données et
noter qu'il n'est pas cordal. En sachant que seul le coupable a menti, la
suppression d'un seul sommet de G le rend cordal.
IV.D.1 Utiliser la fonction est_clique de la question I.E.3, puis montrer 
qu'elle
teste si l'ensemble représenté par la liste xs de longueur k est une clique
d'un graphe à m arêtes avec une complexité O(1 + km).
IV.D.3 Employer une approche gloutonne qui consiste à éliminer itérativement des
sommets simpliciaux en utilisant la fonction trouver_simplicial de la
question IV.D.2. Justifier que l'algorithme est correct en démontrant que
si un graphe G = (S, A) possède un ordre d'élimination parfait, alors pour
tout sommet simplicial x dans G, le graphe induit par S r {x} possède un
ordre d'élimination parfait.
IV.E.1 En notant C1 l'ensemble des sommets de C qui n'ont pas de voisin dans S1 
,
montrer que C r C1 est une coupure. Déduire de la minimalité de C que
C1 = .
IV.E.2 Profiter du fait que G1 et G2 sont des composantes connexes de G.
IV.E.3 Dans le cycle formé à partir des chemins P1 et P2 , où se trouvent les 
cordes ?
IV.F.3.c Utiliser le résultat de la question IV.F.3.a pour appliquer 
l'hypothèse P(H1 ).
Conclure grâce à la question IV.E.4.
IV.G S'inspirer du raisonnement de la question IV.D.3 et utiliser le résultat 
de la
partie IV.F.

I. Graphes d'intervalles
I.A.1 Soient I = [ a ; b ] et J = [ c ; d ] deux intervalles. S'ils sont en 
conflit, il existe
un réel x appartenant à I  J. En particulier, a 6 x 6 b et c 6 x 6 d, ce qui 
implique
que a 6 d et c 6 b.
Réciproquement, supposons que a 6 d et c 6 b. Deux cas sont alors possibles :
soit a 6 c, auquel cas c  I  J, soit a > c, auquel cas a  I  J. Dans tous les 
cas, les
intervalles I et J sont en conflit.
Les intervalles [ a ; b ] et [ c ; d ] sont donc en conflit si et seulement si 
a 6 d et
c 6 b. Ainsi, la fonction conflit se contente d'exécuter ce test.
let conflit (a,b) (c,d) = (a <= d) && (c <= b);;
I.C.1 Le graphe d'intervalles associé au problème b de la figure 1 peut se 
représenter
de la manière suivante :
I2
I0

I3

I6

I8

I5

I7

I4

I1

I.C.2 Afin de construire la représentation des arêtes du graphe G(I0 , . . . , 
In-1 )
associé au tableau de segments (I0 , . . . , In-1 ), parcourons les paires 
d'intervalles itérativement afin d'insérer une arête (i, j) si Ii et Ij sont en 
conflit. Un tableau aretes
de n listes vides est initialement créé pour recevoir les listes de voisins du 
graphe.
Une boucle sur les indices i parcourt ensuite les intervalles Ii et une boucle 
interne
sur les indices j  {0, . . . , i - 1} parcourt les intervalles Ij pour 
concaténer j en tête
de la liste courante des voisins de i, et i en tête de la liste courante des 
voisins de j,
si Ii et Ij sont en conflit : le test de conflit est réalisé à l'aide de la 
fonction conflit
décrite à la question I.A.1.
let construit_graphe segments =
let n = vect_length segments in
let aretes = make_vect n [] in
for i=n-1 downto 0 do
for j=i-1 downto 0 do
if (conflit segments.(i) segments.(j))
then begin
aretes.(i) <- j::aretes.(i);
aretes.(j) <- i::aretes.(j)
end
done;
done;
aretes;;
Par souci esthétique, les indices i et j sont parcourus dans l'ordre 
décroissant,
afin de renvoyer une liste des voisins de chaque sommet dans l'ordre croissant.

I.D.1 Une coloration du graphe d'intervalles de la figure 3, associé au 
problème a
de la figure 1, est donnée par la suite (0, 1, 2, 0, 1, 0, 0) :

Toute coloration de ce graphe nécessite au moins trois couleurs puisque les 
sommets
0, 1 et 2 sont reliés deux à deux et ne peuvent donc pas avoir une couleur en 
commun.
Pour les mêmes raisons, la suite (0, 1, 2, 0, 1, 0, 2, 1, 0) est une coloration 
optimale
du graphe d'intervalles trouvé en question I.C.1, associé au problème b de la 
figure 1,
comme reproduite ci-dessous :

I.D.2.a Le test d'appartenance d'un élément x dans une liste est réalisé à 
l'aide
d'une fonction récursive qui parcourt la liste jusqu'à trouver x et qui conclut 
négativement si la fin de la liste est atteinte.
let rec appartient l x =
match l with
|[] -> false
|a::q -> (a=x) || (appartient q x);;
Il est sans doute maladroit dans cette question de répondre en utilisant la
fonction de signature mem : 'a -> 'a list -> bool de la librairie standard
de Caml telle que mem x l teste l'appartenance de l'élément x dans la liste l.
I.D.2.b Notons que le plus petit entier non présent dans une liste l de taille 
n est
nécessairement inférieur à n + 1. Créons donc un vecteur v de taille n, 
initialisé à
false, dont la case d'indice c a pour vocation de contenir true si et seulement 
si
c appartient à l. À l'aide d'un tel vecteur, trouver le plus petit entier non 
présent
revient à trouver l'indice de la première case du vecteur ne contenant pas 
true, donc
n + 1 si toutes les cases contiennent true, ce que réalise la boucle while 
finale du
programme. Construisons ainsi ce vecteur à l'aide d'une fonction auxiliaire 
récursive de signature parcours : int list -> unit telle que parcours l met à 
jour le
vecteur v en fonction des entiers contenus dans l.
let plus_petit_absent l =
let n = list_length l in
let v = make_vect n false in
let rec parcours = function
|[] -> ()
|c::q -> if (c