BEST-teoremet

I grafteori, en del av den diskreta matematiken, ger BEST-teoremet en produktformel för antalet Eulerkretsar hos en riktad graf. Namnet är ett akronym av de personer som upptäckte teoremet: de Bruijn, van Aardenne-Ehrenfest, Smith och Tutte.

Påstående

Låt G = (V, E) vara en riktad graf. En Eulerkrets är en riktad sluten väg som går längs varje kant en och endast en gång. 1736 visade Euler att G har en Eulerkrets om och endast om G är sammanhängande och ingraden är lika med utgraden hos varje hörn. I detta fall kallas G Eulersk. Vi betecknar in- och utgraden hos ett hörn v med deg(v).

BEST-teoremet säger att antalet Eulerkretsar, ec(G) i en sammanhängande Eulersk graf G ges av formeln:

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

Här är t_w(G) antalet träd som är riktade mot en rot vid ett fixt hörn w i G. Talet t_w(G) kan beräknas som en determinant genom Kirchhoffs sats för riktade grafer. Det är en egenskap hos Eulerska grafer att t_v(G) = t_w(G) för varje par av hörn v och w i en sammanhängande Eulersk graf G.