Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(347 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
In [[graph theory]], a part of [[discrete mathematics]], the '''BEST theorem''' gives a product formula for the number of [[Eulerian circuit]]s in [[directed graph|directed]] (oriented) [[Graph (mathematics)|graphs]].  The name is an acronym of the names of people who discovered it: [[N. G. de Bruijn|de '''B'''ruijn]], [[Tatyana Pavlovna Ehrenfest|van Aardenne-'''E'''hrenfest]], [[Cedric Smith (statistician)|'''S'''mith]] and [[W. T. Tutte|'''T'''utte]].
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


== Precise statement ==
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
Let ''G'' = (''V'', ''E'') be a directed graph.  An Eulerian circuit is a directed closed path which visits each edge exactly once.  In 1736, [[Leonhard Euler|Euler]] showed that ''G'' has an Eulerian circuit if and only if ''G'' is [[connected graph|connected]] and the [[Directed_graph#Indegree_and_outdegree|indegree]] is equal to [[Directed_graph#Indegree_and_outdegree|outdegree]] at every vertex.  In this case ''G'' is called Eulerian. We denote these in- and out-degree of a vertex ''v'' by deg(''v'').  
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


The BEST theorem states that the number ec(''G'') of Eulerian circuits in a connected Eulerian graph ''G'' is given by the formula
Registered users will be able to choose between the following three rendering modes:


:<math>
'''MathML'''
\operatorname{ec}(G) = t_w(G) \prod_{v\in V} \bigl(\deg(v)-1\bigr)!.
:<math forcemathmode="mathml">E=mc^2</math>
</math>


Here ''t''<sub>''w''</sub>(''G'') is the number of [[Arborescence (graph theory)|arborescences]], which are [[tree (graph theory)|trees]] directed towards the root at a fixed vertex ''w'' in ''G''. The number ''t<sub>w</sub>(G)'' can be computed as a [[determinant]], by the version of the [[matrix tree theorem]] for directed graphs.  It is a property of Eulerian graphs that ''t''<sub>''v''</sub>(''G'')&nbsp;=&nbsp;''t''<sub>''w''</sub>(''G'') for every two vertices ''v'' and ''w'' in a connected Eulerian graph ''G''.
<!--'''PNG''' (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


== Applications ==
'''source'''
The BEST theorem shows that the number of Eulerian circuits in directed graphs can be computed in [[polynomial time]], a problem which is [[Sharp-P-complete|#P-complete]] for undirected graphs.<ref>Brightwell and [[Peter Winkler|Winkler]], "[http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf Note on Counting Eulerian Circuits]", CDAM Research Report LSE-CDAM-2004-12, 2004.</ref> It is also used in the asymptotic enumeration of Eulerian circuits of [[complete graph|complete]] and [[complete bipartite graph]]s.<ref>[[Brendan McKay]] and Robert W. Robinson, [http://cs.anu.edu.au/~bdm/papers/euler.pdf Asymptotic enumeration of eulerian circuits in the complete graph], ''[[Combinatorica]]'', 10 (1995), no. 4, 367–377.</ref><ref>M.I. Isaev, [http://www.mipt.ru/nauka/52conf/materialy/07-FUPM1-site.pdf#page=56 Asymptotic number of Eulerian circuits in complete bipartite graphs] (in [[Russian language|Russian]]), Proc. 52-nd MFTI Conference (2009), Moscow.</ref>
:<math forcemathmode="source">E=mc^2</math> -->


== History ==
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].
The BEST theorem was first stated in this form in a "note added in proof" to the  Aardenne-Ehrenfest and de Bruijn paper (1951). The original proof was [[bijective proof|bijective]] and generalized the [[de Bruijn sequence]]s.  It is a variation on an earlier result by Smith and Tutte (1941).


== Notes ==
==Demos==
{{reflist}}


== References ==
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:
*{{citation|last=Euler|first=L.|authorlink=Leonhard Euler|url=http://www.math.dartmouth.edu/~euler/pages/E053.html|title=Solutio problematis ad geometriam situs pertinentis|language=Latin|journal=Commentarii Academiae Scientiarum Petropolitanae|volume=8|year=1736|pages=128–140}}.
*{{citation|first1=W. T.|last1=Tutte|author1-link=W. T. Tutte|first2=C. A. B.|last2=Smith|author2-link=Cedric Smith (statistician)|title=On unicursal paths in a network of degree 4|journal=[[American Mathematical Monthly]]|volume=48|year=1941|pages=233–237|jstor=2302716}}.
*{{citation|author1-link=Tatyana Pavlovna Ehrenfest|first1=T.|last1=van Aardenne-Ehrenfest|author2-link=Nicolaas Govert de Bruijn|first2=N. G.|last2=de Bruijn|title=Circuits and trees in oriented linear graphs|journal=[[Simon Stevin (journal)|Simon Stevin]]|volume=28|year=1951|pages=203–217|url=http://repository.tue.nl/597493}}.
*{{citation|first=W. T.|last=Tutte|authorlink=W. T. Tutte|title=Graph Theory|publisher=Addison-Wesley|location=Reading, Mass.|year=1984}}.
*{{citation|authorlink=Richard P. Stanley|last=Stanley|first=Richard P.|year=1999|url=http://www-math.mit.edu/~rstan/ec/|title=Enumerative Combinatorics|volume=Vol. 2|publisher=[[Cambridge University Press]]|isbn=0-521-56069-1}}.
*{{citation|authorlink=Martin Aigner|last=Aigner|first=Martin|title=A Course in Enumeration|year=2007|isbn=3-540-39032-4|series=Graduate Texts in Mathematics|volume=238|publisher=Springer}}.




[[Category:Directed graphs]]
* accessibility:
[[Category:Theorems in graph theory]]
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.
 
==Test pages ==
 
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]
 
*[[Inputtypes|Inputtypes (private Wikis only)]]
*[[Url2Image|Url2Image (private Wikis only)]]
==Bug reporting==
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"