Graphes, Couplages et Colorations
Public Concerné
Bases en optimisation et théorie des graphes
Présence et réussite aux examens
Pour l'année universitaire 2021-2022 :
- Nombre d'inscrits : 17
- Taux de présence à l'évaluation : 100%
- Taux de réussite à l'évaluation : 88%
Objectifs pédagogiques
L'existence de couplages parfaits et les problèmes de coloration ont des intérêts théoriques et applicatifs. L'objectif est de fournir les principaux résultats de nature structurelle ou algorithmique concernant ces problèmes.
Capacité et compétences acquises
Connaître les résulats fondateurs des problématiques de couplage maximum et de coloration.
Contenu de la formation
- Rappel sur les couplages maximum et définition d'un couplage parfait. Cas des graphes bipartis. Cas général : théorème de Tutte.
- Cas des graphes cubiques et théorème de Petersen. Aspects polyédraux et algorithmiques. Généralisation aux 2-facteurs.
- Coloration des sommets d'un graphe. Exemples et applications. Borne supérieure pour le nombre chromatique et thérorème de Brooks.
- Théorème de Gallay-Roy. Coloration listée. Utilisation de noyaux pour l'obtention de bornes pour le nombre chromatique listé.
- Coloration des arêtes. Exemples d'applications. Théorème de König pour les graphes bipartis, théorème de Vizing. Autres exemples de problèmes de coloration.
Description des modalités de validation
- Examen final
Prévisions d'ouverture
| Groupe | Semestre | Modalité | État d'ouverture | Date du premier cours | Lieux | ||
|---|---|---|---|---|---|---|---|
| US331B | Graphes, Couplages et Colorations | 2 | Cours de Jour | - | - | - | - |
Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation
