Teorema de 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.

Enunciado preciso

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

${\displaystyle \operatorname {ec} (G)=t_{w}(G)\prod _{v\in V}{\bigl (}\deg(v)-1{\bigr )}!.}$ 

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.

Aplicaciones

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]​

Historia

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).

Referencias

1. Brightwell, Graham R.; Winkler, Peter (mayo de 2004). «Note on Counting Eulerian Circuits». CDAM Research Report LSE-CDAM-2004-12. Consultado el 26 de marzo de 2020. 
2. McKAY, Brendan D.; Robinson, Robert W. (1998/12). «Asymptotic Enumeration of Eulerian Circuits in the Complete Graph». Combinatorics, Probability and Computing (en inglés) 7 (4): 437-449. ISSN 1469-2163. doi:10.1017/S0963548398003642. Consultado el 26 de marzo de 2020. 
3. Isáyev, M. N. (2009). . Proc. 52-nd MFTI Conference (en ruso). Archivado desde el original el 15 de abril de 2010. 

Bibliografía

• Euler, L. (1736), «Solutio problematis ad geometriam situs pertinentis», Commentarii Academiae Scientiarum Petropolitanae (en latin) 8: 128-140 ..
• Tutte, W. T.; Smith, C. A. B. (1941), «On unicursal paths in a network of degree 4», American Mathematical Monthly 48: 233-237, doi:10.2307/2302716 ..
• van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951), «Circuits and trees in oriented linear graphs», Simon Stevin 28: 203-217 ..
• Tutte, W. T. (1984), Graph Theory, Reading, Mass.: Addison-Wesley ..
• Stanley, Richard P. (1999), Enumerative Combinatorics, Vol. 2, Cambridge University Press, ISBN 0-521-56069-1 ..
• Aigner, Martin (2007), A Course in Enumeration, Graduate Texts in Mathematics 238, Springer, ISBN 3-540-39032-4 ..

•   Datos: Q3527004