Algorithme de coloration de graphe

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

wikipedia.org/Coloration_de_graphe#Exemples_d'application

homepages.ulb.ac.be/~ecamby/Papiers/BSSM.pdf