BEDSTE sætning
I diskret matematik og især i grafteori , BEST sætning giver en formel for antallet af Eulerian kredsløb af en rettet graf . Navnet er et akronym af mennesker, der har samarbejdet om dets udvikling, dvs. fra B ruijn , van Aardenne- E hrenfest , Cedric S mith (in) og T Utte .
Stater
Lad være en rettet graf ( S er sæt af hjørner, A for buer). Et Eulerian-kredsløb er en lukket sti, der passerer nøjagtigt en gang gennem hver bue. Det er i 1736, at Euler angiver, at der har et Euleriansk kredsløb, hvis og kun hvis det er forbundet, og at ethvert toppunkt har den samme udgående grad som den indkommende grad , idet det komplette bevis udgives af Hierholzer i 1873. I dette tilfælde siges eulerian . Graden (ind- eller udrejse) af et toppunkt bemærkes .
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)
Sætning - Antallet af euleriske kredsløb i en graf er givet med formlen:
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)
hvor er nogen fast toppunkt , og hvor er antallet af spænder , rod , orienterede træer.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 værdien af en determinant i kraft af Kirchhoffs sætning for rettet graf. Det faktum, at tallene er ens for alle hjørner af, er en egenskab ved 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)
Ansøgninger
BESTs sætning viser, at antallet af Eulerian-kredsløb med orienterede grafer kan beregnes på polynomisk tid , hvilket placerer det i P-klassen , mens det er et # P- komplet problem for ikke-rettede grafer.
Teoremet bruges også i den asymptotiske optælling af Eulerianske kredsløb af komplette grafer og af fulde bipartitgrafer .
Historie
BESTs sætning blev først anført i 1951 i en "note tilføjet til testene" af artiklen ( van Aardenne-Ehrenfest og de Bruijn 1951 ). Det originale bevis er bindende og er blevet udvidet til de Bruijns suiter . Dette er en variation af et tidligere resultat fra Tutte og Smith 1941 .
Bemærkninger
-
(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 anden workshop om analytisk algoritmik og kombinatorik , Vancouver, BC, Canada, SIAM ,2005( ISBN 0-89871-596-2 , læs online ) , s. 259-262.
-
(in) Brendan McKay og Robert W. Robinson , " Asymptotisk optælling af euleriske kredsløb i den fulde graf " , combinatorica , vol. 10, nr . 4,1995, s. 367–377 ( læs online ).
-
(i) Mikhail Isaev , " Asymptotisk Funktionsmåde for Antal Eulerian Circuits " , Elektronisk Tidende Kombinatorik , vol. 18, nr . 1,2011( læs online ).
(fr) Denne artikel er helt eller delvist hentet fra den
engelske Wikipedia- artikel med titlen
" BEST teorem " ( se forfatterlisten ) .
Referencer
-
(la) Leonard Euler , “ Solutio problematis ad geometriam situs relevantis ” , Kommentar. Academiae Sci. I. Petropolitanae , vol. 8,1736, s. 128-140 ( læs online ).
-
(en) William Tutte og Cedric AB Smith , " On Unicursal Paths in a Network of Degree 4 " , American Mathematical Monthly , bind. 48,1941, s. 233-237.
-
(en) Tatiana Pavlovna van Aardenne-Ehrenfest og Nicolaas Govert de Bruijn , " Kredsløb og træer i orienterede lineære grafer " , Simon Stevin , vol. 28,1951, s. 203-217 ( læs online ).
-
(en) William Tutte , Graph Theory , Addison-Wesley ,1984.
-
(en) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ detaljer af udgaver ] ( online præsentation ).
-
(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;">