Théorème de BEST

En mathématiques discrètes, et notamment en théorie des graphes, le théorème de BEST donne une formule pour le nombre de circuits eulériens d'un graphe orienté. Le nom est un acronyme des personnes qui ont coopéré à son élaboration, à savoir de Bruijn, van Aardenne-Ehrenfest, Cedric Smith et Tutte.

Énoncé

Soit $G=(S,A)$ un graphe orienté (S est l'ensemble des sommets, A celui des arcs). Un circuit eulérien est un chemin fermé qui passe exactement une fois par chaque arc. C'est en 1736 que Euler énonce que $G$ possède un circuit eulérien si et seulement si $G$ est connexe et que tout sommet a le même le degré sortant que le degré entrant, la démonstration complète étant publiée par Hierholzer en 1873. Dans ce cas, $G$ est dit eulérien. Le degré (entrant ou sortant) d'un sommet $s$ est noté $\deg(s)$ .

Théorème — Le nombre $\operatorname {ec} (G)$ de circuits eulériens d'un graphe $G$ est donné par la formule :

\operatorname {ec} (G)=t_{s_{0}}(G)\prod _{s\in S}{\bigl (}\deg(s)-1{\bigr )}!

où $s_{0}$ est un sommet fixé quelconque de $G$ , et où $t_{s_{0}}(G)$ est le nombre d'arborescences couvrant $G$ , de racine $s_{0}$ , orientées vers $s_{0}.$

Le nombre $t_{s_{0}}(G)$ peut être calculé comme valeur d'un déterminant en vertu du théorème de Kirchhoff pour les graphes orientés. Le fait que les nombres $t_{s_{0}}(G)$ sont égaux pour tous les sommets $s_{0}$ de $G$ est une propriété des graphes eulériens.

Applications

Le théorème de BEST montre que le nombre de circuits eulériens de graphes orientés peut être calculé en temps polynomial, ce qui le met dans la classe P, alors que c'est un problème #P-complet pour les graphes non orientés^[1].

Le théorème est utilisé également dans l'énumération asymptotique de circuits eulériens de graphes complets et de graphes bipartis complets^[2]^,^[3].

Histoire

Le théorème de BEST a été énoncé pour la première fois en 1951, dans une « note ajoutée aux épreuves » de l'article (van Aardenne-Ehrenfest et de Bruijn 1951). La preuve originale est bijective, et a été étendue aux suites de de Bruijn. C'est une variation d'un résultat antérieur de Tutte et Smith 1941.

Notes

↑ (en) Graham Brightwell et Peter Winkler, « Counting Eulerian Circuits is #P-Complete », dans C. Demetrescu, R. Sedgewick et R. Tamassia (éditeurs), ALENEX/ANALCO : Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, Vancouver, BC, Canada, SIAM, 2005 (ISBN 0-89871-596-2, lire en ligne), p. 259-262.
↑ (en) Brendan McKay et Robert W. Robinson, « Asymptotic enumeration of eulerian circuits in the complete graph », Combinatorica, vol. 10, n^o 4,‎ 1995, p. 367–377 (lire en ligne).
↑ (en) Mikhail Isaev, « Asymptotic Behaviour of the Number of Eulerian Circuits », Electronic Journal of Combinatorics, vol. 18, n^o 1,‎ 2011 (lire en ligne).

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « BEST theorem » (voir la liste des auteurs).

Références

(la) Leonard Euler, « Solutio problematis ad geometriam situs pertinentis », Comment. Academiae Sci. I. Petropolitanae, vol. 8,‎ 1736, p. 128-140 (lire en ligne).
(en) William Tutte et Cedric A. B. Smith, « On Unicursal Paths in a Network of Degree 4 », American Mathematical Monthly, vol. 48,‎ 1941, p. 233-237.
(en) Tatiana Pavlovna van Aardenne-Ehrenfest et Nicolaas Govert de Bruijn, « Circuits and trees in oriented linear graphs », Simon Stevin, vol. 28,‎ 1951, p. 203-217 (lire en ligne).
(en) William Tutte, Graph Theory, Addison-Wesley, 1984.
(en) Richard P. Stanley, Enumerative Combinatorics, vol. 2 [détail des éditions] (présentation en ligne).
(en) Martin Aigner, A Course in Enumeration, Springer-Verlag, 2007 (ISBN 978-3-540-39032-9 et 3-540-39032-4).

Portail des mathématiques

Mathématiques discrètes (27)

Théorème de la théorie des graphes (40)

Graphe orienté (14)

Combinatoire (173)

Dernière mise à jour du contenu le 28/02/2021.

Droit d'auteur : le texte de l'article est disponible sous la licence CC BY-SA 3.0.
Les détails concernant les licences et crédits des images sont disponibles en cliquant sur l'image.

Le site Wikimonde est un agrégateur d'articles encyclopédiques, il n'est pas à l'origine du contenu des articles, ni des images.

Le contenu de cet article est une copie de l'article d'origine (//fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_BEST) publié sur Wikipédia (wiki collaboratif publié sous licence libre).
Le contenu des articles n'est pas garanti.
Le texte des articles n'est pas modifié par Wikimonde. Des modifications mineures de mise en page et des liens internes (pour faciliter la navigation) peuvent être effectués automatiquement.

Des crédits concernant les images peuvent être ajoutés automatiquement selon les informations fournis par le site d'origine.
Les images sont chargées depuis des sites externes, certaines peuvent ne pas s'afficher.

Auteurs de cet article « Théorème de BEST » :

WikiCleanerBot, OrlodrimBot, Anne Bauval, Michel Awkal, Gonzolito, Habertix, Vers75, Addbot, Epsilon0, AméliorationsModestes, Roll-Morton, Bouchecl, Robert FERREOL, Esnico30, ManiacParisien, Zebulon84bot, Nemoi, MathsPoetry, CodexBot, 2 utilisateurs non enregistrés.

[BW-1] (en) Graham Brightwell et Peter Winkler, « Counting Eulerian Circuits is #P-Complete », dans C. Demetrescu, R. Sedgewick et R. Tamassia (éditeurs), ALENEX/ANALCO : Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, Vancouver, BC, Canada, SIAM, 2005 (ISBN 0-89871-596-2, lire en ligne), p. 259-262.

[KR-2] (en) Brendan McKay et Robert W. Robinson, « Asymptotic enumeration of eulerian circuits in the complete graph », Combinatorica, vol. 10, n^o 4,‎ 1995, p. 367–377 (lire en ligne).

[Isaev-3] (en) Mikhail Isaev, « Asymptotic Behaviour of the Number of Eulerian Circuits », Electronic Journal of Combinatorics, vol. 18, n^o 1,‎ 2011 (lire en ligne).

[1]

[2]

[3]