BEST theorem
E824089
The BEST theorem is a result in graph theory that gives a formula for counting the number of distinct Eulerian circuits in a directed graph using spanning arborescences and vertex degrees.
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
result in graph theory
ⓘ
theorem ⓘ |
| appliesTo |
Eulerian directed graph
ⓘ
directed graph ⓘ |
| area | enumerative combinatorics ⓘ |
| assumes |
in-degree equals out-degree at every vertex
ⓘ
strongly connected directed graph ⓘ |
| category | theorem in discrete mathematics ⓘ |
| concerns |
Eulerian circuit
ⓘ
counting Eulerian circuits ⓘ |
| doesNotApplyTo | non-Eulerian directed graphs ⓘ |
| field | graph theory ⓘ |
| formulaInvolves |
number of spanning in-arborescences rooted at a vertex
ⓘ
product of factorials of out-degrees minus one ⓘ |
| generalizes | counting formula for Eulerian circuits in undirected graphs via orientations ⓘ |
| givesCountAs | T_r × ∏_v (outdeg(v) − 1)! for a root r ⓘ |
| givesFormulaFor | number of distinct Eulerian circuits in a directed graph ⓘ |
| hasKeyCondition |
graph must be Eulerian
ⓘ
graph must be strongly connected ⓘ |
| holdsFor | finite directed graphs ⓘ |
| implies | existence of at least one Eulerian circuit in an Eulerian digraph ⓘ |
| nameAcronymOf | de Bruijn–van Aardenne-Ehrenfest–Smith–Tutte theorem NERFINISHED ⓘ |
| namedAfter |
Smith
NERFINISHED
ⓘ
Tutte NERFINISHED ⓘ de Bruijn NERFINISHED ⓘ van Aardenne-Ehrenfest NERFINISHED ⓘ |
| originallyProvedBy |
Cedric A. B. Smith
NERFINISHED
ⓘ
Nicolaas Govert de Bruijn NERFINISHED ⓘ Tatyana van Aardenne-Ehrenfest NERFINISHED ⓘ William T. Tutte NERFINISHED ⓘ |
| relatedTo |
Eulerian trail
NERFINISHED
ⓘ
Matrix-Tree theorem NERFINISHED ⓘ de Bruijn graph NERFINISHED ⓘ |
| relates | Eulerian circuits and spanning arborescences ⓘ |
| requires | choice of a root vertex ⓘ |
| usedFor |
analysis of network routing structures
ⓘ
combinatorial enumeration problems ⓘ counting Eulerian cycles in de Bruijn graphs ⓘ |
| usedIn |
coding theory
ⓘ
design of de Bruijn sequences ⓘ theoretical computer science ⓘ |
| usesConcept |
spanning arborescence
ⓘ
vertex in-degree ⓘ vertex out-degree ⓘ |
| usesTool | Matrix-Tree theorem NERFINISHED ⓘ |
| yearIntroducedApprox | 1950s ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.