Planning final, bilan et sources
- Planning final:
- Bilan:
Pour colorier un graphe de manière optimale, il existe donc plusieurs méthodes et plusieurs algorithmes bien différents. Nous avons vu aussi qu’aucun des algorithmes étudiés ne présente un résultat parfait dans absolument tous les cas.
Nous avons tenté de réaliser deux algorithmes utilisant deux approches différentes, soit par le tri préalable des sommets, soit depuis un sommet initial. Cependant, nos algorithmes, tout comme les algorithmes existants, ne proposent pas dans tous les cas un résultat optimal. De plus, nos algorithmes élaborés, s’approchent des algorithmes glouton et Welsh-Powell au niveau de leur exécution.
Pour conclure, ce projet nous a permis de voir, qu’il peut être difficile de proposer une solution algorithmique nouvelle et la plus optimale possible, pour la coloration de graphe. Il était néanmoins intéressant d’étudier les différents algorithmes existants, et d’observer les différentes approches et solutions réalisées par leurs auteurs.
- Sources:
|
Sources |
Fiabilité |
|
- Définition des notions mathématiques : Nombre chromatique : https://www.alloprof.qc.ca/fr/eleves/bv/mathematiques/le-nombre-chromatique-m1015 Graphe : https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes#Graphe
|
Grâce aux connaissances acquises l’an dernier en mathématiques, nous avons pu nous assurer de la fiabilité de ces sources. |
|
- Aspect historique : https://cours-info.iut-bm.univ-fcomte.fr/wiki/pmwiki.php/Graphes/TP6bis https://www.researchgate.net/Graph_Coloring_History.pdf https://fr.wikipedia.org/wiki/Coloration_de_graphe#Historique
|
Pour nous assurer de proposer un aspect historique cohérent, nous avons consulté plusieurs sites, en vérifiant la similitude des événements évoqués. |
|
- Etudes des algorithmes : Welsh-Powell : https://fr.wikipedia.org/wiki/Algorithme_de_Welsh_et_Powell Glouton : https://en.wikipedia.org/wiki/Greedy_coloring Dsatur : https://fr.wikipedia.org/wiki/DSATUR Widgerson : https://fr.wikipedia.org/wiki/Algorithme_de_Wigderson
|
Pour l’algorithme de Welsh-Powell, nous avons eu l’occasion de l’étudier l’an dernier en module de mathématiques. Pour les autres algorithmes nous avons consulté plusieurs sites pour nous assurer de la fiabilité de ceux choisis. |
Inscrivez-vous au blog
Soyez prévenu par email des prochaines mises à jour
Rejoignez les 4 autres membres