En teoría de grafos , una parte de las matemáticas discretas , el teorema BEST da una fórmula producto para el número de circuitos eulerianos en grafos dirigidos (orientados) . El nombre es un acrónimo de los nombres de las personas que lo descubrieron: NG de Bruijn , Tatyana Ehrenfest , Cedric Smith y WT Tutte .
Sea G = ( V , E ) una gráfica dirigida. Un circuito euleriano es un camino cerrado dirigido que visita cada borde exactamente una vez. En 1736, Euler demostró que G tiene un circuito euleriano si y sólo si G es conexo y el grado de entrada es igual al grado de salida en cada vértice. En este caso G se llama eulerian. Denotamos el grado de un vértice v por grados ( v ).
El teorema BEST establece que el número ec( G ) de circuitos eulerianos en un gráfico euleriano conectado G viene dado por la fórmula
Aquí t w ( G ) es el número de arborescencias , que son árboles dirigidos hacia la raíz en un vértice fijo w en G . El número t w (G) se puede calcular como determinante , mediante la versión del teorema del árbol matricial para gráficos dirigidos. Es una propiedad de los gráficos eulerianos que t v ( G ) = t w ( G ) por cada dos vértices v y w en un gráfico euleriano conectado G .
El teorema BEST muestra que el número de circuitos eulerianos en gráficos dirigidos se puede calcular en tiempo polinomial , un problema que es #P-completo para gráficos no dirigidos. [1] También se utiliza en la enumeración asintótica de circuitos eulerianos de grafos bipartitos completos y completos . [2] [3]
El teorema BEST se debe a van Aardenne-Ehrenfest y de Bruijn (1951), [4] §6, Teorema 6. Su demostración es biyectiva y generaliza las secuencias de de Bruijn . En una "nota agregada en la prueba", se refieren a un resultado anterior de Smith y Tutte (1941) que demuestra la fórmula para gráficas con grados (v) = 2 en cada vértice.
