Teorema de BEST

Un ciclo euleriano es un camino cerrado dirigido que pasa por cada arista exactamente una vez.En 1736, Euler demostró que G tiene un ciclo euleriano si y solo si G es conexo y el grado de entrada es igual al grado de salida en todos los vértices.En este caso, se dice que G es euleriano.El teorema de BEST afirma que el número de ciclos eulerianos ec(G) en un grafo euleriano conexo G está dado por la fórmula donde tw(G) es el número de arborescencias, árboles dirigidos hacia la raíz en un vértice fijo w en G. El número tw(G) se puede calcular como un determinante utilizando la versión del teorema de Kirchhoff para grafos dirigidos.Se tiene que tv(G) = tw(G) para todo par de vértices v y w en un grafo euleriano conexo G. El teorema de BEST muestra que el número de ciclos eulerianos en grafos dirigidos puede calcularse en tiempo polinomial, problema #P-completo para grafos no dirigidos.