Home
About

Couplages dans un graphe quelconque

Cours/Théorie des graphes/Couplages/Couplages dans un graphe quelconque

Le problème du couplage dans un graphe quelconque se résout aussi de façon polynomiale, mais les algorithmes sont plus complexes.

Algorithme d'Edmonds cas général

Chemin augmentant dans un graphe quelconque

On a vu que l'algorithme de recherche d'un chemin augmentant fonctionnait sauf s'il constituait une fleur :

contraction fleur 1

Si cela arrive, on peut contracter la corolle en un seul sommet, les arêtes parant de la corolle étant fusionné sur le nouveau sommet :

contraction fleur 2

Aucune autre arête contracté ou partant de la corolle (les arêtes vertes) ne peut être dans le couplage. On a alors la propriété fondamentale suivante de l'algorithme :

Proposition

S'il existe un chemin augmentant dans le graphe contracté, il existe un chemin augmentant dans le graphe initial.

preuve

Plusieurs cas sont à envisager :

  • si le chemin augmentant ne passe pas par la corolle, c'est évident
  • si le nouveau sommet est une extrémité, la tige n'existe pas et soit :
    • l'arête partant du nouveau point est une arête du graphe initial et du coup tout le chemin est aussi dans le graphe initial
    • l'arête partant du nouveau point n'est pas une arête du graphe initial on peut y aller dans le graphe initial sans casser le chemin augmentant dé-corolle
  • le chemin passe par le nouveau sommet. La tige, ou au moins son dernier élément, est alors une des extrémités et au peut retrouver l'autre en passant par la corolle. dé-corolle 2

Dans l'exemple, si on a pas de chance pn peut encore contracter On peut alors contracter la corolle en un seul sommet et en conservant les arêtes qui en partent : contraction fleur exemple

Que l'on peut encore contracter une fois :

contraction fleur exemple 2

Que l'on peut contracter une dernière fois pour obtenir un graphe biparti contenant un chemin augmentant :

contraction fleur exemple 3

Ce chemin peut se détracter en un chemin augmentant du graphe initial.

On peut transformer petit à petit notre graphe. Si on a pas de chance, on obtiendra après toutes les contractions possible un graphe sans corolle, donc biparti et on sait ue pour ces graphes notre algorithme trouve toujours un chemin augmentant s'il existe.

Enfin, toute cette construction se fait de plus de façon polynomiale !

Proposition

La complexité de recherche d'un chemin augmentant dans un graphe $G$ est en $mathcal{O}(e(G)\cdot v(G) + v(G)^2)$ opérations.

preuve

Si l'on trouve une fleur, il faut la contracter, ce qui prend $\mathcal{O}(n)$ opération puis relancer l'algorithme, ce que l'on peut être obligé de faire $\mathcal{O}(n)$ fois.

Comme pour les graphes connexes, $e(G) \geq v(G)-1$ on a :

Proposition

La complexité de recherche d'un chemin augmentant dans un graphe connexe est en $\mathcal{O}(e(G)\cdot v(G))$ opérations.

Algorithme

Identique que pour le graphe biparti, on cherche au pire $\mathcal{O}(v(G))$ fois à augmenter notre couplage. On en déduit que :

Proposition

La complexité de recherche d'un couplage maximum dans un graphe connexe est en $\mathcal{O}(e(G)\cdot v(G)^2)$ opérations.

Propriétés des Couplage parfait et maximum dans un graphe quelconque

TBD :

Tutte, c'est un calcul de déterminant et c'est idem que multiplication de matrice : https://www.cs.mcgill.ca/~amehra13/Presentations/max_matching.pdf