Twierdzenie BEST
W oddzielnych matematyki , a w szczególności w teorii wykres , Besta twierdzenie podaje wzór dla liczby Eulera układów o skierowanej wykresie . Nazwa jest akronimem osób, które współpracowały przy jego opracowaniu, tj. Z B ruijn , van Aardenne- E hrenfest , Cedric S mith (in) i T Utte .
Stany
Pozwolić skierowane wykres ( S jest zbiorem wierzchołków że łuków). Obwód Eulera jest zamknięta ścieżka, która przechodzi dokładnie raz przez każdy z łuku. To właśnie w 1736 roku, że Euler stwierdza, że ma obwód Eulera wtedy i tylko wtedy, gdy jest podłączony i że każdy wierzchołek ma ten sam stopień wychodzący jako stopnia wejściowego , kompletny dowód publikowane przez Hierholzer w roku 1873. W tym przypadku mówi się Eulera . Stopień (wejście lub wyjście) o wierzchołku zauważyć .
sol=(S,W){\ Displaystyle G = (S, A)}
sol{\ displaystyle G}
sol{\ displaystyle G}
sol{\ displaystyle G}
s{\ displaystyle s}
deg(s){\ Displaystyle \ deg (s)}![\ deg (s)](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb5fcb75ca6eb90a5aa49d482823a240e1cea48a)
Twierdzenie - Liczba obwodów Eulera grafu jest określona wzorem:
ec(sol){\ displaystyle \ operatorname {ec} (G)}
sol{\ displaystyle G}![sol](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
ec(sol)=ts0(sol)∏s∈S(deg(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)
gdzie jest jakikolwiek ustalony wierzchołek , a gdzie jest liczba rozpinających się , korzeni , zorientowanych drzew.s0{\ displaystyle s_ {0}}
sol{\ displaystyle G}
ts0(sol){\ displaystyle t_ {s_ {0}} (G)}
sol{\ displaystyle G}
s0{\ displaystyle s_ {0}}
s0.{\ displaystyle s_ {0}.}
Liczbę można obliczyć jako wartość wyznacznika na podstawie twierdzenia Kirchhoffa dla grafów skierowanych. Fakt, że liczby są równe dla wszystkich wierzchołków o to właściwość wykresach Eulera.
ts0(sol){\ displaystyle t_ {s_ {0}} (G)}
ts0(sol){\ displaystyle t_ {s_ {0}} (G)}
s0{\ displaystyle s_ {0}}
sol{\ displaystyle G}![sol](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
Aplikacje
Twierdzenie BEST-a pokazuje, że liczbę obwodów Eulera grafów zorientowanych można obliczyć w czasie wielomianowym , co umieszcza ją w klasie P , podczas gdy jest to problem #P -kompletny dla grafów niekierowanych.
Twierdzenie jest również używane w asymptotycznym wyliczaniu obwodów Eulera grafów pełnych i pełnych grafów dwudzielnych .
Historia
Twierdzenie BESTa zostało po raz pierwszy sformułowane w 1951 r. W „notatce dodanej do testów” artykułu ( van Aardenne-Ehrenfest i de Bruijn 1951 ). Oryginalny dowód jest bijektywny i został rozszerzony na suity de Bruijna . Jest to odmiana wcześniejszego wyniku z Tutte and Smith 1941 .
Uwagi
-
(w) Graham Brightwell and Peter Winkler , „Counting Eulerian Tours is # P-Complete” w Demetrescu C., R. i R. Sedgewick Tamassia (redaktorzy), ALENEX / Analco: Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments oraz Second Workshop on Analytic Algorithmics and Combinatorics , Vancouver, BC, Canada, SIAM ,2005( ISBN 0-89871-596-2 , czytaj online ) , str. 259-262.
-
(w) Brendan McKay i Robert W. Robinson , " Asymptotic enumeration of eulerian Circuits in the full graph " , combinatorica , vol. 10 N O 4,1995, s. 367–377 ( czytaj online ).
-
(w) Michaił Isaev , „ Asymptotic Behaviour of the Number of Eulerian Circuits ” , Electronic Journal of Combinatorics , vol. 18, n o 1,2011( czytaj online ).
(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu z
angielskiej Wikipedii zatytułowanego
„ Twierdzenie BEST ” ( zobacz listę autorów ) .
Bibliografia
-
(la) Leonard Euler , „ Solutio problematis ad geometriam situs relatedis ” , Comment. Academiae Sci. I. Petropolitanae , t. 8,1736, s. 128-140 ( czytaj online ).
-
(en) William Tutte i 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 i Nicolaas Govert de Bruijn , „ Obwody i drzewa w zorientowanych wykresach liniowych ” , Simon Stevin , vol. 28,1951, s. 203-217 ( czytaj online ).
-
(en) William Tutte , Graph Theory , Addison-Wesley ,1984.
-
(en) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ szczegóły wydań ] ( prezentacja online ).
-
(en) Martin Aigner , A Course in Enumeration , Springer-Verlag ,2007( ISBN 978-3-540-39032-9 i 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;">