La coloration d’une carte de pays consiste à attribuer une couleur à chacun des pays de manière à ce que deux pays voisins soient de couleurs différentes. Étudier ces techniques de coloration revient de façon plus abstraite à travailler sur des graphes. Le champ d’applications de la coloration de graphes est très vaste et couvre des domaines aussi variés que le problème de l’attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l’allocation de registres en compilation.
Partie I – Des algorithmes pour colorer un graphe
I.1 – Introduction sur un exemple
I.2 – Tester si une coloration est valide
I.3 – Un algorithme intuitif de coloration
I.4 – Variante de Welsh-Powell
I.5 – Algorithme DSATUR
I.6 – Un minorant du nombre de couleurs nécessaires
Partie II – Interrogation d’une base de données géographiques
Le sujet et le corrigé de cette épreuve sont également disponibles sur le site de l’UPSTI (Union des Professeurs de Sciences et Techniques Industrielles)
