Topic outline

  • General

  • Couplages

    1. Couplage
    2. Couplage dans les graphes bipartis

    • 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)
    • File icon
      Transparents sur les couplages File
    • Quiz icon
      Test sur les couplages Quiz