EnglishCommencer

Le couplage dans un graphe

Le couplage dans un graphe biparti : couplage maximal et maximum, sommet libre, chaîne alternée et augmentante, algorithme des chaînes augmentantes et condition de Hall.

  • 27 cartes
  • 4 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Les étapes

Quelques cartes du deck

  • Couplage : de quoi s'agit-il ?

    Voir la réponse

    Ensemble d'arêtes d'un graphe dont deux quelconques n'ont aucune extrémité commune.

    Chaque sommet est utilisé au plus une fois : un stagiaire ne peut être placé que dans une entreprise, et une entreprise n'accueille qu'un stagiaire.

  • Stagiaires A, B, C ; entreprises 1, 2, 3 ; vœux A1, A2, B1, C2, C3. Parmi ces ensembles d'arêtes, lequel est un couplage ?

    • {A2, B1}
    • {A1, B1}
    • {A2, C2}
    • {C2, C3}
    Voir la réponse

    {A2, B1}

    Dans {A2, B1} aucun sommet n'est répété. {A1, B1} donne l'entreprise 1 à deux stagiaires ; {A2, C2} fait de même avec l'entreprise 2 ; {C2, C3} place C deux fois.

  • Un sommet qu'aucune arête du couplage n'atteint est dit … ; un couplage qui n'en laisse aucun est dit ….

    Voir la réponse

    Un sommet qu'aucune arête du couplage n'atteint est dit libre ; un couplage qui n'en laisse aucun est dit parfait.

    Un couplage parfait couvre tous les sommets : il est donc maximum, et le graphe a nécessairement un nombre pair de sommets.

  • Graphe biparti : de quoi s'agit-il ?

    Voir la réponse

    Graphe dont les sommets se répartissent en deux groupes, chaque arête reliant un sommet de l'un à un sommet de l'autre.

    Stagiaires d'un côté, entreprises de l'autre : aucune arête ne relie deux stagiaires, ni deux entreprises. Un couplage y associe donc toujours un stagiaire à une entreprise.

  • L'algorithme des chaînes augmentantes : quelle étape vient après « Partir d'un couplage, même vide » ?

    • Choisir un sommet libre
    • Chercher une chaîne alternée vers un autre sommet libre
    • Inverser les arêtes de cette chaîne
    • Recommencer jusqu'à ce qu'aucune chaîne n'existe
    Voir la réponse

    Choisir un sommet libre

    L'inversion n'a de sens qu'une fois la chaîne trouvée, et on s'arrête quand la recherche échoue : le couplage est alors maximum.

Réviser ce deck