République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université des Sciences et Technologie de Houari Boumedienne

Faculté des Mathématiques

Département de Recherche Opérationnelle

Mini projet de fin d’étude

En vue de l’obtention du Diplôme de Licence en Recherche Opérationnelle

Thème

Problème de coloration des graphes

Présenté par :
Encadré par :
BOUGUEDOUR Sara
[Link] Yamina
MEZIANE Yasmine
Table des matières

Table des matières 1

Remérciment 2

Introduction générale 3

1 Notions de base 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Degrés et adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Sous structures d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Quelques classes particulières de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Problème de coloration des graphes 12

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Coloration d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Formulation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Complexité [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Coloration de classes particulières de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Méthodes de résolution 18
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Problèmes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Méthodes de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Algorithme de recherche taboue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4.1 L’application de la Recherche Tabou sur le Graphe de petersen . . . . . . . . . . . . . . . . . 23
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Implémentation 30
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 Pourquoi Python ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Implémentation en Python de l’algorithme de recherche taboue pour la coloration des graphes . . . . 31
4.3.1 La fonction principale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Conclusion générale 38

Bibliographie 39

1
Remerciements

Tout d’abord, nous tenons à exprimer notre profonde gratitude envers Allah, le Tout-Puissant, pour Sa miséricorde

et Sa bénédiction infinies, qui nous ont permis de mener à bien ce projet.

Nous tenons également à remercier chaleureusement notre binôme pour sa collaboration tout au long de ce travail et

pour les moments de partage et de convivialité qui ont égayé cette expérience. Nous exprimons notre reconnaissance

envers nos pères, nos mères, nos sœurs et nos frères pour leur soutien inconditionnel et leur encouragement constant.

Nous souhaitons également exprimer notre profonde gratitude envers notre encadrante, Madame BEKHTI Ya-

mina, pour son accompagnement bienveillant, ses conseils avisés et sa disponibilité tout au long de ce projet. Nous

n’aurions pas pu accomplir ce travail sans son soutien et ses encouragements.

Enfin, nous tenons à remercier les anciens membres du club Recherche Opérationnelle (RO) ainsi que MAAMRA

Fateh pour leur aide inestimable. Ce projet a été une expérience enrichissante et nous sommes fiers de ce que nous

avons accompli ensemble. Merci infiniment à tous pour votre soutien et votre confiance.

2
Introduction générale

La Recherche Opérationnelle est une discipline des mathématiques appliquées qui se concentre sur la résolution
de problèmes logistiques, de production, de gestion de la chaı̂ne d’approvisionnement, de finance, de marketing et de
gestion de projets. Elle vise à améliorer l’efficacité des entreprises, à réduire les coûts et à augmenter la rentabilité.
Les professionnels de la Recherche Opérationnelle utilisent des méthodes telles que l’optimisation, la modélisation,

la simulation, l’analyse de données et la programmation linéaire en collaboration avec d’autres experts pour résoudre
des problèmes spécifiques.
La Recherche Opérationnelle a émergé pendant la Seconde Guerre mondiale, où elle a été largement utilisée par
les militaires pour optimiser l’utilisation de leurs ressources limitées, telles que les soldats, les munitions et les four-

nitures. Cette approche a permis à l’armée de prendre des décisions plus éclairées et d’améliorer son efficacité sur
le terrain. Au fil du temps, la Recherche Opérationnelle est devenue une discipline à part entière enseignée dans les
écoles de commerce et les universités du monde entier. Elle a également évolué pour inclure de nouvelles méthodes

et technologies telles que l’analyse de données, la modélisation par simulation et l’optimisation multicritère. Au-
jourd’hui, elle reste un outil essentiel pour aider les entreprises et les organisations à prendre des décisions éclairées
afin d’accroı̂tre leur efficacité et leur rentabilité.
L’Optimisation Combinatoire est une branche récente des mathématiques appliquées qui propose différentes

approches pour résoudre les problèmes donnés. Dans ce mémoire, nous nous intéressons plus spécifiquement au
problème de coloration des graphes et à sa résolution par une méthode d’optimisation combinatoire.
Ce mémoire est composé de quatre chapitres. Le premier chapitre présente les notions de base de la théorie des

graphes, le deuxième chapitre aborde le problème de coloration des graphes, tandis que le troisième chapitre discute
de la méthode de résolution choisie pour résoudre ce problème. Enfin, le dernier chapitre traite de l’implémentation
de la méthode de résolution à l’aide d’un langage de programmation approprié. Le mémoire se conclut par une
conclusion générale.

3
Chapitre 1

Notions de base

1.1 Introduction

La théorie des graphes est un outil puissant de modélisation et de résolution de problèmes. Elle permet de
représenter et d’organiser de manière optimale diverses tâches. Le problème des sept ponts d’Euler, qui consistait
à trouver un chemin circulaire à travers la ville de Königsberg, a été l’un des premiers problèmes de théorie des

graphes à être formulé.

Les graphes offrent une approche de pensée permettant de modéliser une grande variété de problèmes. C’est
pourquoi nous consacrons ce premier chapitre à présenter leurs propriétés et certains concepts fondamentaux. Cette

section nous permettra d’acquérir une compréhension solide qui sera essentielle pour la suite de ce mémoire.

1.2 Graphes
Qu’est-ce qu’un graphe ?

Un graphe G = (V, E) [2] est une structure géométrique composée d’un ensemble de sommets V reliés par un

ensemble d’arêtes E. Chaque arête relie deux sommets distincts, ayant une extrémité initiale x et une extrémité
finale y.
On peut définir les termes suivants :
L’ordre du graphe : le nombre de sommets, noté |V | = n.

La taille du graphe : le nombre d’arêtes, noté |E| = m.

4
 Exemple :

b g

a c e f

d h

Figure 1.1 – G = (V, E) est un graphe.

— Un graphe G est dit simple s’il ne possède ni arête parallèle ni boucle. Une boucle est une arête dont

l’extrémité initiale et l’extrémité finale sont confondues, notée e = (x, x).

— Un multigraphe est un graphe qui peut contenir des boucles et des arêtes multiples entre les mêmes paires
de sommets.

a a

b c b c

d e d e

Figure 1.2 – G = (V, E) est un graphe simple. Figure 1.3 – G=(V, E) est un multigraphe.

— Un graphe non orienté G est défini par le couple G = (V, E) où V est un ensemble fini de sommets et E est

un ensemble de paires non ordonnées de sommets {vi , vj } ∈ V 2 .

— Un graphe orienté G = (V, E) est défini par un ensemble fini V qui représente l’ensemble des sommets du
graphe G et un ensemble E contenu dans V V , qui représente l’ensemble des arcs de G. Chaque arc e ∈ E est
représenté par une paire (x, y), où x ∈ V est l’extrémité initiale de l’arc e ety ∈ V est l’extrémité terminale

de l’arc e.
Exemple :

a a

b c b c

e d e d

Figure 1.4 – G = (V, E) est un graphe non orienté. Figure 1.5 – G = (V, E) est un graphe orienté.

5
1.3 Degrés et adjacence

Soit G = (V, E) un graphe orienté, nous avons :

— Le demi-degré extérieur d’un sommet v est le nombre d’arcs ayant le sommet v comme extrémité initiale.
On le note d+
G (v) =| e ∈ E | I(e) = v |.

— Le demi-degré intérieur d’un sommet v est le nombre d’arcs ayant v comme extrémité terminale. On le note

d−
G (v) =| e ∈ E | T (e) = v |.

— Le degré d’un sommet v est le nombre d’arcs ayant v comme extrémité initiale ou terminale. On le note
dG (v) = d− +
G (v) + dG (v).

Remarque :
P − P +
v∈V dG (v) = v∈V dG (v).

SoitG = (V, E) un graphe non orienté :

— Le degré d’un sommet v dans un graphe non orienté est le nombre d’arêtes incidentes à v. On le note dG (v). La
P
somme des degrés dans un graphe non orienté est égale à deux fois le nombre d’arêtes : v∈V dG (v) = 2· | E |.
Remarque :
La somme des degrés est paire.

Si dG (v) = 0, alors v est un sommet isolé.

Si dG (v) = 1, alors v est un sommet pendant.

Incidence et adjacence :

Deux arcs (arêtes) sont dits adjacents s’ils ont une extrémité commune, c’est-à-dire que e= (x, y) et v = (s, t)
sont adjacents lorsque {x, y} ∩ {s, t} =
̸ ∅.

Un arc (arête) u est dit incident à un sommet x s’il y a une extrémité de u qui est x. Si e = (x, y) est un arc,
alors u est incident à x à l’extérieur, et u est incident à y à l’intérieur.

Matrices associées à un graphe :

La matrice d’adjacence : Soit G un graphe, la matrice d’adjacence M = (ai,j ) est une matrice (n × n), où

chaque ligne (i) et chaque colonne (j) correspondent à un sommet du graphe. Mi,j représente le nombre d’arcs (ou
d’arêtes) ayant xi comme extrémité initiale et xj comme extrémité terminale.
Exemple :

Soit M la matrice d’adjacence associée au graphe G de la figure 1.1 :

6
  
0 1 1 1 0 0 0 0
1 0 1 0 0 0 1 0
 
1 1 0 1 0 0 0 0
 
1 0 1 0 0 0 0 1
M =
0

 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
 
0 1 0 0 0 1 0 0
0 0 0 1 1 1 0 0

La matrice d’incidence sommet-arc : Soit G un graphe orienté sans boucle. La matrice d’incidence sommet-
arc A est une matrice (n × m) où chaque ligne correspond à un sommet de G et chaque colonne correspond à un
arc de G. Chaque élément de la matrice indique la relation entre un sommet et un arc comme suit :


 +1 : signifie que le sommet est une extrémité initiale de l’arc.
−1 : signifie que le sommet est une extrémité terminale de l’arc.
0 : signifie qu’il n’existe pas une relation entre le sommet et l’arc.


Exemple :
Soit A la matrice d’incidence sommet-arc associée au graphe de la figure 1.5.
 
0 1 0 0 0
−1 0 −1 1 −1
 
A= 0 1 0 0 −1 
 0 −1 0 0 0 
0 1 1 0 0
La matrice d’incidence sommet-arête Soit G un graphe non orienté sans boucle. La matrice d’incidence
sommet-arête E est une matrice (n×m) où chaque ligne correspond à un sommet de G et chaque colonne correspond

à une arête de G. Chaque élément de la matrice indique la relation entre un sommet et une arête comme suit :


1 : signifie que le sommet est une extrémité de l’arête.
0 : signifie qu’il n’existe pas une relation entre le sommet et l’arête.

Exemple :
Soit E la matrice d’incidence sommet-arête associée au graphe de la figure 1.4.
 
0 1 0 0 0
1 0 1 1 1
 
E= 0 1 0 0 1

0 1 0 0 0
0 1 1 0 0

Ensembles des prédécesseurs et successeurs

Soit G = (V, E) un graphe orienté :

— L’ensemble des prédécesseurs d’un sommet v est défini comme : | Γ− (v) |= {y ∈ V : ∃e ∈ E où I(e) = y et
T (e) = v}.

— L’ensemble des successeurs d’un sommet v est défini comme : | Γ+ (v) |= {y ∈ V : ∃e ∈ E où T (e) = y et I(e) = v}.
— L’ensemble des voisins d’un sommet v est défini comme : | Γ(v) |=| Γ+ (v) | ∪ | Γ− (v) |.

7
1.4 Sous structures d’un graphe

Sous Graphe : un graphe G′ = (X ′ , U ′ ) est un sous graphe du graphe G = (X, U ) si et seulement si :

X ′ ⊆ X et U ′ ⊆ U .
Graphe partiel : un graphe G′ = (X ′ , U ′ ) est un graphe partiel du graphe G = (X, U ) si et seulement si :
X ′ = X et U ′ ⊆ U .
′
Graphe induit : Soit G = (V, E) un graphe. Soit A ⊆ V , et soit EA ⊆ E. Alors le graphe G′ (A, UA′ ) est
appelé le graphe induit de G.
Exemple :

Prenons comme exemple le graphe G de la figure 1.1.

b b g

a c a c e f

d d h

Figure 1.6 – G′ = (X ′ , U ′ ) est un Figure 1.7 – G′ = (X ′ , U ′ ) est un graphe partiel du

sous graphe du graphe G = (X, U ). graphe G = (X, U ).
b g

a f

d h

Figure 1.8 – G′ (A, UA′ ) est un graphe induit du graphe

G = (X, U ).

8
1.5 Quelques classes particulières de graphes

Soit G = (X, U ) un graphe non orienté.

Une chaı̂ne dans G est une séquence d’arêtes qui relie deux sommets x et y.
— Une chaı̂ne élémentaire est une chaı̂ne qui passe une et une seule fois par chaque sommet de la chaı̂ne.
— Une chaı̂ne simple est une chaı̂ne qui passe une et une seule fois par chaque arête de la chaı̂ne.

Un cycle est une chaı̂ne qui revient au même point de départ.

Soit G = (X, U ) un graphe orienté.
Un chemin dans G est une séquence d’arcs qui relie deux sommets x et y.

Un circuit est un cycle tel que tous les arcs sont orientés dans le même sens.
Exemples :

b b c

d a

c Figure 1.10 – C3 est un cycle.

Figure 1.9 – P4 est une chaı̂ne.

b c
b

d
a
c
Figure 1.12 – C3′ est un circuit.
Figure 1.11 – P4′ est un chemin qui relie le sommet a
au sommet d.

Un graphe complet : Un graphe G = (X, U ) est complet si tous les sommets sont deux à deux adjacents,
c’est-à-dire que tout couple de sommets est relié par une arête. On le note Kn . Autrement dit, pour tout x, y
appartenant à V , il existe une arête e dans E qui relie x à y.
Une clique : On appelle une clique le sous-graphe complet d’un graphe G.

9
 Exemple :

a
f d e

b
b c

d
a
c
Figure 1.14 – Les sommets {c, d, e} forment une
clique.
Figure 1.13 – K4 est un graphe complet.

Un stable est un ensemble de sommets deux à deux non adjacents.

Un graphe complémentaire : Un graphe G′ = (E ′ , V ′ ) est dit complémentaire d’un graphe simple G =

(V, E) s’il a exactement le même ensemble de sommets que le graphe G, et que deux sommets du graphe G′
sont reliés par une arête si et seulement s’ils ne le sont pas dans G.

Remarque : Le complémentaire d’un graphe complet est un stable.

Un graphe biparti : Un graphe G = (V1 ∪ V2 , E) est biparti si l’ensemble des sommets V peut être
partitionné en deux sous-ensembles V1 et V2 , tels que pour tout couple de sommets dans V1 ou dans V2 , ils
ne sont pas reliés. Avec : V1 ∪ V2 = V , V1 ∩ V2 = ∅, V1 ̸= ∅ et V2 ̸= ∅.

Un Graphe biparti complet : Dans un graphe biparti G = (V1 ∪ V2 , E), si chaque sommet de V1 est relié
à un sommet de V2 , alors le graphe G est un graphe biparti complet.
Exemples :

b f b f

c e c e

a d a d

Figure 1.15 – G = (V1 ∪ V2 , E) est un graphe biparti. Figure 1.16 – K3,3 est un graphe biparti complet.

Un graphe connexe : Un graphe G = (V, E) est dit connexe si et seulement si pour tout couple de sommets
x et y dans V , il existe au moins une chaı̂ne reliant x à y.

Un arbre : Un graphe G est un arbre s’il est connexe et acyclique. Soit G = (V, E) un graphe avec n =| V |≥ 2
sommets et m =| E | arêtes. Les propriétés suivantes sont équivalentes et caractérisent un graphe :
— G est connexe et acyclique.

10
 — G est connexe et si une arête de G est supprimée, le graphe devient non connexe.
— G est connexe et possède (n − 1) arêtes.
— G est acyclique et si une arête est ajoutée, un cycle est créé.
— G est acyclique et possède (n − 1) arêtes.

— Entre chaque paire de sommets, il existe une et une seule chaı̂ne les reliant.
Une forêt est un graphe dans lequel chaque composante connexe est un arbre. Cela signifie que la forêt
peut être composée de plusieurs arbres disjoints, où chaque arbre est une composante connexe.

Exemples :

a b c b e g i

e d c d f h

Figure 1.17 – G = (V, E) est un arbre. Figure 1.18 – G = (V, E) est une forêt.

Un graphe planaire : Un graphe G = (V, E) est planaire s’il peut être représenté dans le plan sans que les
arêtes se croisent.

Exemple :

a b

e d f

Figure 1.19 – G = (V, E) est un graphe Planaire.

Un Graphe k-régulier : Un graphe G = (V, E) est dit k-régulier si tous les sommets du graphe ont un

degré égal à k, c’est-à-dire que chaque sommet est adjacent à exactement k autres sommets.

1.6 Conclusion

En conclusion, les concepts présentés dans ce chapitre fournissent une base fondamentale pour l’étude et l’ap-

plication des graphes. Ils permettent de résoudre une variété de problèmes et de développer des applications dans
divers domaines. La théorie des graphes offre des outils et des techniques pour modéliser et analyser des structures
complexes, telles que les réseaux de communication, les réseaux sociaux, les systèmes de transport, etc.

11
Chapitre 2

Problème de coloration des graphes

2.1 Introduction

Le problème de coloration des graphes est un sujet d’étude qui remonte au XIXème siècle, lorsque Francis
Guthrie, un cartographe anglais, a posé la question suivante : Est-il possible de colorier une carte des cantons
d’Angleterre avec seulement quatre couleurs, de telle manière que deux cantons ayant une frontière commune

n’aient jamais la même couleur ? Cette conjecture, connue sous le nom de conjecture des quatre couleurs, a captivé
l’attention des mathématiciens pendant de nombreuses années.
Ce n’est qu’en 1976 que cette conjecture a été démontrée par Appel et Haken à l’aide de l’ordinateur. Cependant,

il convient de noter que cette résolution ne s’applique qu’aux graphes planaires, ce qui limite son application aux
problèmes des cartographes plutôt qu’aux problèmes mathématiques généraux.
La coloration des graphes trouve également des applications pratiques dans divers domaines tels que la planifica-
tion, l’ordonnancement et la conception de réseaux de télécommunication. Par exemple, en attribuant des couleurs

différentes à des canaux de communication, il est possible de minimiser les interférences et d’optimiser l’utilisation
des ressources. De plus, la coloration des graphes est utilisée dans le domaine de l’informatique pour résoudre des
problèmes tels que le placement de composants sur une carte de circuit imprimé, l’optimisation des itinéraires de

transport et la planification des horaires de production. Ces applications démontrent l’importance et la pertinence
du problème de coloration des graphes dans de nombreux domaines.

2.2 Coloration d’un graphe

Soit G = (V, E) un graphe simple non orienté.

La coloration des sommets (ou des arêtes) d’un graphe consiste à attribuer à chaque sommet (ou à chaque arête)
une couleur, de telle manière que deux sommets (ou arêtes) adjacents n’aient jamais la même couleur.

12
Coloration des sommets [3]

Une k-coloration des sommets de G est une application C telle que :

C : V → {1...k}
x → c(x)
Tq : {x, y} ∈ E → c(x) ̸= c(y).

— Une coloration avec k couleurs est une partition des sommets en k ensembles stables.

— Un graphe qui admet une k-coloration est dit k-coloriable.

— Une coloration est dite propre lorsque deux sommets adjacents ont toujours des couleurs différentes.
Définition : Le nombre chromatique d’un graphe est le nombre minimum de couleurs nécessaires pour colorier

ses sommets de manière propre, c’est-à-dire en assignant des couleurs différentes à des sommets adjacents. On le
note généralement par le symbole (G). Formellement, le nombre chromatique d’un graphe G est le plus petit entier
k tel que G admet une k-coloration.
Exemple :

Soit G = (V, E) le graphe de Peterson d’ordre 10. La figure 2.1 suivante illustre la coloration de ce graphe, où
il est démontré que le nombre chromatique est égal à 3.

b
c d
f e

g h

i j

Figure 2.1 – Le graphe de Peterson est 3-chromatique.

Théorème 1 : (Théorème du degré maximum)[4]

Pour tout graphe G, soit ∆ le degré maximum du graphe G. Alors, le nombre chromatique χ(G) est majoré

par : χ(G) ≤ ∆ + 1.
Preuve :
Soit G un graphe avec ∆ étant le degré maximum de ses sommets. Supposons que nous disposons d’une palette

de (∆ + 1) couleurs. Considérons maintenant chaque sommet du graphe individuellement.

Pour chaque sommet, nous pouvons faire le raisonnement suivant : ce sommet est adjacent à au plus ∆ autres
sommets, et donc il est adjacent à au plus ∆ couleurs différentes utilisées pour colorer ces sommets adjacents. Puisque
nous avons (∆ + 1) couleurs disponibles, il reste toujours au moins une couleur non utilisée pour ce sommet.

13
 Ainsi, pour chaque sommet du graphe, nous pouvons toujours trouver une couleur non utilisée dans la palette
pour le colorer, sans qu’il y ait de conflit de couleur avec ses sommets adjacents. Par conséquent, nous pouvons
colorer tous les sommets de G avec au plus (∆ + 1) couleurs, ce qui prouve que χ(G) ≤ ∆ + 1.
Théorème 2 : (Théorème du Nombre Chromatique )[4]

Pour tout graphe non vide G, le nombre chromatique χ(G) satisfait l’inégalité suivante : χ(G) ≤ n + (1 − α(G)).
Où n est l’ordre du graphe G et α(G) est la taille du plus grand stable dans G.
Preuve :

Considérons S comme étant un stable de V de cardinalité α(G). Une coloration possible des sommets consiste
à attribuer la même couleur à tous les sommets de S, et à attribuer des couleurs différentes aux n − α(G) autres
sommets. Ainsi, nous avons utilisé au plus 1 + (n − α(G)) couleurs pour colorer le graphe G. Par conséquent,
χ(G) ≤ n + (1 − α(G)).

Théorème 3 : (Théorème de Monotonicité du Nombre Chromatique )[4]

Soit G un graphe. Pour tout sous-graphe H de G, on a χ(H) ≤ χ(G), où χ(H) et χ(G) représentent respecti-
vement le nombre chromatique de H et de G.
Preuve :

La preuve de ce théorème repose sur le fait que la coloration d’un sous-graphe H de G peut être étendue à une
coloration de G sans utiliser plus de couleurs. Autrement dit, si on dispose d’une coloration valide des sommets de
H avec k couleurs, cette coloration peut être étendue à une coloration valide des sommets de G sans utiliser plus de

k couleurs. Par conséquent, le nombre chromatique de H, χ(H), ne peut pas être supérieur au nombre chromatique
de G, χ(G).
Théorème 4 : (Théorème de Brooks ) [4]
Soit G un graphe connexe simple et non complet. Si G n’est ni un graphe complet ni un cycle impair, alors

χ(G) ≤ ∆(G), où χ(G) est le nombre chromatique de G et ∆(G) est le degré maximum des sommets de G.
Preuve :
La preuve du théorème de Brooks est basée sur une argumentation par récurrence. Elle montre que pour tout

graphe connexe simple et non complet G qui n’est ni un graphe complet ni un cycle impair, le nombre chromatique
de G est au plus égal au degré maximum ∆(G). Pour cela, on considère une clique maximale dans G et on montre
que chaque sommet en dehors de cette clique est adjacent à au plus ∆(G) sommets de la clique. Ainsi, on peut
colorer les sommets de la clique avec ∆(G) couleurs et colorer les sommets en dehors de la clique avec une couleur

différente pour chaque sommet, ce qui donne une coloration valide de G avec ∆(G) couleurs.

2.3 Formulation mathématique

Le problème de coloration des sommets d’un graphe consiste à attribuer des couleurs aux sommets de manière à
ce que deux sommets adjacents ne puissent pas avoir la même couleur. Pour formaliser ce problème, on peut utiliser

14
la modélisation mathématique suivante :

 Pq
Z(Min)

 Pq
= k=1 Zk
 k=1 Cik = 1 ∀i ∈ V




C + C ≤ 1 ∀(i, j) ∈ E, ∀k = 1, . . . , q
j,k i,k


 Ci,k ∈ {0, 1} ∀i ∈ V, ∀k = 1, . . . , q
Z k ∈ {0, 1} ∀k = 1, . . . , q





Zk ≥ Ci,k ∀i ∈ V, ∀k = 1, . . . , q


où :

◦ Z(Min) est la fonction objectif qui cherche à minimiser le nombre total de couleurs utilisées.
◦ Ci,k est une variable binaire qui indique si le sommet i est coloré avec la couleur k.
◦ Zk est une variable binaire qui est égale à 1 si la couleur k est utilisée.
Pq
◦ k=1 Cik = 1 garantit que chaque sommet est coloré avec une seule couleur.

◦ Cj,k + Ci,k ≤ 1 garantit que deux sommets adjacents ne peuvent pas avoir la même couleur.
◦ Ci,k ∈ {0, 1} et Zk ∈ {0, 1} définissent les variables binaires.
◦ La contrainte Zk ≥ Ci,k est utilisée pour garantir que si le sommet i est attribué à la couleur k (Ci,k = 1),
alors la variable Zk correspondante doit également être activée (Zk = 1).

2.4 Complexité [1]

La coloration des sommets d’un graphe peut sembler un problème simple, mais sa complexité augmente ra-

pidement avec des graphes de grande taille. En réalité, l’algorithme de coloration des graphes est classé comme
NP-difficile, ce qui signifie que sa complexité est exponentielle dans le pire des cas. Cook et al. ont découvert la
complexité de ce problème en 1971.[5]
Cela implique qu’il n’existe pas d’algorithme efficace connu qui puisse résoudre le problème en un temps rai-

sonnable pour le cas général des graphes. Cependant, il existe des algorithmes d’approximation qui permettent de
trouver des solutions proches de la solution optimale en un temps polynomial, bien qu’ils ne garantissent pas de
trouver la solution exacte. De plus, dans certains cas particuliers où le nombre chromatique est borné, il est possible

de résoudre le problème de coloration des graphes en un temps polynomial

2.5 Coloration de classes particulières de graphes

Coloration des cycles élémentaires :

Soit Cn un cycle élémentaire d’ordre n. Alors :

— Si n est pair, le nombre chromatique de Cn est égal à 2.

— Si n est impair, le nombre chromatique de Cn est égal à 3.

15
Coloration d’un graphe complet :

Théorème 5 :
Soit G un graphe complet d’ordre n. Alors χ(G) = n.

Preuve :
Soit G un graphe complet d’ordre n. Pour prouver que χ(G) = n, nous devons montrer deux choses : (1)
χ(G) ≤ n et (2) χ(G) ≥ n.
(1) Montrons que χ(G) ≤ n. Pour cela, nous attribuons une couleur différente à chaque sommet de G. Comme

G est complet, chaque sommet est adjacent à tous les autres sommets. Par conséquent, il n’y a pas de contrainte
sur les couleurs utilisées, et nous pouvons donc utiliser n couleurs distinctes pour colorer les sommets de G. Ainsi,
χ(G) ≤ n.

(2) Montrons maintenant que χ(G) ≥ n. Supposons par l’absurde que χ(G) < n. Cela signifierait qu’il existe
une coloration des sommets de G avec moins de n couleurs. Cependant, comme G est complet, chaque paire de
sommets est adjacente, ce qui implique que tous les sommets doivent avoir des couleurs différentes pour respecter
la condition de non-adjacence des mêmes couleurs. Mais cela contredit notre supposition initiale selon laquelle il y

avait une coloration avec moins de n couleurs. Par conséquent, χ(G) ≥ n.

Ainsi, nous avons montré que χ(G) ≤ n et χ(G) ≥ n, ce qui implique que χ(G) = n.

Coloration d’un graphe planaire :

Théoréme 5 : (Théorème des 4 couleurs) [6, 7]

Tout graphe planaire est 4-coloriable.
Théoréme 6 [6, 8] :

Tout graphe planaire sans triangle est 3-coloriable.

Théoréme 7 [6, 9]
Tout graphe planaire avec au plus trois triangles est 3-coloriable.

Coloration d’un graphe biparti :

Théoréme 8 [6] :
Tout graphe biparti est 2-coloriable.

Preuve :
Soit G un graphe biparti avec des ensembles de sommets V1 et V2 tels que chaque arête relie un sommet de V1
à un sommet de V2 .

Pour colorier G avec 2 couleurs, nous pouvons attribuer la couleur 1 à tous les sommets de V1 et la couleur
2 à tous les sommets de V2 . Étant donné que chaque arête relie un sommet de chaque ensemble, deux sommets
adjacents auront des couleurs différentes.

16
 Ainsi, tout graphe biparti peut être 2-colorié.
Exemples :
Nous illustrons quelques exemples de graphes accompagnés de leurs colorations optimales.

b a

a c

d b c

Figure 2.2 – Le cycle C4 est 2-chromatique. Figure 2.3 – Le cycle C3 est 3-chromatique.

a h b
a d

e
b c d
f

c g
e g f
Figure 2.4 – Le graphe biparti G = (V1 ∪ V2 , E) est
2-chromatique. Figure 2.5 – Le graphe planaire G = (V, E) est 4-
coloriable.

2.6 Conclusion

Après une étude détaillée de la coloration des graphes, de ses caractéristiques et de ses applications à certaines
classes de graphes bien connues, il est essentiel de s’intéresser à la coloration dans le cas général des graphes. Une

question clé demeure : comment pouvons-nous déterminer le nombre chromatique de n’importe quel graphe ? De
plus, comment pouvons-nous résoudre efficacement divers problèmes en utilisant la coloration des graphes ? Quels
algorithmes nous permettent d’obtenir une bonne solution à ce problème en un temps de calcul réduit ?

17
Chapitre 3

Méthodes de résolution

3.1 Introduction

Lorsqu’il s’agit de résoudre un problème en recherche opérationnelle, l’objectif est de trouver une solution
optimale parmi un ensemble fini mais vaste de solutions admissibles. Une méthode évidente consiste à tester toutes
les combinaisons possibles afin de trouver la meilleure solution. Ces algorithmes, appelés algorithmes exhaustifs,

examinent toutes les possibilités, mais ils sont souvent très coûteux en termes de complexité.
Afin de réduire le temps de recherche et d’obtenir des solutions optimales de manière plus efficiente, d’autres
algorithmes ont été développés. Ces algorithmes appartiennent à différentes familles et classes, et dans ce chapitre,

nous allons les aborder en détail.

3.2 Problèmes d’optimisation

Avant d’énumérer les différentes méthodes utilisées en recherche opérationnelle pour trouver la meilleure solution,

il est important de comprendre les types de problèmes traités.

Un problème d’optimisation :

Un problème d’optimisation est un problème mathématique visant à trouver la meilleure solution parmi un
ensemble de solutions possibles, en maximisant ou minimisant une fonction objectif tout en respectant un ensemble

de contraintes.
La recherche opérationnelle s’intéresse à la résolution de divers types de problèmes d’optimisation, tels que
les problèmes d’optimisation linéaire, les problèmes d’optimisation non linéaire et les problèmes d’optimisation

combinatoire. Pour résoudre ces problèmes, différentes méthodes ont été adaptées, telles que la méthode de Newton,
la méthode de descente de gradient, la recherche taboue, la méthode émulée, etc.

Un problème d’optimisation combinatoire :

Les problèmes d’optimisation combinatoire (OC) sont des problèmes qui cherchent la meilleure solution parmi
un ensemble fini mais de grande cardinalité de solutions réalisables. Ils englobent plusieurs disciplines, notamment

18
la théorie des graphes, la combinatoire énumérative, les problèmes de dénombrement et la théorie polyédrale. Ces
problèmes ont de nombreuses applications dans divers domaines tels que la logistique, les télécommunications, la
planification de production industrielle et le transport aérien.
Il existe de nombreuses techniques d’optimisation pour résoudre ces problèmes, telles que les algorithmes

génétiques, les algorithmes de recuit simulé, les algorithmes de recherche taboue, les méthodes de programmation
linéaire et les heuristiques.

3.3 Méthodes de résolution

Les méthodes de résolution peuvent être réparties en deux classes :

Méthodes Exactes :

Les méthodes exactes [10], également appelées méthodes complètes, cherchent la solution optimale en examinant

de manière exhaustive l’ensemble des solutions possibles. Elles sont utilisées pour trouver au moins une solution
optimale à un problème. Parmi les méthodes les plus connues et les plus précises, on trouve :
La méthode de séparation et d’évaluation : l’évaluation permet de réduire l’espace de recherche en éliminant
certains sous-ensembles qui ne contiennent pas la solution optimale, tandis que la séparation consiste à diviser le

problème en deux sous-ensembles et à les résoudre en conservant la meilleure solution, ce qui garantit la résolution
du problème initial.
La méthode de programmation dynamique : elle consiste à résoudre le problème en le décomposant en
sous-problèmes plus simples, puis à combiner les solutions de ces sous-problèmes pour obtenir la solution globale.

La programmation linéaire : elle permet de modéliser le problème sous la forme d’un programme linéaire et
d’utiliser des techniques d’optimisation linéaire pour trouver la solution optimale.

Méthodes approchées :

Dans certains cas, les méthodes exactes nécessitent un temps de résolution trop long, c’est pourquoi des méthodes

approchées [10] sont utilisées. Ces méthodes, également appelées méthodes approximatives, permettent d’obtenir
rapidement de bonnes solutions, mais sans garantie d’optimalité. Elles englobent deux classes :
Les heuristiques : ce sont des règles empiriques simples qui exploitent la structure du problème. Elles

conduisent généralement à des solutions sous-optimales, mais elles convergent rapidement vers de bonnes solutions.
Il existe deux types d’heuristiques principalement utilisés : les heuristiques de construction (méthodes gloutonnes)
qui construisent la solution de manière itérative, et les heuristiques de descente qui, à partir d’une solution donnée,
cherchent un optimum local.

Les métaheuristiques : ce sont des méthodes de résolution plus générales qui peuvent être appliquées à un large
éventail de problèmes. Contrairement aux heuristiques, les métaheuristiques ne sont pas spécifiques à un problème
particulier. Parmi les métaheuristiques les plus courantes, on peut citer la recherche locale itérative, la recherche

19
de voisinage variable, la recherche taboue, l’algorithme de recuit simulé, la recherche en essaim et l’algorithme
génétique.
Dans ce mémoire, nous nous intéresserons plus particulièrement à la recherche taboue.

3.4 Algorithme de recherche taboue

La recherche taboue est une méthode heuristique de recherche locale utilisée pour résoudre des problèmes com-
plexes. Elle permet de trouver rapidement des solutions optimales en explorant un voisinage de solutions possibles.

La méthode de recherche taboue a été proposée pour la première fois par Fred Glover en 1986 comme une alterna-
tive aux méthodes déterministes existantes. Depuis sa création, cette méthode a connu de nombreuses améliorations
et variations afin d’améliorer ses performances. La recherche taboue est particulièrement utile pour résoudre des
problèmes d’optimisation difficiles pour lesquels les méthodes d’optimisation classiques ne donnent pas de résultats

satisfaisants. Elle a été utilisée avec succès dans de nombreux domaines tels que la logistique, la planification de la
production, la conception de circuits intégrés et l’analyse financière.

Principe de la recherche taboue :

Le principe de la recherche taboue repose sur l’exploration d’un voisinage de solutions à partir d’une solution
initiale, tout en évitant certains mouvements qui mèneraient à des solutions non souhaitables ou interdites. L’objectif
est d’explorer différents points de recherche afin d’atteindre l’optimum global dans le cas de la minimisation ou le

maximum global dans le cas de la maximisation.

L’algorithme de la recherche taboue met en œuvre ce principe en utilisant une mémoire appelée liste taboue.
Cette liste stocke les solutions déjà explorées et les rend interdites pour une certaine durée, ce qui permet de

poursuivre la recherche de manière intelligente. Toute solution figurant dans la liste taboue est appelée solution
taboue. Le rôle de la liste taboue évolue au cours de la résolution. Durant les itérations, de nouvelles solutions sont
ajoutées à la liste et des solutions existantes peuvent en être retirées (si le tabou est levé).
À chaque itération, la nouvelle solution choisie ne doit pas appartenir à la liste taboue. La durée de présence d’une

solution dans la liste dépend de la longueur maximale fixée pour cette liste. Après un certain nombre d’itérations,
une solution taboue peut être retirée de la liste, ce qui permet de l’utiliser à nouveau. Il est donc nécessaire de
définir un nombre maximal d’itérations.

20
 Début

Solution initiale

Générer un ensemble de solutions voisines

évaluer les solutions

mettre à jour
Sélectioner la meilleure solution admissible
la liste taboue

NON
Critères d’arrêt atteint ?

OUI

Stop

Fin

Figure 3.1 – Organigramme de l’algorithme de recherche taboue.

21
Algorithme glouton :

Dans le cadre de notre étude sur la coloration des sommets, nous souhaitons résoudre le problème de coloration
en utilisant une approche gloutonne suivie d’une recherche taboue. Tout d’abord, nous allons appliquer l’algorithme

glouton pour obtenir une solution initiale. L’algorithme glouton attribue des couleurs aux sommets du graphe de
manière itérative en choisissant à chaque étape la couleur qui minimise les conflits avec les couleurs déjà attribuées
aux voisins. Cette approche donne généralement une coloration de bonne qualité. Une fois que nous aurons obtenu
cette solution initiale, nous l’utiliserons comme point de départ pour notre recherche taboue. La recherche taboue

est une technique d’optimisation qui explore l’espace des solutions en utilisant des mouvements locaux et en évitant
les boucles infinies grâce à une liste taboue. Nous espérons que cette combinaison de l’algorithme glouton suivi de
la recherche taboue nous permettra d’obtenir une coloration encore meilleure et plus proche de l’optimum global

du graphe.

Algorithm 1 Algorithme glouton

Entrée : Un graphe G = (V, E).
Sortie : Une k-coloration du graphe G.
s ← ∅ . colors ← liste de couleurs disponibles.
for i allant de 0 à n − 1 : do
voisins ← liste des couleurs des voisins de i dans s.
if voisins est non vide then
solution[i] ← min(ensemble des couleurs − ensemble des voisins)
end
else
solution[i] ← couleur aléatoire parmi les couleurs disponibles
end
Ajouter i à s avec la couleur solution[i].
end
Retourner solution

Algorithme de la recherche taboue :

Nous présentons ci-dessous l’algorithme de recherche taboue qui décrit le processus de recherche de la meilleure
solution :

Soit f la fonction objectif qui calcule le coût, représentant le nombre de couleurs différentes utilisées dans la
solution.

22
Algorithm 3 Algorithme de recherche taboue pour le problème de coloration des graphes.
Entrée : Un graphe G = (V, E).
Sortie : La meilleure solution retrouvée s∗ .
Initialiser le nombre de couleurs K trouvé en appliquant l’algorithme 3.4.
LT ← ∅ : % Initialiser la liste taboue LT comme étant vide.
T : % Introduire la taille de la liste taboue.
Imax : % Initialiser le nombre d’itérations maximum Imax .
I ← 0 % Initialiser l’itération courante I à 0.
s :← solution % Initialiser la solution s avec une solution initiale obtenue par l’algorithme 3.4.
s∗ ← s % Initialiser la meilleure solution s∗ avec s.

while (I < Imax %la condition d’arrêt n’est pas satisfaite) do

Générer le voisinage Ns de la solution s en permutant les couleurs des sommets.
for (∀v ∈ Ns ) do
for (chaque couleur c possible pour v en fonction de ses voisins) do
if (c n’est pas taboue dans LT pour le sommet v) then
Calculer le coût de v : f (v) si v est coloré en c.
end
end
Colorer v avec la couleur qui minimise f (v) et mettre à jour s∗ .
end
if (f (s∗ ) < f (s) et la couleur choisie pour s n’est pas taboue pour v) then
Ajouter la solution s∗ dans la liste taboue LT .
s ← s∗ (mettre à jour la solution s)
Mettre à jour le nombre de couleur k
end
if (|LT | = T ) then
Supprimer le tabou le plus ancien.
end
I ←I +1
end
return s∗ .

3.4.1 L’application de la Recherche Tabou sur le Graphe de petersen

Au cours de cette partie, nous allons d’abord appliquer l’algorithme glouton pour obtenir une solution initiale.
Ensuite, nous utiliserons cette solution comme point de départ pour appliquer l’algorithme de recherche tabou.

Commençons maintenant par les données d’entrée de l’algorithme, que nous appellerons les ”données”

(0) Données : graphe de petersen G=(E,V)

IM AX = 6
K = 10

T =5

23
 1

3
4 2
6 5

8 7

10 9

Application de l’algorithme glouton sur le graphe de Peterson :

(1) Données : Le graphe de petersen G.
Nombre de couleurs = n (n = 10).

(2) Initialisation : solution ← ∅ (liste vide au départ).

colors ← {rouge, vert, jaune, bleu, violet, rose, marron, gris, noir, orange}.

1
Itération 1

3 On choisit le sommet 1
4 2 Voisins ← {2,3,4}
6 5
Voisin n’est pas vide donc :
8 7 min = min{rouge, vert, jaune, bleu, violet, rose,
marron, gris, noir, orange}.
10 9 min ={rouge}.
solution = {(1 , rouge)}.

1
Itération 2

3 On choisit le sommet 2.
4 2 Voisins ← {1,5,9}.
6 5
Voisin n’est pas vide donc :
8 7 min = min{vert, jaune, bleu, violet, rose, marron,
gris, noir, orange}.
10 9 min = {vert}.
solution= {(1, rouge), (2, vert)}.

24
 1
Itération 3

3 On choisit le sommet 3.
4 2 Voisins ← {1, 7, 8}.
6 5
Voisin n’est pas vide donc :
8 7 min = min{jaune, vert, bleu, violet, rose, marron,
gris, noir, orange}.
10 9 min ={jaune}.
solution = {(1, rouge), (2, vert), (3, jaune)}.

1 Itération 4

On choisit le sommet 4.
3 Voisins ← {1, 6, 10}.
4 2 Voisin n’est pas vide donc :
6 5
min = min {vert, jaune, bleu, violet, rose, marron,
8 7 gris, noir, orange}.
min = {vert}.
10 9 solution = {(1, rouge), (2, vert), (3, jaune), (4,
vert)}.

1 Itération 5

On choisit le sommet 4.
3 Voisins ← {2, 6, 8}.
4 2 Voisin n’est pas vide donc :
6 5
min = min {bleu, rouge, violet, rose, marron, gris,
8 7 noir, orange}.
min = {bleu}.
10 9 solution = {(1, rouge), (2, vert), (3, jaune), (4,
vert), (5, bleu)}.

1 Itération 6

On choisit le sommet 6.
3 Voisins ← {4, 5, 7}.
4 2 Voisin n’est pas vide donc :
6 5
min = min {rouge, jaune, violet, rose, marron, gris,
8 7 noir, orange}.
min = {rouge}.
10 9 solution = {(1, rouge), (2, vert), (3, jaune), (4,
vert), (5, bleu), (6, rouge)}.

1
Itération 7

3 On choisit le sommet 7.
4 2 Voisins ← {3, 6, 9}.
6 5
Voisin n’est pas vide donc :
8 7 min = min {bleu, violet, rose, marron, gris, noir,
orange}.
10 9 min = {bleu}.
solution = {(1, rouge), (2, vert), (3, jaune), (4, vert), (5, bleu), (6,

25
 1
Itération 8

3 On choisit le sommet 8.
4 2 Voisins ← {3, 5, 10}.
6 5
Voisin n’est pas vide donc :
8 7 min = min{rose, rouge, vert, violet, marron, gris, noir, orange}.
min = {rose}.
10 9 solution = {(1, rouge), (2, vert), (3, jaune), (4,
vert), (5, bleu),(6, rouge),(7, bleu), (8, rose)}.

Itération 9
1
On choisit le sommet 9.
Voisins ← {2, 7, 10}.
3 Voisin n’est pas vide donc :
4 2 min = min{rouge, jaune, violet, rose, marron, gris,
6 5
noir, orange}.
8 7 min = {rouge}.
solution = {(1, rouge), (2, vert), (3, jaune), (4,
10 9 vert), (5, bleu), (6, rouge), (7, bleu), (8, rose), (9,
rouge)}.

Itération 10

On choisit le sommet 10.

Voisins ← {4, 8, 9}.
1 Voisin n’est pas vide donc :
min = min {bleu, violet, marron, gris, noir, orange}.
min = {bleu}.
3 solution = {(1, rouge), (2, vert), (3, jaune),(4, vert),
4 2 (5, bleu), (6, rouge), (7, bleu), (8, rose), (9, rouge),
6 5
(10, bleu)}.
8 7
Nous avons ainsi obtenu une coloration à l’aide de
10 9 l’algorithme glouton pour le graphe de Peterson, uti-
lisant 5 couleurs distinctes.

26
 Après avoir obtenu une solution initiale à l’aide de l’algorithme glouton pour le graphe de Peterson avec une
coloration utilisant 5 couleurs distinctes, nous pouvons maintenant procéder à l’application de l’algorithme de
recherche taboue dans le but d’améliorer cette solution.
Initialisation
1

S0 = {(1, rouge), (2, vert), (3, jaune),(4, vert), (5,

3 bleu), (6, rouge), (7, bleu), (8, rose), (9, rouge), (10,
4 2 bleu)}.
6 5
s∗ ← s0 , K = 5, I = 0.
8 7 LT = ∅.

10 9

1
Itération 1
Soit le sommet 1 : Les couleurs possibles pour 1
3 sont : {jaune, vert, bleu, rose}.
4 2 et leurs conflits sont respectivement {1, 2, 0, 0}.
6 5
S1 = {(1, bleu), (2, vert), (3, jaune), (4, vert), (5,
8 7 bleu), (6, jaune), (7, bleu), (8, rose), (9, rouge), (10,
bleu)}.
10 9 K = 5 ,I = 1.
LT = {(1, bleu)}.

1
Itération 2
Soit le sommet 2 : Les couleurs possibles pour 2
3 sont :{jaune, rouge, bleu, rose} et leurs conflits sont
4 2 respectivement {0, 1, 2, 0}.
6 5
S2 ={(1, bleu), (2, rose), (3, jaune), (4, vert), (5,
8 7 bleu), (6, jaune), (7, bleu), (8, rose), (9, rouge), (10,
bleu)}.
10 9 K = 5, I = 2.
LT = {(1, bleu), (2, rose)}.

27
 1
Itération 3
Soit le sommet 3 : Les couleurs possibles pour 3
3 sont : {vert, rouge, bleu, rose} et leurs conflits sont
4 2 respectivement {0, 0, 2, 1}.
6 5
S3 = {(1, bleu), (2, rose), (3, rouge), (4, vert), (5,
8 7 bleu), (6, jaune), (7, bleu) ,(8, rose), (9, rouge), (10,
bleu)}.
10 9 K = 5, I = 3.
LT = {(1, bleu), (2, rose), (3, rouge)}

1
Itération 4
Soit le sommet 4 : Les couleurs possibles pour 4
3 sont : {rouge, bleu, rose, jaune} et leurs conflits sont
4 2 respectivement {0, 2, 0, 1}.
6 5
S4 = {(1, bleu), (2, rose), (3, rouge), (4, rose), (5,
8 7 bleu), (6, jaune), (7, bleu), (8, rose), (9, rouge), (10,
bleu)}.
10 9 K = 4, I = 4.
LT = {(1, bleu), (2, rose), (3, rouge), (4, rose)}.

1
Itération 5
Soit le sommet 5 : Les couleurs possibles pour 5
3 sont : {rouge, rose, jaune}, et leurs conflits sont
4 2 respectivement {0, 2, 1}.
6 5
S5 = {(1, bleu), (2, rose), (3, rouge),(4, rose), (5,
8 7 rouge), (6, jaune), (7, bleu), (8, rose), (9, rouge),(10,
bleu)}.
10 9 K = 4, I = 5.
LT = {(1, bleu), (2, rose), (3, rouge), (4, rose), (5, rouge)}.

28
 Itération 6
Soit le sommet 6 : Les couleurs possibles pour
6 sont : {rouge,rose, bleu}. et leurs conflits sont
respectivement {1, 1, 1}.
donc aucune couleur n’est disponible pour le som-
1 met 6.
FIN.
K = 4, I = 6.
3 LT = {(2, rose), (3, rouge), (4, rose), (5, rouge), (6, rose)}.
4 2 I = IM AX , fin.
6 5
En appliquant l’algorithme de recherche taboue,
8 7 nous avons réussi à améliorer la solution initiale de
la coloration des sommets du graphe de Peterson,
10 9 trouvée par l’algorithme glouton, passant ainsi de 5
couleurs à 4 couleurs.

3.5 Conclusion

Les résultats obtenus démontrent que la méthode de recherche taboue peut être appliquée avec succès pour
résoudre de nombreux problèmes d’optimisation, y compris celui de la coloration des graphes. Cette méthode heu-

ristique s’avère très fiable pour obtenir une solution approximative à une grande variété de problèmes d’optimisation
combinatoire dans divers domaines, tout en demandant moins de temps de recherche.

29
Chapitre 4

Implémentation

4.1 Introduction

Un langage de programmation est un langage informatique qui permet de formuler des algorithmes et de produire
des instructions qui seront exécutées par un ordinateur. Il existe plusieurs langages de programmation, tels que
Python, Java et Matlab, chacun offrant ses propres caractéristiques et domaines d’application.

Dans ce chapitre, notre attention sera portée sur l’implémentation de l’algorithme de recherche taboue pour
résoudre le problème de coloration des graphes en utilisant le langage de programmation Python.

4.2 Pourquoi Python ?

Le langage Python est un langage de programmation de haut niveau et interprété, qui a été créé au début des
années 1990 par Guido Van Rossum. Contrairement à des langages comme le C, Python n’a pas besoin d’être compilé
avant d’être exécuté. Il est directement interprété par l’ordinateur, ce qui facilite son utilisation et sa portabilité.

Python est un langage open source, ce qui signifie que son code source est accessible à tous et peut être modifié
et distribué librement. Cette caractéristique a contribué à la popularité croissante de Python, qui est aujourd’hui
largement utilisé dans différents domaines, tels que :

— La Programmation d’applications.
— La création de services web.
— La génération de code.
— La métaprogrammation.

30
Configuration de la machine utilisée :

L’algorithme a été exécuté sur une machine avec les spécifications suivantes :
— Appareil : LAPTOP-CV1QUAL1.

— Processeur : Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz 2.00 GHz.

— Mémoire RAM installée : 8,00 Go.
— Système d’exploitation : Système d’exploitation 64 bits, processeur x64.
— Fonctionnalités : Prise en charge de la fonction tactile avec 2 points de contact.

4.3 Implémentation en Python de l’algorithme de recherche taboue

pour la coloration des graphes
Bibliothèques Python utilisées :

networkx : une bibliothèque Python permettant de manipuler des graphes et des réseaux.
[Link] : une bibliothèque Python permettant de créer des graphiques et des visualisations.
random : une bibliothèque Python permettant de générer des nombres aléatoires.

collections : une bibliothèque Python qui fournit des alternatives hautement optimisées aux types de données
intégrés tels que les listes, les tuples et les dictionnaires.

Variables et fonctions utilisées

Les variables et fonctions utilisées dans l’algorithme de recherche taboue pour la résolution du problème de
coloration des graphes sont les suivantes :
graphe : La structure de données que nous avons utilisée pour représenter le graphe en entrée est la matrice

d’adjacence M .
Nombre de couleurs disponibles : Ce paramètre spécifie le nombre de couleurs différentes qui peuvent
être utilisées pour colorier les sommets.

Nombre maximal d’itérations : Ce paramètre spécifie le nombre maximum d’itérations que l’algorithme
doit effectuer avant de s’arrêter.
Taille de la liste taboue : Ce paramètre spécifie la taille de la liste taboue utilisée par l’algorithme.
Nombre de répétitions : Ce paramètre spécifie le nombre de fois que l’algorithme doit répéter chaque

itération.
lListe de couleurs : Une liste des k couleurs disponibles pour la coloration des sommets.
File représentant la liste taboue : Une file de taille fixe contenant les mouvements récemment effectués

qui ne sont pas autorisés pour les itérations suivantes.

Solution : Un dictionnaire contenant la couleur actuelle de chaque sommet dans le graphe.

31
 Ensemble de mouvements candidats : Un ensemble de mouvements possibles qui peuvent être effectués
à chaque itération.
Nombre de conflits : Le nombre de conflits actuels dans la solution.
Nouvelle solution : La solution générée lors d’une itération de l’algorithme.

Niveau d’aspiration : Un dictionnaire contenant le niveau d’aspiration pour chaque nombre de conflits.
Nombre de conflits dans la nouvelle solution : Le nombre de conflits dans la nouvelle solution générée
lors d’une itération.

Fonction de vérification de la liste taboue : Une fonction qui vérifie si un mouvement est autorisé selon
la liste taboue.
Fonction Initial solution : Une fonction qui prend en entrée un graphe et le nombre de couleurs dispo-
nibles, et qui renvoie une solution initiale aléatoire pour la coloration du graphe. Cette solution consiste à

attribuer une couleur aléatoire à chaque sommet du graphe. Si un sommet a des voisins qui ont déjà une
couleur attribuée, il reçoit une couleur différente de celle de ses voisins.
Fonction nombre chromatique : Une fonction qui prend en entrée un graphe et la meilleure solution de
coloration, et qui renvoie le nombre chromatique du graphe.

4.3.1 La fonction principale

1 def tabou_coloration ( graphe , nb_de_coleurs , max_iterations , taille_tabou , max_reps ) :

2

La fonction tabou coloration utilise une approche de recherche taboue pour trouver une solution de coloration
d’un graphe qui minimise lse nombre de conflits. Elle accepte en paramètres un graphe, le nombre de couleurs
disponibles, le nombre maximum d’itérations, la taille de la liste taboue et le nombre maximum de répétitions.

La fonction itère jusqu’à ce que le nombre maximum d’itérations soit atteint, ou qu’aucun conflit ne soit détecté,
ou que le nombre maximum de répétitions soit atteint. À chaque itération, la fonction génère une liste de mouvements
candidats, puis choisit un mouvement à partir de cette liste en utilisant une stratégie basée sur la liste taboue et le

niveau d’aspiration. La liste taboue est mise à jour à chaque itération pour conserver les mouvements récemment
effectués.
À la fin de l’algorithme, la fonction renvoie la meilleure solution trouvée ainsi que son nombre chromatique,
c’est-à-dire le nombre de couleurs différentes utilisées dans la solution.

Le programme en Python

Ci-dessous la fonction Python de de la liste taboue :

3 def tabu_list ( tabu_list , move , tabu_size ) :
4 if move in tabu_list :
5 return False
6 else :
7 tabu_list . append ( move )

32
8 if len ( tabu_list ) > tabu_size :
9 tabu_list . popleft ()
10 return True
11

Pour obtenir une coloration initiale des sommets du graphe en entrée, nous avons utilisé une heuristique gloutonne
que nous présentons dans la fonction Python suivante :
12 def initial_solution ( graphe , nb_de_coleurs ) :
13 solution = dict ()
14 colors = list ( range ( nb_de_coleurs ) )
15 for i in range ( len ( graphe ) ) :
16 voisins = [ solution [ j ] for j in range ( len ( graphe ) ) if graphe [ i ][ j ] > 0 and j in
solution ]
17 if voisins :
18 solution [ i ] = min ( set ( colors ) - set ( voisins ) )
19 else :
20 solution [ i ] = colors [ randrange (0 , len ( colors ) ) ]
21 return solution
22

Nous présentons ci-dessous le programme principal en Python de l’algorithme de recherche taboue pour résoudre
le problème de coloration des graphes :
23 def tabou_coloration ( graphe , nb_de_coleurs , max_iterations , taille_tabou , max_reps ) :
24 solution = initial_solution ( graphe , nb_de_coleurs )
25 best_solution = solution . copy ()
26 best_conflicts = sum ( graphe [ i ][ j ] > 0 and solution [ i ] == solution [ j ] for i in range (
len ( graphe ) ) for j in range ( i ) )
27 tabu_liste = deque ()
28 aspiration_level = dict ()
29 it ration = 0
30 while i t r a t i o n < max_iterations and best_conflicts > 0 and max_reps > 0:
31 max_reps -= 1
32 move_candidates = []
33 conflicts = {}
34 for i in range ( len ( graphe ) ) :
35 old_color = solution [ i ]
36 for new_color in range ( nb_de_coleurs ) :
37 if new_color != old_color :
38 new_solution = solution . copy ()
39 new_solution [ i ] = new_color
40 move_candidates . append (( i , new_color ) )
41 conflicts [( i , new_color ) ] = sum ( graphe [ i ][ j ] > 0 and new_solution [ i ]
== new_solution [ j ] for j in range ( len ( graphe ) ) )
42 sorted_moves = sorted ( conflicts . items () , key = lambda x : x [1])
43 move_candidates = [ move for move , conf in sorted_moves if conf == sorted_moves
[0][1]]
44 move = choice ( move_candidates )
45 tabu = tabu_list ( tabu_liste , move , taille_tabou )
46 if tabu :
47 solution [ move [0]] = move [1]
48 conflicts = sorted_moves [0][1]
49 if conflicts < best_conflicts :
50 best_solution = solution . copy ()
51 best_conflicts = conflicts
52 aspiration_level = { k : v - 1 for k , v in aspiration_level . items () if v > 1}
53 if move [1] != old_color and ( move [0] not in aspiration_level or aspiration_level
[ move [0]] <= 0) :
54 aspiration_level [ move [0]] = taille_tabou

33
55 i t r a t i o n += 1
56 return best_solution
57

La fonction Python suivante affiche la meilleure solution retrouvée par la méthode de recherche taboue :
58 def no mb re _chromatique ( best_solution ) :
59 return len ( set ( best_solution . values () ) )
60

Nous appliquons ce programme sur le graphe de Peterson et nous retournons le résultat de l’exécution.

3
4 2

5 1

6 12

7 11

8 10
9

Nous allons chercher le nombre chromatique du graphe G en appliquant l’algorithme :

34
 La matrice d’adjacence du graphe de Petrson :
1

3 graphe = [[0 , 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0] ,
4 [1 , 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0] ,
5 [0 , 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0] ,
6 [0 , 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0] ,
7 [1 , 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0] ,
8 [0 , 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1] ,
9 [1 , 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1] ,
10 [0 , 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1] ,
11 [0 , 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0] ,
12 [1 , 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] ,
13 [0 , 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0] ,
14 [0 , 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0]]
15

16 best_solution = tabou_coloration ( graphe )

17 print ( best_solution )

Nous utilisons cette fonction Python pour illustrer le résultat trouvé :

61

62 G = nx . Graph ()
63 for i in range ( len ( graphe ) ) :
64 G . add_node ( i )
65 for j in range (i , len ( graphe ) ) :
66 if graphe [ i ][ j ] > 0:
67 G . add_edge (i , j )
68

69

70 node_colors = [ best_solution [ i ] for i in range ( len ( graphe ) ) ]

71

72

73 pos = nx . spring_layout ( G )
74

75

76 nx . dr a w _n e t workx_nodes (G , pos , node_color = node_colors , cmap = plt . cm . Set1 )

77 nx . dr a w _n e t workx_edges (G , pos )
78 nx . d r a w _ n e t w orkx_labels (G , pos )
79 plt . axis ( ’ off ’)
80 plt . show ()

35
 Ici, nous affichons le résultat de l’exécution :

4.4 Expérimentations

Au cours de cette section du chapitre, nous appliquerons l’algorithme de recherche taboue sur plusieurs graphes
générés aléatoirement. Chaque graphe sera soumis à 10 exécutions de l’algorithme, et les résultats obtenus seront
présentés dans un tableau. Le tableau indiquera le nombre maximal, minimal et moyen de couleurs obtenues sur

les 10 exécutions. Cette approche nous permettra de tester le déroulement de la méthode de recherche taboue dans
différentes conditions et d’analyser ses performances en détail.

Instances n m Solution initiale Nombre de couleurs k t(ms)

kmin kmoy kmax
inst 10 nodes 10 26 8 4 5 5 0.51
inst 20 nodes 20 94 11 6 7 7 2.76
inst 30 nodes 30 208 14 8 10 11 4.82
inst 50 nodes 50 633 20 12 13 14 13.9
inst 100 nodes 100 2482 28 20 22 23 68.72
inst 150 nodes 150 5547 50 29 30 30 159.99
inst 200 nodes 200 9861 76 29 30 31 257.07

4.5 Conclusion

Après avoir appliqué l’algorithme de recherche taboue à des instances aléatoires, il a été constaté que la solution
obtenue n’est pas toujours optimale et peut être assez éloignée de l’optimalité dans certains cas. Cela suggère que

cette méthode ne peut pas garantir l’optimalité et le nombre chromatique minimum, mais elle fournit néanmoins
des solutions de qualité acceptable dans un temps réduit.
Il est également remarqué que la qualité de la solution obtenue dépend de plusieurs paramètres. Dans notre cas,
nous avons utilisé l’heuristique gloutonne pour déterminer le nombre initial de couleurs et avons choisi une taille de

36
liste taboue proportionnelle au nombre de sommets du graphe en entrée. Cependant, en ajustant ces paramètres, il
serait possible d’obtenir d’autres solutions, parfois même la solution optimale.
En conclusion, la recherche taboue reste une méthode heuristique efficace et utile pour résoudre les problèmes
d’optimisation combinatoire difficiles.

37
Conclusion générale

Au cours de ce mémoire, notre objectif était d’utiliser la recherche taboue pour résoudre le problème de coloration,
qui est un problème de la théorie des graphes consistant à attribuer des couleurs aux sommets d’un graphe de sorte
que deux sommets adjacents n’aient pas la même couleur.
Nous avons commencé par introduire les notions générales de la théorie des graphes. Ensuite, nous avons abordé

la problématique de la coloration des graphes et proposé sa résolution à travers l’algorithme de recherche taboue,
connu pour son efficacité dans la fourniture de colorations quasi optimales dans la plupart des cas.
Nous avons ensuite procédé à l’implémentation de l’algorithme, ce qui nous a permis d’évaluer son fonctionnement
et son degré d’optimalité.

La coloration des graphes est l’un de ces problèmes mathématiques qui, bien qu’ils soient faciles à énoncer et à
visualiser, comportent de nombreux aspects exceptionnellement difficiles à résoudre. Toutefois, grâce à des méthodes
de résolution et à divers algorithmes, nous avons pu fournir une approche théorique du problème et l’appliquer à

des problèmes du monde réel.

En conclusion, ce mémoire nous a permis d’approfondir notre compréhension du problème de la coloration
des graphes et d’enrichir nos connaissances dans ce domaine. Il nous a également permis de nous initier à la
programmation en utilisant Python et de découvrir les nombreuses fonctionnalités de ce langage, que nous espérons

maı̂triser davantage à l’avenir.

38
Bibliographie

[1] David Défossez. Coloration d’hypergraphes et clique-coloration. l’École Doctorale ≪ Mathématiques, Sciences
et Technologies de l’Information, Informatique, 12 octobre 2006.

[2] [Link] et collectif. La Théorie des graphes. Pages Bleues, 2002/2003.

[3] Cour Théorie des Graphes. 2022/2023.

[4] Didier Muler. Introduction a la théorie des graphes. COMMISSION ROMANDE DE MATHÉMATIQUE,
2012.

[5] Stephen A. Cook. The Complexity of Theorem-Proving Procedures. University of Toronto.

[6] Olivier Togni. L3 : cours Graphes Chapitre III : coloration de graphe. 7 janvier 2019.

[7] Olivier Togni. Théorème (Appel Haken, 1976) :

L3 : cours Graphes Chapitre III : coloration de graphe. 7 janvier 2019.

[8] Olivier Togni. Théorème (Grotzsch, 1959) :

L3 : cours Graphes Chapitre III : coloration de graphe. 7 janvier 2019.

[9] Olivier Togni. Théorème (Askionov, 1974) :

L3 : cours Graphes Chapitre III : coloration de graphe. 7 janvier 2019.

[10] [Link]. Chapitre iv :heuristiques et meta-heuristique, 2015/2016.

39