Mois : décembre 2015

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.

Carte1Vide

 

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 :

GraphesTest

ContreExemple.

 

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  :

CarteRenduProgramme

 

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