Aspect historique et applications
Domaines d'applications
Comme mentionné dans l’article ‘Aspect historique’, la coloration de graphe a pour la première fois été énoncée pour des problèmes de coloration de cartes géographiques. Aujourd’hui encore, on utilise ce procédé pour ce domaine. En effet, la coloration de graphe est très utile pour élaborer des cartes géographiques lisibles. Par exemple, lors de l’élaboration d’une carte des régions de France, il est plus simple de séparer les régions en différentes couleurs. Des régions limitrophes ne peuvent donc pas être coloriés de la même couleur. Voici un exemple de carte utilisant la coloration :
Le principe de la coloration de graphe peut aussi être utilisé pour d’autres domaines. Par exemple, pour la confection d’emploi du temps, en réseaux de télécommunications, en chimie pour éviter le contact entre des produits dangereux, ou encore pour la résolution de Sudoku.
Sources:
pixabay.com/fr/illustrations/carte-de-la-france
Aspect historique
C’est au XIXème siècle que la théorie de la coloration de graphes a pour la première fois été évoquée. On s’interrogeait alors sur des problèmes de coloration de cartes géographiques. En 1852, Francis Guthrie (1831-1899, mathématicien sud-africain), énonça une conjecture, appelée le « problème des quatre couleurs ». Cette conjecture est la suivante : il est possible de colorer les sommets d’un graphe planaire en utilisant au plus quatre couleurs de telle sorte que toutes les arêtes aient des extrémités de couleurs différentes.
Pendant plus d’un siècle, plusieurs mathématiciens, dont A. De Morgan et W.R. Hamilton, tentèrent de résoudre ce problème, en vain. En 1879 et 1880, A. Kempe et P. Guthrie, publièrent deux démonstrations. Celles-ci furent démontées en 1890 par P. Heawood.
Ce n’est qu’en 1976, que Kenneth Appel et Wolfgang Haken, réussirent à démontrer le théorème. Ce théorème est aussi le premier problème mathématique démontré grâce à un ordinateur.
Sources:
cours-info.iut-bm.univ-fcomte.fr
researchgate.net/Graph_Coloring_History_results_and_open_problems