Embedded Files
suffit-il de 4 couleurs pour dessiner n'importe quelle carte géographique ?
D’autres problèmes plus pratiques peuvent se ramener au problème de la coloration d'une carte, d'un graphe :
- Affecter des fréquences différentes à des cellules voisines dans un réseau de téléphone mobile GSM.
- Organiser un examen suivant les matières que doit passer chaque étudiant. Comment mettre en parallèle plusieurs épreuves sans léser un candidat ?
- Optimiser l'utilisation des machines de travail. Comment mettre en parallèle des fabrications utilisant plusieurs machines ?
- Problème d'incompatibilité. Comment faire cohabiter des personnes ou des animaux en tenant compte de leur incompatibilité ?
- La résolution du Sudoku peut se ramener à un problème de coloration de graphe.
VIDEO
POSTER
DIAPO
ARTICLE
ACTIVITE DE RECHERCHE
Cet atelier permet aux élèves de découvrir la notion de coloration de graphes et son intérêt pour la modélisation.
On commence par une activité grandeur nature. Chaque élève reçoit un prénom et une liste de personnes avec qui il ou elle ne veut absolument pas être assis·e à table. Objectif : faire le plan de table de sorte à ce que personne ne soit assis·e avec quelqu’un·e qu’il ou elle n’aime pas.
Ensuite, les élèves travaillent sur la représentation de ce problème pour arriver à la modélisation de celui-ci en termes de coloration de graphes. Mais comment colorer un graphe de sorte que deux sommets reliés par une arête ne soient pas de la même couleur ? Est-ce possible ? Avec combien de couleurs ? Existe-t-il des algorithmes qui permettent de le faire efficacement ?
COLORATION
Nombre chromatique
Nombre chromatique
Colorier un graphe c'est colorier les sommets de telle façon que deux sommets distincts et adjacents aient toujours des couleurs différentes.
Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorier le graphe.
L'algorithme de Welsh Powell est un algorithme qui permet de trouver une bonne coloration d'un graphe, c'est à dire une coloration utilisant le moins de couleurs possible, sans garantie toutefois qu'elle soit optimale (avec le nombre minimum de couleur qu'il faudrait pour colorer le graphe). L'algorithme a cependant l'avantage d'être assez simple dans son fonctionnement et de s'exécuter rapidement.
Étapes de l'algorithme :
Classer les sommets par degrés décroissants.
En parcourant la liste dans l’ordre ainsi créé, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur.
S’il reste des sommets non colorés dans le graphe, revenir à l’étape 2. Sinon, FIN.
TH DES 5 COULEURS
Page updated
Google Sites
Report abuse