BESTE teorem
I diskret matematikk , og spesielt i grafteori , gir BESTs setning en formel for antall Eulerian-kretser i en rettet graf . Navnet er et akronym av mennesker som har samarbeidet i utviklingen, dvs. fra B ruijn , van Aardenne- E hrenfest , Cedric S mith (in) og T Utte .
Stater
La være en rettet graf ( S er settet med hjørner, A for buer). En Eulerian-krets er en lukket sti som går nøyaktig en gang gjennom hver bue. Det er i 1736 at Euler oppgir at det har en Eulerian-krets hvis og bare hvis den er koblet til, og at et toppunkt har samme utgående grad som den innkommende graden , og det komplette beviset ble publisert av Hierholzer i 1873. I dette tilfellet blir det sagt eulerian . Graden (inn eller ut) av toppunktet er notert .
G=(S,PÅ){\ displaystyle G = (S, A)}
G{\ displaystyle G}
G{\ displaystyle G}
G{\ displaystyle G}
s{\ displaystyle s}
grader(s){\ displaystyle \ deg (s)}![\ deg (er)](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb5fcb75ca6eb90a5aa49d482823a240e1cea48a)
Teorem - Antallet Eulerian-kretser i en graf er gitt av formelen:
ec(G){\ displaystyle \ operatorname {ec} (G)}
G{\ displaystyle G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
ec(G)=ts0(G)∏s∈S(grader(s)-1)!{\ displaystyle \ operatorname {ec} (G) = t_ {s_ {0}} (G) \ prod _ {s \ in S} {\ bigl (} \ deg (s) -1 {\ bigr)}!}![{\ displaystyle \ operatorname {ec} (G) = t_ {s_ {0}} (G) \ prod _ {s \ in S} {\ bigl (} \ deg (s) -1 {\ bigr)}!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69e0af18075c5e36433b2eb98b551507a200cd83)
der er noen fast toppunkt , og der er antallet spenner , rot , orientert trær.s0{\ displaystyle s_ {0}}
G{\ displaystyle G}
ts0(G){\ displaystyle t_ {s_ {0}} (G)}
G{\ displaystyle G}
s0{\ displaystyle s_ {0}}
s0.{\ displaystyle s_ {0}.}
Antallet kan beregnes som verdien av en determinant i kraft av Kirchhoffs teorem for dirigerte grafer. Det faktum at tallene er like for alle hjørner av er en egenskap av euleriske grafer.
ts0(G){\ displaystyle t_ {s_ {0}} (G)}
ts0(G){\ displaystyle t_ {s_ {0}} (G)}
s0{\ displaystyle s_ {0}}
G{\ displaystyle G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
applikasjoner
BESTs teorem viser at antall Eulerian-kretser med orienterte grafer kan beregnes på polynomisk tid , noe som setter det i P-klassen , mens det er et # P- komplett problem for ikke-rettede grafer.
Teoremet brukes også i den asymptotiske oppregningen av Eulerian-kretser med komplette grafer og komplette bipartittgrafer .
Historie
BESTs teorem ble først uttalt i 1951, i en "note lagt til testene" av artikkelen ( van Aardenne-Ehrenfest og de Bruijn 1951 ). Det originale beviset er bindende og har blitt utvidet til de Bruijns suiter . Dette er en variant av et tidligere resultat fra Tutte og Smith 1941 .
Merknader
-
(i) Graham Brightwell og Peter Winkler , "Counting Eulerian Tours is # P-Complete" i Demetrescu C., R. og R. Sedgewick Tamassia (redaktører), ALENEX / Analco: Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments og den andre workshop om analytisk algoritmikk og kombinatorikk , Vancouver, BC, Canada, SIAM ,2005( ISBN 0-89871-596-2 , leses online ) , s. 259-262.
-
(in) Brendan McKay og Robert W. Robinson , " Asymptotic enumeration of eulerian circuits in the full graph " , combinatorica , vol. 10, n o 4,1995, s. 367–377 ( les online ).
-
(i) Mikhail Isaev , " Asymptotic Behavior of the Number of Eulerian Circuits " , Electronic Journal of Combinatorics , vol. 18, n o 1,2011( les online ).
(no) Denne artikkelen er delvis eller helt hentet fra den
engelske Wikipedia- artikkelen med tittelen
" BEST teorem " ( se forfatterlisten ) .
Referanser
-
(la) Leonard Euler , “ Solutio problematis ad geometriam situs relevantis ” , Kommentar. Academiae Sci. I. Petropolitanae , vol. 8,1736, s. 128-140 ( les online ).
-
(no) William Tutte og Cedric AB Smith , " On Unicursal Paths in a Network of Degree 4 " , American Mathematical Monthly , vol. 48,1941, s. 233-237.
-
(en) Tatiana Pavlovna van Aardenne-Ehrenfest og Nicolaas Govert de Bruijn , " Circuits and trees in orientated linear graphs " , Simon Stevin , vol. 28,1951, s. 203-217 ( les online ).
-
(no) William Tutte , Graph Theory , Addison-Wesley ,1984.
-
(no) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ detalj av utgaver ] ( online presentasjon ).
-
(en) Martin Aigner , A Course in Enumeration , Springer-Verlag ,2007( ISBN 978-3-540-39032-9 og 3-540-39032-4 ).
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">