AccueilđŸ‡«đŸ‡·Chercher

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].

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[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

Notes et références

Notes

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) AccĂšs libre
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.