Un couplage est un ensemble d’arête deux à deux indépendantes : elle ne partagent pas de sommets.
Couplage parfait : Chaque sommet du graphe est dans exactement une arrête du couplage
Un graphe parfait a un nombre pair de sommets (la réciproque n’est pas vraie)
Un couplage parfait est un couplage de taille maximale (impossible à agrandir, on ne peut pas coupler plus), la réciproque n’est pas vraie.
Exemple d’utilisation : Dans une entreprises logistique les salariés ont un ou plusieurs permis leur permettant de rouler un certain type de véhicule. On peut représenter le problème dans un graphe avec comme sommet les salariés et les véhicules de l’entreprise. Pour résoudre le problème il faut alors trouver un couplage de taille max.
Algorithme glouton pour trouver un couplage maximal :
Etape 1 : On sélectionne une arrête aléatoirement et on la mémorise dans une copie du graphe (à gauche)
Etape 2 : On supprime les arrêtes qui sont incidentes aux deux sommets et on sélectionne une autres arrête aléatoirement
Etape 3 : On supprime les arrêtes qui sont incidentes aux deux sommets, on obtient alors un couplage maximal
