blob: 9f2f215b42dfd137107cec43d6ff8e26699cabb5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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.
|
