Lemme de Berge

En théorie des graphes, le lemme de Berge est le suivant :

Lemme de Berge — Un couplage M dans un graphe G est maximum (c'est-à-dire contient le plus grand nombre d'arêtes possible) si et seulement s'il n'y a pas de chemin d'augmentation (un chemin qui commence et se termine sur des sommets libres (non couplés)), et qui alterne entre les arêtes dans et en dehors du couplage M.

Ce lemme a été prouvé par le mathématicien français Claude Berge en 1957, bien qu'il ait déjà été observé par Julius Petersen en 1891 et par Dénes Kőnig en 1931.

Preuve

Pour démontrer le lemme de Berge, on établit d'abord un autre lemme :

Soit G un graphe et soient M et M′ deux couplages dans G. Soit G' le graphe résultant de la différence symétrique de M et M′ ; c'est-à-dire $(M\setminus M')\cup (M'\setminus M)$. Alors G′ est constitué de composantes connexes de l'un des types suivants :

1. un sommet isolé ;
2. un cycle de longueur paire dont les arêtes alternent entre M et M′ ;
3. une chaîne dont les arêtes alternent entre M et M′, avec des extrémités distinctes.

Preuve. Chaque sommet de G′ peut être incident à au plus 2 arêtes : une dans M et une dans M′. Or les graphes où chaque sommet est de degré au plus 2 sont constitués de sommets isolés, de cycles] et de chaînes. De plus, toute chaîne et tout cycle dans G′ doit alterner entre des arêtes de M et de M′. Un tel cycle a autant d'arêtes dans M que dans M′, et donc est de longueur paire.

On démontre maintenant la contraposée du lemme de Berge : G possède un couplage plus grand que M si et seulement si G a un chemin d'augmentation. En effet, un chemin d'augmentation P de G peut être utilisé pour construire un couplage M′ plus grand que M : il suffit pour cela de prendre pour M′ la différence symétrique de P et de M ; alors M′ contient exactement les arêtes de G qui apparaissent soit dans P soit dans M . Ceci prouve l'assertion.

Pour le sens direct, on considère un couplage M′ dans G plus grand que M. Soit D la différence symétrique de M et de M′. Alors D se compose de chemins et de cycles de longueur paire par le lemme précédent. Puisque M′ est plus grand que M, l'ensemble D contient une composante qui a plus d'arêtes venant de M′ que de M. Une telle composante est une chaîne dans G qui commence et se termine par une arête de M′, c'est donc un chemin augmentant.

Conséquences

Corollaire 1

Soit M un couplage maximal et considérons une chaîne alternée dont les arêtes alternent entre arêtes dans et en dehors de M. Si la chaîne alternée est un cycle ou une chaîne de longueur paire, alors un nouveau couplage maximale M′ peut être obtenu en interchangeant les arêtes dans M et celles en dehors de M.

Par exemple, si la chaîne alternée est $(m_{1},n_{1},m_{2},n_{2},\ldots )$, où $m_{i}\in M$ et $n_{i}\notin M$, les interchanger a pour conséquence que les $n_{i}$ font partie du nouveau couplage en remplacement des $m_{i}$.

Corollaire 2

Une arête est dite libre si elle appartient à un couplage maximal mais n'appartient pas à tous les couplages maximaux.

Une arête e est libre si et seulement si, dans un couplage maximal quelconque M, l'arête e appartient à une chaîne alternante de longueur paire commençant en un sommet non couplé ou appartient à un cycle alternant.

Par le premier corollaire, si l'arête e fait partie d'une telle chaîne alternante, alors un nouveau couplage maximal M′, existe et e appartient soit à M soit à M′, et donc est libre. Réciproquement, si l'arête e est libre, alors e est dans un couplage maximal M mais pas dans M′ . Puisque e ne fait pas partie à la fois de M et de M′, elle figure dans la différence symétrique de M et M′. La différence symétrique de M et M′ consiste en un graphe constitué de sommets isolés, de cycles alternés de longueur paire, et de chaînes alternées. Supposons que e appartient à une chaîne de longueur impaire. Mais alors l'un des couplages M ou M′ doit avoir une arête de moins que l'autre dans ce composant, ce qui signifie que le composant dans son ensemble est un chemin augmentant par rapport à ce couplage. Par le lemme de Berge, ce couplage (M ou M′ ) ne peut pas être un couplage maximal, ce qui contredit l'hypothèse que M et M′ sont tous deux maximaux. Ainsi, puisque e ne peut appartenir à aucune chaîne de longueur impaire, elle doit être soit dans un cycle alterné, soit dans une chaîne alternée de longueur paire.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Berge's Lemma » (voir la liste des auteurs).
• Claude Berge, « Two theorems in graph theory », Proceedings of the National Academy of Sciences of the United States of America, vol. 43, n^o 9,‎ 15 septembre 1957, p. 842–844 (PMID 16590096, PMCID 534337, DOI 10.1073/pnas.43.9.842, lire en ligne).
• Douglas West, Introduction to Graph Theory, Pearson Education, Inc., 2001 (ISBN 81-7808-830-4), p. 109–110.
• Claude Berge, Graphs and Hypergraphs, North-Holland Publishing Company, 1973 (ISBN 0-444-10399-6), p. 122–125.
• deDieter Jungnickel (en), Graphs, Networks and Algorithms, Springer Verlag, coll. « Algorithms and Computation in Mathematics » (n^o 5), 2008, 3^e éd. (ISBN 978-3-540-72779-8, MR 2363884)
• Julius Petersen, « Die Theorie der regulären Graphs », Acta Mathematica, vol. 15,‎ 1891, p. 193–220 (lire en ligne)