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.

Inhalt 1 Precise statement 2 Anwendungen 3 Geschichte 4 Anmerkungen 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. Im 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 {Anzeigestil Betreibername {ec} (G)=t_{w}(G)Produkt _{vin V}{plötzlich (}Grad(v)-1{größer )}!.} 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, Satz 6. Their proof is bijective and generalizes the de Bruijn sequences. In einem "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, Kombinatorik, 10 (1995), nein. 4, 367–377. ^ M.I. Isaev, Asymptotic number of Eulerian circuits in complete bipartite graphs Archived 2010-04-15 at the Wayback Machine (auf Russisch), Proz. 52-nd MFTI Conference (2009), Moskau. ^ 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 Latein), 8: 128–140. Alle, W. T.; Schmied, C. EIN. 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. Alle, W. T. (1984), Graph Theory, Lektüre, Masse.: Addison-Wesley. Stanley, Richard P. (1999), Enumerative Kombinatorik, vol. 2, Cambridge University Press, ISBN 0-521-56069-1. Satz 5.6.2 Aigner, Martin (2007), A Course in Enumeration, Abschlusstexte in Mathematik, vol. 238, Springer, ISBN 3-540-39032-4. Kategorien: Directed graphsTheorems in graph theory

Wenn Sie andere ähnliche Artikel wissen möchten BEST theorem Sie können die Kategorie besuchen Directed graphs.

Hinterlasse eine Antwort

Deine Email-Adresse wird nicht veröffentlicht.

Geh hinauf

Wir verwenden eigene Cookies und Cookies von Drittanbietern, um die Benutzererfahrung zu verbessern Mehr Informationen