1 files changed, 29 insertions, 0 deletions
diff --git a/THEG/Couplages.md b/THEG/Couplages.md
new file mode 100755
index 0000000..9f2f215
--- /dev/null
+++ b/THEG/Couplages.md
@@ -0,0 +1,29 @@
+# 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.
+\ No newline at end of file