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[1].
ĂnoncĂ©
Formule de Tutte-Berge[2] â La taille d'un couplage maximal d'un graphe est Ă©gal Ă
oĂč est le nombre de composantes connexes d'un graphe 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 de sommets crĂ©e au plus composantes impaires. (Un sous-ensemble ' qui crĂ©e au moins 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 ; 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,â , p. 258â259
- Claude Berge, ThĂ©orie des graphes et ses applications, Paris, Dunod, . â 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 », (ISBN 1-84628-969-6), p. 428.
- John Adrian Bondy et U. S. R. Murty, Graph Theory with Applications, New York, North Holland, (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 » (no 108), (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 » (no 29), , 543 p. (ISBN 9780080872322, présentation en ligne), p. 90-91.
- Alexander Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer-Verlag, (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, no 2,â , 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, no 5,â , p. 674â676 (DOI 10.1016/j.ejc.2011.01.009, lire en ligne)