BEST theorem

BEST theorem In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte.

Contents 1 Precise statement 2 Applications 3 History 4 Notes 5 References Precise statement Let G = (V, E) be a directed graph. An Eulerian circuit is a directed closed path which visits each edge exactly once. In 1736, Euler showed that G has an Eulerian circuit if and only if G is connected and the indegree is equal to outdegree at every vertex. In this case G is called Eulerian. We denote the indegree of a vertex v by deg(v).

The BEST theorem states that the number ec(G) of Eulerian circuits in a connected Eulerian graph G is given by the formula {displaystyle operatorname {ec} (G)=t_{w}(G)prod _{vin V}{bigl (}deg(v)-1{bigr )}!.} Here tw(G) is the number of arborescences, which are trees directed towards the root at a fixed vertex w in G. The number tw(G) can be computed as a determinant, by the version of the matrix tree theorem for directed graphs. It is a property of Eulerian graphs that tv(G) = tw(G) for every two vertices v and w in a connected Eulerian graph G.

Applications The BEST theorem shows that the number of Eulerian circuits in directed graphs can be computed in polynomial time, a problem which is #P-complete for undirected graphs.[1] It is also used in the asymptotic enumeration of Eulerian circuits of complete and complete bipartite graphs.[2][3] History The BEST theorem is due to van Aardenne-Ehrenfest and de Bruijn (1951),[4] §6, Theorem 6. Their proof is bijective and generalizes the de Bruijn sequences. In a "note added in proof", they refer to an earlier result by Smith and Tutte (1941) which proves the formula for graphs with deg(v)=2 at every vertex.

Notes ^ Brightwell and Winkler, "Note on Counting Eulerian Circuits", CDAM Research Report LSE-CDAM-2004-12, 2004. ^ Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377. ^ M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs Archived 2010-04-15 at the Wayback Machine (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow. ^ van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951). "Circuits and trees in oriented linear graphs". Simon Stevin. 28: 203–217. References Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Petropolitanae (in 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, JSTOR 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. Theorem 5.6.2 Aigner, Martin (2007), A Course in Enumeration, Graduate Texts in Mathematics, vol. 238, Springer, ISBN 3-540-39032-4. Categories: Directed graphsTheorems in graph theory

Si quieres conocer otros artículos parecidos a BEST theorem puedes visitar la categoría Directed graphs.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.


Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información