Graphes et structures

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)

Contact(s) administratif(s)

Stephane BESSY (stephane.bessy @ umontpellier.fr)