Concours CPGE 2024 - CCINP - Epreuve d'Informatique - Filière TSI - Colorer un graphe

publié le 06 mai 2024 par Olivier TOURVIEILLE

Groupe principal

Description

Colorer un graphe

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)

https://www.upsti.fr/espace-etudiants/annales-de-concours

Fichiers et liens