Graphes (UGA)

Coloration

• 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 

  2. Graphes d'intervalles
  

  • 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 

  3. Graphes planaires
  

  • 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 : $k$-coloration, nombre chromatique, graphe d'intersection, graphe d'intervalles, graphe planaire

  Notations :  $\chi(G)$, $\Delta(G)$, $\omega(G)$

• ---

• Leçon sur la coloration de graphes Lesson
• Modélisation de problèmes pratiques avec la coloration Lesson
• Graphes planaires et coloration Lesson
• Transparents coloration File
• Feuille d'exercices sur les graphes bipartis et la coloration File
• One idea, one story: le théorème des 4 couleurs Page
• Comprendre la formule d'Euler (graphes planaires) par 3Blue1Brown URL
• ---

• Test Cliques, Stables et Coloration Quiz
• Test graphes d'intervalles et graphes planaires Quiz