Teorema BEST

En teoría de grafos, el teorema de BEST provee una fórmula producto para el número de ciclos eulerianos en un grafo (orientado) dirigido. El nombre es un acrónimo de los apellidos de sus descubridores: Nicolaas Govert de Bruijn, Tatyana Pavlovna Ehrenfest, Cedric Smith y William Thomas Tutte.

Sea G = (V, E) un grafo dirigido. 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. Denotamos el grado de entrada de un vértice v como deg(v).

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 t_w(G) es el número de arborescencias, á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 utilizando la versión del teorema de Kirchhoff para grafos dirigidos. Se tiene que t_v(G) = t_w(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.^[1]​ Se utiliza también para la enumeración asintótica de ciclos eulerianos de grafos completos y bipartitos completos.^[2]​^[3]​

El teorema de BEST fue enunciado por primera vez en esta forma en una «nota añadida en la demostración» en el artículo de Ehrenfest y De Bruijn (1951). La demostración original era biyectiva y generalizaba las sucesiones de De Bruijn. Es una variación de un resultado anterior de Smith y Tutte (1941).

---