Informatique - Colorer un graphe
Publication :le 09 septembre 2024
Auteur :
Filière(s) :
Sujet :
Corrigé UPSTI :
Ce corrigé sera rendu public le 1er octobre 2026.
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.
É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.