Graphes et structuresCode de l'UE : HMIN223M
Présentation
Nous présenterons à travers ce cours des résultats classiques de la théorie des graphes. Notre objectif sera d'appréhender des preuves parfois complexes manipulant des objets non triviaux. Nous reviendrons sur les raisonnements par l'absurde, par récurrence, par réduction, ... Entre autres, nous nous intéresserons aux :
- problème du couplage dans les graphes bipartis (théorème de Hall), dans les graphes en général (théorème de Tutte), flots...
- problèmes de colorations de graphes avec notamment le problème des quatre couleurs et plus précisément le théorème des cinq couleurs (argument de Kempe (preuve par l'absurde), Lovasz (preuve par réduction), Thomassen (preuve par induction))...
- problèmes sur les graphes orientés avec les théorèmes de Gallai-Roy, Gallai-Milgram, d'Edmonds.
Également seront abordées les problématiques de connectivité, de décompositions, d'hypergraphes,...
Volume horaire
- CM : 16.5
- TD : 33
- TP : 0
Diplômes intégrant cette UE
En bref
Crédits ECTS 5
Période de l'année
secondSemestre
Contact(s)
Composante
Faculté des Sciences