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

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

Here t_w(G) is the number of arborescences, which are trees directed towards the root at a fixed vertex w in G. The number t_w(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 t_v(G) = t_w(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 was first stated in this form in a "note added in proof" to the paper of van Aardenne-Ehrenfest and de Bruijn (1951). The original proof was bijective and generalized the de Bruijn sequences. It is a variation on an earlier result by Smith and Tutte (1941).

Notes

1. ^Brightwell and Winkler, "Note on Counting Eulerian Circuits", CDAM Research Report LSE-CDAM-2004-12, 2004.
2. ^Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.
3. ^M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs (in Russian), Proc. 52-nd MFTI Conference (2009), Moscow.

References

{{citation|last=Euler|first=L.|authorlink=Leonhard Euler|url=http://www.math.dartmouth.edu/~euler/pages/E053.html|title=Solutio problematis ad geometriam situs pertinentis|language=Latin|journal=Commentarii Academiae Scientiarum Petropolitanae|volume=8|year=1736|pages=128–140}}.

{{citation|first1=W. T.|last1=Tutte|author1-link=W. T. Tutte|first2=C. A. B.|last2=Smith|author2-link=Cedric Smith (statistician)|title=On unicursal paths in a network of degree 4|journal=American Mathematical Monthly|volume=48|year=1941|pages=233–237|jstor=2302716|doi=10.2307/2302716}}.

{{citation|author1-link=Tatyana Pavlovna Ehrenfest|first1=T.|last1=van Aardenne-Ehrenfest|author2-link=Nicolaas Govert de Bruijn|first2=N. G.|last2=de Bruijn|title=Circuits and trees in oriented linear graphs|journal=Simon Stevin|volume=28|year=1951|pages=203–217|url=http://repository.tue.nl/597493}}.

{{citation|first=W. T.|last=Tutte|authorlink=W. T. Tutte|title=Graph Theory|publisher=Addison-Wesley|location=Reading, Mass.|year=1984}}.

{{citation|authorlink=Richard P. Stanley|last=Stanley|first=Richard P.|year=1999|url=http://www-math.mit.edu/~rstan/ec/|title=Enumerative Combinatorics|volume=Vol. 2|publisher=Cambridge University Press|isbn=0-521-56069-1}}.

{{citation|authorlink=Martin Aigner|last=Aigner|first=Martin|title=A Course in Enumeration|year=2007|isbn=3-540-39032-4|series=Graduate Texts in Mathematics|volume=238|publisher=Springer}}.

2 : Directed graphs|Theorems in graph theory