MEJOR teorema

En la teoría de grafos , una rama 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) . Su nombre es un acrónimo de los nombres de quienes lo descubrieron: NG de Bruijn , Tatyana van Aardenne-Ehrenfest , Cedric Smith y WT Tutte .

Sea G  =  ( V , E ) un grafo dirigido. Un circuito euleriano es un camino cerrado dirigido que visita cada arista exactamente una vez. En 1736, Euler demostró que G tiene un circuito euleriano si y solo si G es conexo y el grado de entrada es igual al grado de salida en cada vértice. En este caso, G se denomina euleriano. Denotamos el grado de entrada de un vértice v por deg( 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

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

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 matricial para grafos dirigidos. Es una propiedad de los grafos eulerianos que t _v ( G )  = t _w ( G ) para cualquier par de vértices v y w en un grafo euleriano conexo G . 

El teorema BEST demuestra 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 completos y bipartitos 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 añadida en la demostración", se refieren a un resultado anterior de Smith y Tutte (1941) que demuestra la fórmula para grafos con deg(v)=2 en cada vértice.

• Euler, L. ( 1736), "Solutio problematis ad geometriam situs pertinentis" , Commentarii Academiae Scientiarum Petropolitanae (en latín), 8 : 128-140.
• Tutte, WT ; Smith, CAB (1941), "Sobre caminos unicursales en una red de grado 4", American Mathematical Monthly , 48 (4): 233–237 , doi : 10.2307/2302716 , JSTOR 2302716 .
• van Aardenne-Ehrenfest, T .; de Bruijn, NG (1951), "Circuitos y árboles en gráficos lineales orientados" (PDF) , Simon Stevin , 28 : 203– 217.
• Tutte, WT (1984), Teoría de grafos , Reading, Mass.: Addison-Wesley.
• Stanley, Richard P. (1999), Combinatoria enumerativa , vol.  2, Cambridge University Press , ISBN 0-521-56069-1Teorema 5.6.2
• Aigner, Martin (2007), Un curso de enumeración , Textos de posgrado en matemáticas, vol.  238, Springer, ISBN 978-3-540-39032-9.