Formule de Tutte-Berge

Dans le domaine mathématique de théorie des graphes, la formule de Tutte-Berge est une caractérisation de la taille maximale d'un couplage dans un graphe . Elle est une généralisation du théorème de Tutte sur les couplages parfaits, et est nommé d'après William Tutte (qui a prouvé le théorème de Tutte) et Claude Berge (qui a prouvé sa généralisation.

Dans ce graphe, la suppression du sommet central produit trois composantes de taille impaire : les trois lobes à cinq sommets du graphe. Par la formule de Tutte-Berge, tout couplage a au plus (1-3 + 16) / 2 = 7 arêtes. De fait, les quatre couplages distingués par leurs couleurs ont chacun 6 arêtes.

Énoncé

Formule de Tutte-Berge — La taille d'un couplage maximal d'un graphe $G=(V,E)$ est égal à

${\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right),$

où $\operatorname {odd} (H)$ est le nombre de composantes connexes d'un graphe $H$ qui ont un nombre impair de sommets.

Explications

Intuitivement, pour tout sous-ensemble U des sommets, la seule façon de couvrir complètement une composante impaire de G − U par un couplage implique que l'une des arêtes figurant dans le couplage est incidente à U. Si en effet une composante impaire n'avait pas d'arête du couplage la reliant à U, alors la partie du couplage qui couvre la composante couvrirait ses sommets par paires, mais comme la composante a un nombre impair de sommets, il y aurait nécessairement au moins un sommet restant et non couplé. Par conséquent, si, pour un choix, l'ensemble U a peu de sommets mais que sa suppression crée un grand nombre de composantes impaires, alors il y aura de nombreux sommets non couplés, ce qui implique que le couplage lui-même est petit. Ce raisonnement peut être précisé en affirmant que la taille d'un couplage maximal est au plus égale à la valeur donnée par la formule de Tutte-Berge.

La caractérisation de Tutte et Berge prouve que c'est le seul obstacle à la création d'un grand couplage : la taille du couplage optimal est déterminée par le sous-ensemble U qui donne la plus grande différence entre le nombre de composantes impaires en dehors de U et le nombre de sommets de U. Autrement dit, il existe toujours un sous-ensemble U tel que la suppression de U crée le nombre correct de composantes impaires nécessaire pour que la formule soit vraie. Une façon de déterminer un tel ensemble U est de choisir n'importe quel couplage maximal M, et de définir un ensemble X comme l'ensemble des sommets qui sont non couplés dans M, ou qui peuvent être atteints à partir d'un sommet non couplé par un chemin alterné qui se termine par une arête couplée. Soit U l'ensemble des sommets qui sont couplés par M avec des sommets de X. Deux sommets de X ne peuvent pas être adjacents, car s'ils l'étaient, leurs chemins alternés pourraient être concaténés pour donner un chemin par lequel le couplage pourrait être augmenté, contredisant la maximalité de M. Chaque voisin d'un sommet x dans X doit appartenir à U, sinon on pourrait prolonger un chemin alterné vers x par une autre paire d'arêtes vers le voisin, faisant du voisin un élément de U. Par conséquent, dans G − U, chaque sommet de X forme une composante à un seul sommet, de taille impaire. Il ne peut y avoir d'autres composantes impaires, car tous les autres sommets restent couplés après la suppression de U. Donc, avec cette construction, la taille de U et le nombre de composantes impaires créées en supprimant U réalisent la formule.

Relation avec le théorème de Tutte

Le théorème de Tutte caractérise les graphes avec des couplages parfaits comme étant ceux pour lesquels la suppression d'un sous-ensemble $U$ de sommets crée au plus $|U|$ composantes impaires. (Un sous-ensemble '$U$ qui crée au moins $|U|$ composantes impaires peut toujours être réalisé avec l'ensemble vide . ) Dans ce cas, selon la formule de Tutte–Berge, la taille du couplage est $|V|/2$ ; autrement dit, le couplage maximal est un couplage parfait. Ainsi, le théorème de Tutte peut être dérivé de la formule de Tutte-Berge, et la formule peut être vue comme une généralisation du théorème de Tutte.

Notions liées

• Dureté d'un graphe ou la façon de créer de nombreuses composantes connexes en supprimant un petit ensemble de sommets sans tenir compte de la parité des composantes.
• Théorème du mariage de Hall
• Théorème de Tutte

Notes et références

Notes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tutte–Berge formula » (voir la liste des auteurs).

Références

• Claude Berge, « Sur le couplage maximum d'un graphe », Comptes rendus hebdomadaires des séances de l'Académie des sciences, vol. 247,‎ 1958, p. 258–259
• Claude Berge, Théorie des graphes et ses applications, Paris, Dunod, 1958. — Traduit en anglais, russe, espagnol, roumain, chinois.
• John Adrian Bondy et U. S. R. Murty, Graph theory: an advanced course, Springer-Verlag, coll. « Graduate Texts in Mathematics », 2007 (ISBN 1-84628-969-6), p. 428.
• John Adrian Bondy et U. S. R. Murty, Graph Theory with Applications, New York, North Holland, 1976 (ISBN 0-444-19451-7, lire en ligne)
• Richard A. Brualdi, Combinatorial matrix classes, Cambridge, Cambridge University Press, coll. « Encyclopedia of Mathematics and Its Applications » (n^o 108), 2006 (ISBN 0-521-86565-4, zbMATH 1106.05001, lire en ligne), 360
• László Lovász et Michael D. Plummer, Matching Theory, North Holland (Elsevier), coll. « Annals of Discrete Mathematics » (n^o 29), 1986, 543 p. (ISBN 9780080872322, présentation en ligne), p. 90-91.
• Alexander Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer-Verlag, 2003 (ISBN 3-540-44389-4, lire en ligne), 413
• Tutte, « The factorization of linear graphs », Journal of the London Mathematical Society, series 1, vol. 22, n^o 2,‎ 1947, p. 107–111 (DOI 10.1112/jlms/s1-22.2.107)
• Douglas B. West, « A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem », European Journal of Combinatorics, vol. 32, n^o 5,‎ 2011, p. 674–676 (DOI 10.1016/j.ejc.2011.01.009, lire en ligne)