Ayteur : Léa Chemoul
Dans le cadre de ce projet, nous cherchons à implémenter et à comparer des algorithmes de colorations sur des graphes non-orientés. Déterminer le nombre chromatique d’un graphe est un problème NP-difficile. Il n’existe donc pas à ce jour d’algorithme polynomial permettant de déterminer le nombre chromatique d’un graphe quelconque. Aussi, ce problème est finalement un problème d’optimisation. Nous l’étudions dans ce projet en nous posant la question suivante :” Pour un graphe G donné non-orienté, quel est le nombre minimum de couleurs nécessaires afin que la coloration de G soit valide”. Ces algorithmes fournissent une coloration explicite d’un graphe donné donc donnent un majorant du nombre chromatique, c’est à dire un nombre suffisant pour colorer le graphe de manière valide.
Langage : Java (JDK 8) Environnement de développement : Intellij Idea Librairies : En ouvrant un nouveau projet avec les sources disponibles, pensez à intégrer les librairies (/lib) relatives au projet. Outils de coloration : GRAPHVIZ