Algorithme d'Edmonds pour les couplages

Étant donné G = (V, E) et un couplage M de G, un sommet v est couplé, apparié, ou couvert par M s'il existe une arête de M incidente à v.

Un chemin en G est un chemin alternant, s'il passe alternativement par des arêtes de M et des arêtes de E \ M.

Un chemin augmentant P est un chemin alternant qui commence et se termine par deux sommets non couverts par M distincts. Notez que le nombre d'arêtes de E \ M dans un chemin augmentant est supérieur de un au nombre d'arêtes de M, et par conséquent, le nombre total d'arêtes dans un chemin augmentant est impair.

Une augmentation de couplage le long d'un chemin augmentant P est l'opération consistant à remplacer M par un nouveau couplage ?${\displaystyle M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)}$ .

D'après le lemme de Berge, le couplage M est maximal si et seulement s'il n'y a pas de chemin augmentant de M dans G.[5] - [6] Par conséquent, soit un couplage est maximal, soit il peut être augmenté. Ainsi, à partir d'un couplage initial, nous pouvons calculer un couplage maximal en augmentant le couplage actuel avec des chemins augmentant tant que nous pouvons en trouver, et renvoyer le résultat obtenu s'il ne reste plus de chemins augmentant. Nous pouvons formaliser l'algorithme comme suit :

   ENTRÉE: Graphe G, couplage initial M sur G
   SORTIE: couplage maximal M* sur G
A1 fonction find_maximum_matching (G, M) : M*
A2    P ← find_augmenting_path (G, M)
A3    si P est non vide alors
A4        renvoyer find_maximum_matching (G, augmentation de M le long de P)
A5    sinon
A6        renvoyer M
A7    fin si

Nous devons encore décrire comment trouver efficacement des chemins augmentant. Le sous-programme qui réalise cette tâche utilise des fleurs et des contractions.

Étant donné un graphe G = (V, E) et un couplage M de G, une fleur B est un cycle dans G constitué de 2k + 1 arêtes dont exactement k appartiennent à M. En outre, une fleur comporte un sommet v (sa base) tel qu'il existe un chemin alternant de longueur paire (la tige ) de v à un sommet w non couvert par M.

Trouver des fleurs:

• Parcourez le graphe à partir d'un sommet non couvert par M.
• Étiquetez ce sommet comme un sommet externe "e".
• En commençant par ce sommet, alternez l'étiquetage entre les sommets intérieurs "i" et extérieurs "e" de sorte qu'aucun sommet adjacent ne possède le même libellé.
• Si nous nous retrouvons avec deux sommets adjacents étiquetés comme "e" externes, alors nous avons un cycle de longueur impaire et donc une fleur.

Définissons le graphe contracté' G' comme le graphe obtenu à partir de G en contractant chaque arête de B, et définissons le couplage contracté M' comme le couplage de G correspondant à M, c'est-à-dire le couplage obtenu en retirant à M toutes les arêtes de B.

Montrons que G' a un chemin augmentant de M' si et seulement si G a un chemin augmentant de M, et que tout chemin augmentant P' de M dans G peut être étendu en un chemin augmentant de M dans G.

Le chemin étendu est obtenu en annulant la contraction par B du graphe G, et en intercalant dans P' les arêtes qui doivent l'être[7].

• Si P' traverse un chemin u → v_B → w dans G', alors ce chemin est remplacé par le chemin u → (u'→ ... → w') → w dans G, où les sommets u' et w' de la fleur ainsi que le chemin (u'→ ... → w') dans B sont choisis pour s'assurer que le nouveau chemin est toujours alternant (u' n'est pas couvert par ${\displaystyle M\cap B}$, ${\displaystyle \{w',w\}\in E\setminus M}$ ).

• si P ' a une extrémité v_B, alors le chemin u → v_B dans G' est remplacé par le segment u → (u '→ ... → v') dans G, où les sommets u' et v' de la fleur ainsi que le chemin (u'→ ... → v') dans B sont choisis pour s'assurer que le nouveau chemin est toujours alternant (v' n'est pas couvert par M,${\displaystyle \{u',u\}\in E\setminus M}$ ${\displaystyle \{u',u\}\in E\setminus M}$${\displaystyle \{u',u\}\in E\setminus M}$${\displaystyle \{u',u\}\in E\setminus M}$).

Ainsi, la recherche peut être effectuée à partir du graphe obtenu en contractant les fleurs. Cette réduction est au cœur de l'algorithme d'Edmonds.

La recherche d'un chemin augmentant utilise une structure de données auxiliaire constituée d'une forêt F dont les arbres correspondent à des portions spécifiques du graphe G. Cette forêt F est la même que celle utilisée pour trouver un couplage maximal dans un graphe biparti (sans avoir besoin de réduire les fleurs). A chaque itération, l'algorithme soit (1) trouve un chemin augmentant, (2) trouve une fleur et s'appelle récursivement sur le graphe contracté correspondant, ou (3) conclut qu'il n'y a pas de chemin augmentant. La structure auxiliaire est construite par la procédure incrémentale décrite ci-dessous[7].

La procédure de construction considère les sommets v et les arêtes e de G et met à jour F de manière incrémentale si nécessaire. Si v est dans un arbre T de la forêt, nous noterons root(v) la racine de T. Si u et v sont tous les deux dans le même arbre T dans F, nous noterons distance(u, v) la longueur du chemin unique de u à v dans T.

  ENTRÉE: un graphe G, un couplage M sur G
  SORTIE: un chemin augmentant P dans G ou le chemin vide si aucun chemin augmentant n'est trouvé
B01 fonction find_augmenting_path(G, M) :
B02    F ← forêt vide
B03    retirer toutes les marques sur des sommets et arêtes de G, marquer toutes les arêtes de M
B05    pour tout sommet v non couvert par M faire
B06       créer un arbre singleton {v} et l'ajouter à F
B07    fin pour
B08    tant que qu'il y a un sommet v non marqué dans F avec distance(v, racine(v)) paire faire
B09       tant qu'il existe une arête non marquée e = {v, w} faire
B10          si w n'est pas dans F alors
                // w apparaît dans M, donc on ajoute e et l'arête de M incidente à w à F
B11             x ← sommet correspondant à w dans M
B12             ajouter les arêtes {v, w} et {w, x} à l'arbre de v
B13          sinon
B14             si la distance(w, racine (w)) est impaire alors
                   // Ne fais rien.
B15             sinon
B16                si racine(v) ≠ racine(w) alors
                      // On stocke un chemin augmentant en F${\displaystyle \cup }${e}.
B17                   P ← chemin(racine(v) → ... → v ) → (w → ... → racine(w))
B18                   renvoyer P
B19                sinon
                      // On contracte une fleur de G et on recherche un chemin dans le graphe contracté.
B20                   B ← fleur formée par e et les arêtes sur le chemin v → w dans T
B21                   G', M' ← contraction de G et M par B
B22                   P' ← find_augmenting_path (G', M')
B23                   P ← étendre P' à G
B24                   renvoyer P
B25                 fin si
B26             fin si
B27          fin si
B28          marquer l'arête e
B29       fin tant que
B30       marquer le sommet v
B31    fin tant que
B32    renvoyer  le chemin vide
B33 Fin fonction