En teoria de grafs, una part de les matemàtiques discretes, el teorema BEST dóna una fórmula del producte per al nombre de circuits eulerians en grafs dirigits (orientats). El nom és un acrònim dels noms de les persones que el van descobrir: NG de Bruijn, Tatyana van Aardenne-Ehrenfest, Cedric Smith i WT Tutte. miniatura|Exemple de graf dirigit simple
Declaració precisa Sigui G=(V , E) un graf dirigit. Un circuit eulerià és un camí tancat dirigit que visita cada aresta exactament una vegada. El 1736, Euler va demostrar que G té un circuit eulerià si i només si G està connectat i el grau interior és igual al grau exterior en cada vèrtex. En aquest cas, G s'anomena eulerià. Denotem el grau interior d'un vèrtex v per deg(v).
El teorema de BEST estableix que el nombre ec(G) de circuits eulerians en un graf eulerià connectat G ve donat per la fórmula
Aquí tw(G) és el nombre d'arborescències, que són arbres dirigits cap a l'arrel en un vèrtex fix w a G. El nombre tw(G) es pot calcular com a determinant, mitjançant la versió del teorema de l'arbre matricial per a gràfics dirigits. És una propietat dels gràfics eulerians que tv(G)=tw(G) per a cada dos vèrtexs v i w en un graf eulerià connectat G.
Aplicacions El teorema BEST demostra que el nombre de circuits eulerians en grafs dirigits es pot calcular en temps polinòmic, un problema que és #P-complet per a grafs no dirigits.Brightwell and Winkler, "Note on Counting Eulerian Circuits", CDAM Research Report LSE-CDAM-2004-12, 2004. També s'utilitza en l'enumeració asimptòtica de circuits eulerians de grafs complets i bipartits complets.Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs (en rus), Proc. 52-nd MFTI Conference (2009), Moscow.
Història El teorema BEST es deu a van Aardenne-Ehrenfest i de Bruijn (1951), §6, Teorema 6. La seva demostració és bijectiva i generalitza les successions de Bruijn. En una "nota afegida a la demostració", fan referència a un resultat anterior de Smith i Tutte (1941) que demostra la fórmula per a gràfics amb deg(v) = 2 a cada vèrtex.
Referències
Categoria:Teoria de grafs