From 66c3bbfa94d8a41e58adf154be25e6d86fee8e30 Mon Sep 17 00:00:00 2001 From: "martial.simon" Date: Sun, 13 Apr 2025 19:54:19 +0200 Subject: init: initial commit --- THEG/Couplages.md | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100755 THEG/Couplages.md (limited to 'THEG/Couplages.md') 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 -- cgit v1.2.3