Graphes (UGA)

Couplages

• Compétences

  • Connaitre le théorème qui lie les couplages max et les chaines altérnées augmentantes. 
  • Reproduire la preuve de ce théorème
  • Connaitre le lien entre  couplages et transversals dans les graphes quelconques et dans les graphes bipartis
  • Comprendre la preuve du théorème de Koning

  Vocabulaire : couplage, couplage parfait, Chaine $M$-alternée, Chaine $M$-augmentante, différence symétrique, transversal

  Notation : $\nu(G)$, $X\Delta Y$, $\tau(G)$

• ---

• Transparents sur les couplages File
• ---

• Test sur les couplages Quiz