A. Sigayret : Algorithmique

Algorithmes de référence : Couplage maximal de graphe


Définitions et notations :
Deux arêtes d'un graphe non-orienté sont dites incidentes quand elles ont un sommet commun.
Un couplage d'un graphe non-orienté est un ensemble d'arêtes qui sont deux à deux non-incidentes.
Une chaine x1,...,xk est dite améliorante pour un couplage C quand x1x2∉C, x2x3∈C, ..., et xk−1xk∉C (alternance des arêtes hors et dans C).
Un couplage est dit parfait quant tous les sommets du graphe sont incidents d'une arête de ce couplage.
Un couplage C est dit maximal [pour l'inclusion] quand il n'est inclus dans aucun autre couplage su graphe.
Un graphe non orienté G=(V,E) est dit biparti quand V peut être partitionné en deux sous-ensembles non vides V1 et V2 tels que toute arête de E a un sommet dans V1 et l'autre dans V2. (En d'autres termes, V1 et V2 sont des stables : ils n'ont aucune arête interne).

Théorèmes :
– Un couplage parfait est maximal. (réciproque fausse.)
– Si H est une chaine améliorante pour un couplage C alors C⊕H=(C∪K)−(C∪K) est un couplage de taille supérieure à celle de C. Par conséquent, un couplage est maximal si et seulement si il ne possède pas de chaine améliorante.
– Si C1 et C2 sont deux couplages d'un graphe tels que |C1|<|C2| alors C1⊕C2 contient au moins |C2|−|C1| chaines améliorantes disjointes (pour passer de C1 à C2).

schéma algorithmique AMELIORER
donnée : un graphe non orienté G=(V,E).
Résultat : un couplage maximal C de G.
C← ∅
Tantque il existe une chaine améliorante de C faire
Déterminer un ensemble maximal de chaines améliorantes disjointes;
Ajouter ces chaines améliorantes à C.
 
schéma algorithmique AMELIORERVITE
donnée : un graphe non orienté G=(V,E).
Résultat : un couplage maximal C de G.
Tantque il existe une chaine améliorante de C faire
Choisir la (les) plus courte(s) chaine(s) améliorante(s);
Ajouter cette chaine améliorantes à C.
N.B. la recherche de chaines améliorantes est plus facile dans un graphe biparti.

Complexité : actuellement proche de O(n2,5).

Question : peut-on descendre à O(n2 lg(n)) ?