# Définition
Soit $G = (V,E)$ un graphe simple non-orienté.
- Un **couplage** (**matching**) $M$ est un ensemble d'arêtes deux-à-deux non adjacentes.
	- $M_1 = \emptyset$ est un couplage
- Un couplage est **maximal** s'il n'existe pas de couplage $M'$ tel que $M \subseteq M'$
- Un couplage est **maximum** s'il n'existe pas de couplage $M'$ tel que $|M| < |M'|$
- Un couplage est **parfait** si chaque sommet du graphe touche une arête du couplage.
- Un couplage **parfait** a $\frac{|V|}{2}$ arêtes exactement
- Un couplage **parfait** est **maximum**
- Un couplage **maximum** est **maximal**

# Trouver des couplages
Soit $M \subseteq E$ un couplage pour $G = (V,E)$.
Un **sommet libre** de $G$ est un sommet non touché par $M$.
Un **chemin améliorant** est un chemin de $G$ qui :
- relie deux sommets libres
- alterne des arêtes de $E \setminus M$ et des arêtes de  $M$.

## Théorème
$M$ est **maximum** pour $G \Leftrightarrow$ il n'existe pas de **chemin améliorant**.

## Algo
- On part d'un sommet libre
- on construit un arbre (avec DFS ou BFS) avec la contrainte d'alterner arêtes de $E \setminus M$ et arête de $M$
- marquer les sommets comme pairs ou impairs pour aider à respecter l'alternance $E \setminus M$ / $M$
- on s'arrête quand on tombe sur un sommet libre.

## Cycles de taille impaire - Algorithme de Jack Edmonds
Consiste à compresser les cycles en un seul noeud.