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, Modèle:Lien 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é $\mathrm{deg}(s)$.

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.

Le théorème est utilisé également dans l'énumération asymptotique de circuits eulériens de graphes complets et de graphes bipartis completsModèle:,.

Histoire

Le théorème de BEST a été énoncé pour la première fois en 1951, dans une Modèle:Citation de l'article Modèle:Harv. 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 Modèle:Harvsp.

Références

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Enumerative Combinatorics.
• Modèle:Ouvrage.