Projet Design & analysis of
algorithm
Sana Bhira
Feres Jerbi
Melek Hammami
• Un graphe est un schéma contenant des
points nommés sommets, reliés ou non
Notion de par des segments appelés arêtes.
graphe et • Un graphe est dit simple s’il ne
sous-graphe comporte aucune boucle et que deux
arêtes ne relient jamais la même paire de
sommets.
• Un graphe est dit complet si tous les
sommets sont adjacents les uns avec les
autres.
• Un sommet d’un graphe correspond à
Sommets, un point du graphe composé ou non par
arêtes, ordre des arêtes.
• Les arêtes représentent les liaisons entre
et degré d’un un sommet et un autre ou un sommet sur
graphe lui-même.
• L’ordre d’un graphe est le nombre de
sommets de ce graphe.
• Dans un graphe, le degré de chaque
sommet est le nombre d’arêtes dont il est
l’une des extrémités.
• En théorie des graphes , la coloration de
graphe consiste à attribuer une couleur à
chacun de ses sommets de manière que deux
sommets reliés par une arête soient de couleur
différente. On cherche souvent à utiliser le
nombre minimal de couleurs, appelé nombre
Problématique chromatique. La coloration
fractionnaire consiste à chercher non plus une
mais plusieurs couleurs par sommet et en
associant des coûts à chacune. Le champ
d'applications de la coloration de graphe couvre
notamment le problème de l'attribution de
fréquences dans les télécommunications, la
conception de puces électroniques .. etc
• L'importance du problème a donné lieu à
l'élaboration de nombreuses heuristiques
spécifiques au problème, spécialement
des algorithmes séquentiels de coloration
Solutions sommet par sommet (DSATUR, cosine,
existantes: maya, etc.). Elle a aussi suscité de
nombreuses expérimentations des
méthodes approchées générales : méta-
heuristique (recuit simulé, recherche
tabou), ou encore algorithme génétique.
Procédure:
1. Ordonner les sommets par ordre
décroissant de degré.
2. Colorer un sommet de degré maximum
avec la couleur 1.
Algorithme DSATUR 3. Choisir un sommet non coloré avec DSAT
maximum. Si conflit choisir celui avec
degré maximum.
4. Colorer ce sommet par la plus petite
couleur possible.
5. Si tous les sommets sont colorés alors
stop. Sinon aller en 3.
Procédure:
1. Choisir un sommet x de degré maximum.
Algorithme 2. Choisir un voisin de ce sommet y tel que
vc(x,y) soit maximum.
RLF 3. Contracter y en x.
4. Répéter 2 et 3 jusqu’à ce que x soit
voisin à tous les autres sommets.
5. Enlever le sommet x et reprendre à
l’étape 1.
• L’algorithme de Welsh & Powell consiste ainsi à
colorer séquentiellement le graphe en visitant les
sommets par ordre de degré décroissant. L’idée
est que les sommets ayant beaucoup de voisins
Principe de La seront plus difficiles à colorer, et donc il faut les
colorer en premier. La complexité de l’algorithme
coloration devient O(n ln n + m) en utilisant un tri par
par Welsh- comparaison, mais reste O(n + m) avec un tri par
dénombrement. Cependant on peut parfois
Powel aboutir aux pires colorations possibles ( n 2 au
lieu de 2). L’heuristique DSATUR propose une
amélioration du principe de l’algorithme de
Welsh & Powell afin d’éviter ce problème.
• Nous allons donc adopter cet algorithme puisqu'il
est le plus connu.
Procédure:
1. Repérer le degré de chaque sommet.
2. Ranger les sommets par ordre de degrés
décroissants (dans certains cas plusieurs
possibilités).
3. Attribuer au premier sommet (A) de la liste une
Algorithme couleur.
Welsh-Powel 4. Suivre la liste en attribuant la même couleur au
premier sommet (B) qui ne soit pas adjacent à (A).
5. Suivre (si possible) la liste jusqu’au prochain
sommet (C) qui ne soit adjacent ni à A ni à B.
6. Continuer jusqu’à ce que la liste soit finie.
7. Prendre une deuxième couleur pour le premier
sommet (D) non encore coloré de la liste.
8. Répéter les opérations 4 à 7.
9. Continuer jusqu’à avoir coloré tous les sommets.
1. On note L la liste des sommets si classes suivant l’ordre décroissant de leur
2. degre : d(s1) d(s2) d(s3) ::: d(sn).
3. Initialisation :
4. L : liste des sommets dans l’ordre décroissant du degré
5. couleur = 0
6. Tant que L ≠ ∅ ; faire
7. couleur=couleur+1
8. couleur(s) = couleur
9. Pour tout t dans L faire
L'algorithme : 10. Si t ∉ Γs
11. couleur(t)=couleur
12. Γs = Γs ∪ Γt
13. Fin si
14. Fin Pour
15. Retirer les sommets colorés de L
16. Fin Tant que
• Prenons ces graphes :
Des
Exemples :
Contre-Exemple :
• Afin de tester l’efficacité
de l’algorithme de Welsh
Powell, nous allons
mettre en place un
contre-exemple.
• Soit le graphe :
Contre-Exemple :
• Nous allons dérouler
l’algorithme de Welsh
Powell normalement :
Contre-Exemple :
• Avec l’application de l’algorithme, on obtient alors cette coloration :
Contre-Exemple :
• Hors, elle n’est pas
optimale.
En effet, seul deux
couleurs suffisent pour
colorier ce graphe, tel
que :
Implémentation de la solution avec Python