Coloration
Résumé de section
-
- Coloration
- Bornes et algorithmes
- Coloration de graphes d’intervalles
- Coloration de graphes planaires
-
Compétences
1. Bornes et algorithmes- Connaitre les preuve sur les bornes de coloration avec la clique max et le degré max
- Décrire l'algorithme glouton de coloration
- Utiliser l'algorithme glouton pour prouver la borne sur le degré max
- Modéliser des problèmes pratiques commme des problèmes de coloration de graphe
- Construire le graphe d'intersection associé à une famille d'ensembles
- Utiliser l'algorithme glouton pour résoudre optimalement la coloration de graphes d'intervalles
- Montrer l'optimalité de l'algorithme
- Expliquer la formule d'Euler
- Démontrer qu'un graphe planaire est 6-coloriable
- Utiliser l'algorithme glouton pour 6-colorier un graphe planaire
Vocabulaire :
-coloration, nombre chromatique, graphe d'intersection, graphe d'intervalles, graphe planaireNotations :
, 
, 
-
Les étudiants doiventMarquer comme terminé
