Liens entre théorèmes min-max.

Les théorèmes min-max interviennent fréquemment en mathématiques discrètes, en particulier en théorie des graphes. Ils consistent à établir une égalité du type : max valeur(machin) = min valeur(truc). Très souvent l'inégalité max valeur(machin) ≤ min valeur(truc) est facile à montrer et la difficulté réside dans la preuve de l'égalité. Un exemple de théorème min-max classique est le théorème de Ford-Fulkerson sur les flots entre deux sommets, qui dit que le flot maximum qui peut passer est égal à la capacité minimum d'une coupe séparant ces deux sommets.

Du point de vue algorithmique, ces théorèmes sont souvent très importants. Si on s'intéresse à la fameuse valeur d'égalité max valeur(machin) = min valeur(truc), il est courant que calculer valeur(machin) soit polynomial, de même que calculer valeur(truc), et ainsi tester si max valeur(machin) ≤ k est dans co-NP et tester si min valeur(truc) ≤ k est dans NP. Cela indique que le problème de décision appartient à la classe NP ∩ co-NP. Pour l'instant c'est un problème ouvert de savoir si NP ∩ co-NP=P, mais l'histoire montre que beaucoup de problèmes dans NP ∩ co-NP ont finalement trouvé un algorithme polynomial.

Il est courant que plusieurs théorèmes min-max soient très liés entre eux au sens que l'un peut se déduire à partir d'un autre, sans avoir à refaire une preuve en partant de zéro. L'objectif de ce sujet est d'illustrer cette observation pour des théorèmes min-max qui ont trait aux graphes. La liste suivante énumère plusieurs théorèmes min-max classiques (la liste n'est pas exhaustive, vous pouvez ajouter d'autres théorèmes min-max susceptibles de se greffer à ceux-là) :

• Théorème de König-Egervary : si G non orienté est biparti, alors le cardinal maximum d'un couplage est égal au cardinal minimum d'un ensemble de sommets couvrant les arêtes.
• Théorème de König sur les indépendants: si G non orienté est biparti sans sommet isolé, alors le cardinal maximum d'un indépendant est égal au cardinal minimum d'une couverture des sommets par des arêtes (càd. plus petit graphe partiel couvrant tous les sommets).
• Théorème de Menger (version sommets-disjoints entre deux sommets) : si x et y sont deux sommets non adjacents de G non orienté, alors le nombre maximum de chaînes entre x et y deux à deux sommets-disjointes (hors les extremités) est égal au cardinal minimum d'un x,y-séparateur.
• Théorème de Menger (version sommets-disjoints entre deux parties) : si X et Y sont ensembles de sommets de G non orienté, alors le nombre maximum de chaînes entre X et Y deux à deux sommets-disjointes est égal au cardinal minimum d'un X,Y-séparateur.
• Théorèmes de Menger (en version arêtes-disjointes, et entre deux sommets ou entre deux parties): idem même deux énoncés en remplaçant sommets-disjoints par arêtes-disjointes.
  
• Théorème de Ford-Fulkerson : dans un graphe orienté avec capacités sur les arcs, le flot maximum qui peut passer entre deux sommets est égal à la capacité minimum d'une coupe séparant ces deux sommets.
• Théorème de König sur la coloration d'arêtes : si G est biparti, alors le nombre minimum de couleurs pour colorer les arêtes est égal au degré maximum du graphe.
• Théorème de Dilworth : dans un ordre partiel, le cardinal maximum d'une "antichaîne" est égal au nombre minimum de "chaînes" couvrant tous les éléments de l'ordre (ici "antichaîne" = partie où éléments tous incomparables, et "chaîne" = partie où tous les éléments sont comparables).

Après avoir redonné un peu plus en détail les énoncés, le but est de dresser des liens entre ces théorèmes (ceci dit, vous pouvez en plus redonner des démonstrations autonomes de certains de ces résultats, si vous le souhaitez), par exemple il y a des liens dans les deux sens entre König-Egervary et Dilworth à base de petites transformations de graphes, comme suggéré dans l'exercice 8.4.27 du livre de D. West.

Quelques références (pas exhaustif).

• Introduction to Graph Theory, livre de D. West, Prentice Hall (2001).
• Digraphs: theory, algorithms and applications, livre de J. Bang-Jensen et G. Gutin, Springer (2002).

Retour à la page des sujets.