- Finalisation du diaporama
- Finalisation de l’archive
Auteur : grillschuimer
Compte rendu 11|01|2015
- Finalisation du diaporama
- Ajout des CR dans le mémoire
Compte rendu 06|01|2016
- Rédaction et transferts des annexes (auto-évaluations, glossaire …)
- Début du diaporama
Compte-rendu 15|12|2015
- Mémoire quasi terminé (il reste le bilan du projet à faire)
- Affiche terminée
- Toutes les sources ont été mises à jour
- Diapo commencé
Compte-rendu 11/12/2015
- Toutes les parties sont terminées sauf le bilan du projet
- Le mémoire est quasi complet
- L’affiche est dans un stade avancé
Partie IV : Adaptation de l’algorithme sous forme d’un exemple concret
1. L’exemple choisi : Cartographie
Nous avons choisi de travailler sur un exemple vu en première année : la coloration d’une carte et principalement celle des régions de la France (Les anciennes : 22).
La cartographie est un exemple concret de l’application des algorithmes de coloration et de nombreuses hypothèses sont alors effectuées sur le nombre chromatique nécessaire à la coloration des cartes notamment le plus connu d’entre eux : le théorème des 4 couleurs.
Pour le cas de la coloration d’un pays, si deux pays possèdent une frontière commune, il faut relier les deux capitales. Alors le réseau des liens entre capitales, le graphe, avec ses sommets colorés est équivalent à la carte initiale en termes de coloration.
2. Mise en place du programme sous le langage choisi : Java
Le programme Java est décomposé en plusieurs classes :
La classe Sommet :
Sa structure est la suivante : il est définit par un numéro qui correspond au numéro du sommet dans le futur graphe, d’une chaîne de caractère qui correspond à son Nom qui sera également utile par la suite dans les graphes et surtout pour la cartographie, il est également défini par une couleur qui est initialisé à blanc par défaut, également d’une liste de sommet qui correspond au sommet adjacent au sommet en question. La classe dispose également d’un ensemble de getter et setter pour récupérer et configurer les différents paramètres du sommet. Ainsi que des méthodes permettant l’ajout de sommet adjacent, la vérification d’un sommet adjacent par rapport à un autre, une méthode de calcul du degré d’un sommet, une méthode d’affichage des sommets adjacents et une méthode d’affichage du sommet.
La classe Graphe:
Elle principalement défini par un ensemble de sommets mais également un nombre chromatique qui est initialisé à 0 par défaut, cette classe comprend également les méthodes permettant la récupération et la modification des données du graphes.
La classe comprend également des méthodes de calcul du nombre chromatique max, du sommet ayant le plus grand degré et également la méthode permettant de trié les sommets du graphes en fonction de leurs degré pour les mettre en forme avant l’exécution de Welsh-Powel
La classe Algorithme:
Elle est uniquement constitué de l’algorithme de Welsh-Powel, elle prend en paramètre un Graphe et le ressort colorié par la méthode de Welsh-Powel, nous avions créer cette classe de façon extérieur afin de faire agir l’algorithme sur le graphe et ne pas exécuter une méthode présente dans la classe graphe c’est également plus pratique d’un point de vue de la lisibilité.
Les classes de test :
- Exemple et Contre Exemple :
Cette classe présente les exemples et contre exemple évoqué dans la partie précédente, elle permet de vérifié que le résultat attendu correspond bien à ce que nous avions trouvé à la main y compris pour le contre-exemple qui prouve le manque d’efficacité dans certain cas.
- France
Cette classe permet de montrer le fonctionnement de l’algorithme sur la carte de la France .
- Dynamique
Cette classe permet de tester de façon dynamique une graphe rentré en directe et avoir une vue directe de la coloration de ce graphe sans devoir créer toutes les classes et les attributs à la main.
3. Démonstration du programme
Démonstration des exemples et contre-exemple :
Ensemble des 5 graphes :
Graphe 1 :
Graphe constituer de 1 sommet(s)
Nombre Chromatique : 1
N1 Couleur : rouge
-> Adjacent : S1 est isolé !
_______________________________________
Graphe 2 :
Graphe constituer de 2 sommet(s)
Nombre Chromatique : 2
N1 Couleur : rouge
-> Adjacent : 2 |
N2 Couleur : bleu
-> Adjacent : 1 |
_______________________________________
Graphe 3 :
Graphe constituer de 3 sommet(s)
Nombre Chromatique : 3
N1 Couleur : rouge
-> Adjacent : 2 | 3 |
N2 Couleur : bleu
-> Adjacent : 1 | 3 |
N3 Couleur : vert
-> Adjacent : 1 | 2 |
_______________________________________
Graphe 4 :
Graphe constituer de 4 sommet(s)
Nombre Chromatique : 2
N1 Couleur : rouge
-> Adjacent : 2 | 4 |
N2 Couleur : bleu
-> Adjacent : 1 | 3 |
N3 Couleur : rouge
-> Adjacent : 2 | 4 |
N4 Couleur : bleu
-> Adjacent : 1 | 3 |
_______________________________________
Graphe 5 :
Graphe constituer de 5 sommet(s)
Nombre Chromatique : 3
N1 Couleur : rouge
-> Adjacent : 2 | 5 |
N2 Couleur : bleu
-> Adjacent : 1 | 3 |
N3 Couleur : rouge
-> Adjacent : 2 | 4 |
N4 Couleur : bleu
-> Adjacent : 3 | 5 |
N5 Couleur : vert
-> Adjacent : 1 | 4 |
Contre Exemple :
Le résultat attendu est une coloration avec 2 couleurs
Graphe constituer de 8 sommet(s)
Nombre Chromatique : 3
N2 Couleur : rouge
-> Adjacent : 1 | 3 | 8 |
N3 Couleur : bleu
-> Adjacent : 2 | 4 |
N4 Couleur : rouge
-> Adjacent : 3 | 5 |
N5 Couleur : rouge
-> Adjacent : 6 | 6 |
N7 Couleur : bleu
-> Adjacent : 5 | 8 |
N8 Couleur : vert
-> Adjacent : 2 | 7 |
N1 Couleur : bleu
-> Adjacent : 2 |
N6 Couleur : bleu
-> Adjacent : 5 |
La carte de la France colorié par le programme :
Carte de la France
_______________________________________
Graphe constituer de 22 sommet(s)
Nombre Chromatique : 4
Centre N12 Couleur : rouge
-> Adjacent : 2 | 3 | 10 | 11 | 13 | 14 | 15 | 16 |
Bourgogne N10 Couleur : bleu
-> Adjacent : 6 | 9 | 11 | 12 | 16 | 17 |
Auvergne N16 Couleur : vert
-> Adjacent : 10 | 12 | 15 | 17 | 19 | 20 |
Champagne Ardenne N6 Couleur : rouge
-> Adjacent : 4 | 7 | 9 | 10 | 11 |
Franche Comté N9 Couleur : vert
-> Adjacent : 6 | 7 | 8 | 10 | 17 |
Ile de France N11 Couleur : vert
-> Adjacent : 3 | 4 | 6 | 10 | 12 |
Limousin N15 Couleur : bleu
-> Adjacent : 12 | 14 | 16 | 18 | 19 |
Rhone Alpes N17 Couleur : rouge
-> Adjacent : 9 | 10 | 16 | 20 | 21 |
Languedoc Roussillon N20 Couleur : bleu
-> Adjacent : 16 | 17 | 19 | 21 | 22 |
Basse Normandie N2 Couleur : bleu
-> Adjacent : 1 | 3 | 12 | 13 |
Haute Normandie N3 Couleur : jaune
-> Adjacent : 2 | 4 | 11 | 12 |
Picardie N4 Couleur : bleu
-> Adjacent : 3 | 5 | 6 | 11 |
Pays de la Loire N13 Couleur : vert
-> Adjacent : 1 | 2 | 12 | 14 |
Poitou Charente N14 Couleur : jaune
-> Adjacent : 12 | 13 | 15 | 18 |
Midi Pyrénéens N19 Couleur : rouge
-> Adjacent : 15 | 16 | 18 | 20 |
Lorraine N7 Couleur : bleu
-> Adjacent : 6 | 8 | 9 |
Aquitaine N18 Couleur : vert
-> Adjacent : 14 | 15 | 19 |
PACA N21 Couleur : vert
-> Adjacent : 17 | 20 | 22 |
Bretagne N1 Couleur : rouge
-> Adjacent : 2 | 13 |
Alsace N8 Couleur : rouge
-> Adjacent : 7 | 9 |
Corse N22 Couleur : rouge
-> Adjacent : 20 | 21 |
Nord Pas de Calais N5 Couleur : rouge
-> Adjacent : 4 |
4. Bilan
Compte-rendu 04|12|2015
- Partie III terminée
- Partie IV quasiment terminée
- Mémoire en format .word avancé
- Début de la réalisation de l’affiche
Partie III : La coloration par Welsh-Powel
1. Principe
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 seront plus difficiles à colorer, et donc il faut les colorer en premier. La complexité de l’algorithme devient O(n ln n + m) en utilisant un tri par comparaison, mais reste O(n + m) avec un tri par dénombrement. Cependant on peut parfois 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.
Il y a une certaine procédure à respecter afin de mettre en oeuvre cet algorithme.
Procédure :
- Repérer le degré de chaque sommet.
- Ranger les sommets par ordre de degrés décroissants (dans certains cas plusieurs possibilités).
- Attribuer au premier sommet (A) de la liste une couleur.
- Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
- Suivre (si possible) la liste jusqu’au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
- Continuer jusqu’à ce que la liste soit finie.
- Prendre une deuxième couleur pour le premier sommet (D) non encore coloré de la liste.
- Répéter les opérations 4 à 7.
- Continuer jusqu’à avoir coloré tous les sommets.
2. Algorithme
-
On note L la liste des sommets si classes suivant l’ordre décroissant de leur
-
degre : d(s1) d(s2) d(s3) ::: d(sn).
-
Initialisation :
-
L : liste des sommets dans l’ordre décroissant du degré
-
couleur = 0
-
Tant que L ≠ ∅ ; faire
-
couleur=couleur+1
-
couleur(s) = couleur
-
Pour tout t dans L faire
-
Si t ∉ Γs
-
couleur(t)=couleur
-
Γs = Γs ∪ Γt
-
Fin si
-
Fin faire
-
Retirer les sommets colores de L
-
Fin faire
3. Exemples
Prenons ces 5 graphes :
Graphe 1 :
Sommet | Degré | Successeurs |
1 | 0 | X |
Couleur/Sommet | 1 |
C1 : rouge | C1 |
Graphe 2 :
Sommet | Degré | Successeurs |
1 | 1 | 2 |
2 | 1 | 1 |
Couleur/Sommet | 1 | 2 |
C1 : rouge | C1 | |
C2 : bleu | X | C2 |
Graphe 3 :
Sommet | Degré | Successeurs |
1 | 2 | {2,3} |
2 | 2 | {1,3} |
3 | 2 | {1,2} |
Couleur/Sommet | 3 | 2 | 1 |
C1 : vert | C1 | ||
C2 : bleu | X | C2 | |
C3 : rouge | X | X | C3 |
Graphe 4 :
Sommet | Degré | Successeurs |
1 | 2 | {2,4} |
2 | 2 | {1,3} |
3 | 2 | {2,4} |
4 | 2 | {1,3} |
Couleur/Sommet | 4 | 3 | 2 | 1 |
C1 : bleu | C1 | C1 | ||
C2 : rouge | X | C2 | X | C2 |
Graphe 5 :
Sommet | Degré | Successeurs |
1 | 2 | {2,5} |
2 | 2 | {1,3} |
3 | 2 | {2,4} |
4 | 2 | {3,5} |
5 | 2 | {1,4} |
Couleur/Sommet | 5 | 4 | 3 | 2 | 1 |
C1 : bleu | C1 | C1 | |||
C2 rouge | X | C2 | X | C2 | |
C3 : Vert | X | X | X | X | C3 |
4. Contre-exemple
Afin de tester l’efficacité de l’algorithme de Welsh Powell, nous allons mettre en place un contre exemple.
Soit le graphe :
Nous allons dérouler l’algorithme de Welsh Powell normalement :
Sommet | Degré | Successeurs |
1 | 1 | 2 |
2 | 3 | {1,3,8} |
3 | 2 | {2,4} |
4 | 2 | {3,5} |
5 | 3 | {4,6,7} |
6 | 1 | 5 |
7 | 2 | {5,8} |
8 | 2 | {2,7} |
Couleur/sommet | 5 | 2 | 8 | 7 | 4 | 3 | 6 | 1 |
C1 (rouge) | C1 | C1 | ||||||
C2 (vert) | x | x | C2 | C2 | C2 | C2 | ||
C3 (bleu) | x | x | x | C3 | x | C3 | x | x |
Avec l’application de l’algorithme, on obtient alors cette coloration :
Hors, elle n’est pas optimale.
En effet, seul deux couleurs suffisent pour colorier ce graphe, tel que :
5. Limites
L’algorithme de Welsh Powell permet d’avoir une coloration des sommets cohérente.
Néanmoins, le contre-exemple montre bien que la coloration proposée n’est pas toujours optimale, car dans certains cas, un nombre plus restreint de couleurs peuvent être utilisées (voir ci-dessus).
Il est donc parfois plus simple d’étudier le graphe sans ce dernier et de trouver soi-même une coloration optimale, et ensuite vérifier sa coloration avec l’algorithme pour voir si elle est optimale ou non (à condition que le graphe soit facile de compréhension comme l’est notre contre-exemple).
Compte-rendu 30|11|2015
- Finalisation du programme Java
- Début de la rédaction du mémoire sous format Word
- Début de la rédaction de la partie III
Compte-rendu 27|11|2015
- Programme Java fonctionnel avec des exemples simples et début des tests sur la carte de la France.
- Partie II terminée (reste à ajouter les exemples DSATUR et RLF)
- Début de la partie III
- Ajout de nouvelles sources