Coloration de Graphe
Algorithme glouton de coloration
Enonce
Implémenter la coloration gloutonne. Retourner un dictionnaire {sommet: couleur}. Tester sur le graphe de Petersen simplifié.
Signature attendue
def coloration_gloutonne(G: dict) -> dict:Exemple
coloration_gloutonne({0: [1, 2], 1: [0, 2], 2: [0, 1]})→{0: 0, 1: 1, 2: 2}
📖 Rappel de cours
La coloration de graphe assigne une couleur à chaque sommet tel que deux sommets adjacents n'aient pas la même couleur. Le nombre minimum de couleurs est le nombre chromatique $\chi(G)$.
Algorithme glouton :
Pour chaque sommet, assigner la plus petite couleur non utilisée par ses voisins.
Garantie :
Au plus $\Delta + 1$ couleurs, où $\Delta$ est le degré maximal.
L'algorithme glouton ne garantit pas le nombre optimal de couleurs.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Algorithme de Bellman-Ford
- Algorithme de Prim
- Algorithme de Kruskal
- Plus Court Chemin dans un Labyrinthe
- Représentations d'un Graphe
- Test de Bipartisme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.