En la teoría de grafos , una parte de las matemáticas discretas , el teorema BEST proporciona una fórmula de 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: de Bruijn , van Aardenne - Ehrenfest , S mith and T utte .
Sea G = ( V , E ) un grafo dirigido. 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 solo si G es conexo y el grado interior es igual al grado exterior en cada vértice. En este caso G se llama Euleriano. Denotamos el grado interior de un vértice v por grado ( v ).
El teorema BEST establece que el número ec( G ) de circuitos eulerianos en un grafo euleriano conexo 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 un determinante , mediante la versión del teorema del árbol de matrices para grafos dirigidos. Es una propiedad de los grafos eulerianos que t v ( G ) = t w ( G ) para cada dos vértices vyw en un grafo euleriano conexo G .
El teorema BEST muestra que el número de circuitos eulerianos en grafos dirigidos se puede calcular en tiempo polinomial , un problema que es #P-completo para grafos 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 sucesiones de de Bruijn . En una "nota agregada en la prueba", se refieren a un resultado anterior de Smith y Tutte (1941) que prueba la fórmula para gráficos con grados (v) = 2 en cada vértice.