Gloutonner
G. Aldon - J. Germoni - J.-M. Meny
mars 2012
IREM de LYON ()
glouton
mars 2012
1 / 23
Algorithme glouton
Le principe de lalgorithme glouton (greedy algorithm) :
faire toujours un choix localement optimal dans lespoir que ce choix
m`enera `a une solution globalement optimale.
IREM de LYON ()
glouton
mars 2012
2 / 23
Coloration des sommets dun graphe
On cherche `a obtenir une coloration des sommets dun graphe qui
satisfasse `a la contrainte suivante : deux sommets voisins nont jamais la
meme couleur.
On cherche `a optimiser le nombre de couleurs utilisees. Le plus petit
nombre de couleurs permettant la coloration est appele nombre
chromatique du graphe.
IREM de LYON ()
glouton
mars 2012
3 / 23
Algorithme glouton
On consid`ere lalgorithme suivant :
Input. Un graphe G et des couleurs 1,2,3,4. . .Les sommets de G sont
numerotes de 1 `a n (s1 ,s2 ,. . .,sn ).
IREM de LYON ()
glouton
mars 2012
4 / 23
Algorithme glouton
On consid`ere lalgorithme suivant :
Input. Un graphe G et des couleurs 1,2,3,4. . .Les sommets de G sont
numerotes de 1 `a n (s1 ,s2 ,. . .,sn ).
Output. Une coloration valide du graphe G . Mais le nombre de
couleurs utilisees est-il minimal ?
IREM de LYON ()
glouton
mars 2012
4 / 23
Algorithme glouton
On consid`ere lalgorithme suivant :
Input. Un graphe G et des couleurs 1,2,3,4. . .Les sommets de G sont
numerotes de 1 `a n (s1 ,s2 ,. . .,sn ).
Output. Une coloration valide du graphe G . Mais le nombre de
couleurs utilisees est-il minimal ?
Traitement. Pour i allant de 1 `a n, affecter au sommet si la plus
petite couleur non dej`a affectee `a ses voisins dej`a colories (cest-`a-dire
la plus petite couleur non dej`a affectee `a ceux des sommets
s1 ,s2 ,. . .,si1 qui lui sont adjacents). En dautres termes, on
gloutonne : on sattache, localement, `a ne pas augmenter le nombre
de couleurs lorsque cest possible.
IREM de LYON ()
glouton
mars 2012
4 / 23
Une coloration non necessairement optimale
Appliquer lalgorithme au graphe ci-dessous avec plusieurs numerotions des
sommets et en deduire que lalgorithme ne donne pas necessairement le
nombre chromatique.
IREM de LYON ()
glouton
mars 2012
5 / 23
Une coloration non necessairement optimale
Premi`ere numerotation :
1
Seconde numerotation :
1
IREM de LYON ()
glouton
mars 2012
6 / 23
La coloration peut etre optimale
Exercice. Etablir
quon peut toujours numeroter les sommets de facon `a
obtenir le nombre chromatique en appliquant lalgorithme.
IREM de LYON ()
glouton
mars 2012
7 / 23
La coloration peut etre optimale
Exercice. Etablir
quon peut toujours numeroter les sommets de facon `a
obtenir le nombre chromatique en appliquant lalgorithme.
Preuve.
On suppose disposer dune coloration optimale par les couleurs c1 , c2 ,
c3 , . . ., c .
On numerote dabord les sommets de couleur c1 , puis les sommets de
couleur c2 , puis les sommets de couleur c3 . . .
Lalgorithme colorie alors les sommets de couleur c1 en une couleur
c10 , les sommets de couleurs c2 en couleur c10 ou c20 , les sommets de
couleur c3 en couleur c10 ou c20 ou c30 . . .
IREM de LYON ()
glouton
mars 2012
7 / 23
Illustration
Appliquer le principe de la demonstration precedente au graphe ci-dessous
pour lequel on a donne une coloration optimale.
IREM de LYON ()
glouton
mars 2012
8 / 23
Illustration
On numerote, par exemple, comme suit suivant lordre
couleurs :
2
6
3
1
5
8
IREM de LYON ()
des
9
4
glouton
mars 2012
9 / 23
Illustration
Les sommets rouges reprennent la couleur rouge :
2
6
3
1
5
8
IREM de LYON ()
9
4
glouton
mars 2012
10 / 23
Illustration
Les sommets 5, 6, 7 voisins de sommets rouges prennent la couleur jaune :
2
6
3
1
5
8
IREM de LYON ()
9
4
glouton
mars 2012
11 / 23
Illustration
Le sommet 8 ne reprend pas sa couleur initiale :
2
6
3
1
5
8
IREM de LYON ()
9
4
glouton
mars 2012
12 / 23
Illustration
Le sommet 9 doit prendre une troisi`eme couleur :
2
6
3
1
5
8
IREM de LYON ()
9
4
glouton
mars 2012
13 / 23
Un glouton tr`es mauvais ?
Lalgorithme glouton propose ne donne pas necessairement le nombre
minimum de couleurs. Mais peut-il etre tr`es mauvais (du point de vue du
nombre de couleurs utilisees) ?
Montrer que oui avec des graphes construits comme le suivant :
IREM de LYON ()
glouton
mars 2012
14 / 23
Un glouton tr`es mauvais
On numerote dabord ligne par ligne de gauche `a droite. Lalgorithme
donne 4 couleurs :
7
8
5
IREM de LYON ()
glouton
mars 2012
15 / 23
Un glouton tr`es mauvais
On numerote maintenant par colonne, lalgorithme donne 2 couleurs :
4
8
3
IREM de LYON ()
glouton
mars 2012
16 / 23
Un glouton tr`es mauvais
En generalisant sur ce type de graphe, on obtient des graphes colores avec
lalgorithme, avec k couleurs, k entier fixe `a lavance aussi grand que
desire, alors que le nombre chromatique est 2.
IREM de LYON ()
glouton
mars 2012
17 / 23
Les epreuves du gymnase
On reprend le probl`eme du gymnase : on veut que se deroule, sur 24 h, le
plus grand nombre possible depreuves, chaque epreuve etant caracterisee
par une heure de debut et une heure de fin. On cherche maintenant le
nombre minimal de gymnases permettant le deroulement de toutes les
epreuves.
IREM de LYON ()
glouton
mars 2012
18 / 23
Glouton 1
Les dates de fin au plus tot ayant permis le deroulement dun nombre
optimal depreuves avec un seul gymnase, on essaie de remplir le
gymnase 1 au maximum avec ce principe, puis on passe `a un gymnase 2,
puis . . .
IREM de LYON ()
glouton
mars 2012
19 / 23
Glouton 1
Les dates de fin au plus tot ayant permis le deroulement dun nombre
optimal depreuves avec un seul gymnase, on essaie de remplir le
gymnase 1 au maximum avec ce principe, puis on passe `a un gymnase 2,
puis . . .
Verifier que le resultat nest pas optimal avec la situation suivante :
h
b
f
a
d
e
g
c
IREM de LYON ()
glouton
mars 2012
19 / 23
Glouton 1
Le gymnase 1 verra se derouler les epreuves : h, d, e,
le gymnase 2 : a, f
le gymnase 3 : b, g
le gymnase 4 : c.
Alors que 3 gymnases suffisent : h, c, f a, d, e b, g .
IREM de LYON ()
glouton
mars 2012
20 / 23
Glouton 2
On represente les intervalles de temps
h
b
a
d
c
f
e
g
par le graphe des incompatibilites :
b
IREM de LYON ()
glouton
mars 2012
21 / 23
Glouton 2
On represente les intervalles de temps
h
b
a
d
c
f
e
g
par le graphe des incompatibilites :
b
h
e
Montrer quune coloration du graphe par notre algorithme glouton de
coloration utilise un nombre de couleurs egal au nombre chromatique avec
une numerotation des sommets correspondant `a lordre croissant des
extremites gauche des intervalles.
IREM de LYON ()
glouton
mars 2012
21 / 23
Glouton 2 Illustration
Numerotation des sommets pour lapplication de lalgorithme (ordre
croissant des debuts depreuves) :
3
1
6
ce qui donne la coloration suivante :
c3
c2
c2
c1
c3
c1
IREM de LYON ()
c2
glouton
c1
mars 2012
22 / 23
Glouton 2 Preuve de loptimalite
Lorsquun sommet v recoit une couleur k, cest que lextremite gauche de
lintervalle v appartient `a au moins k 1 intervalles (sinon on pourrait
choisir une couleur 6 k 1 pour v ).
IREM de LYON ()
glouton
mars 2012
23 / 23
Glouton 2 Preuve de loptimalite
Lorsquun sommet v recoit une couleur k, cest que lextremite gauche de
lintervalle v appartient `a au moins k 1 intervalles (sinon on pourrait
choisir une couleur 6 k 1 pour v ).
Tous ces intervalles se coupent (lextremite gauche de v est commun `a
tous) :
le graphe presente donc une clique dordre > k, donc le nombre
chromatique est dau moins k.
IREM de LYON ()
glouton
mars 2012
23 / 23
