Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(435 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
In [[graph theory]], the '''resistance distance''' between two [[vertex (graph theory)|vertices]] of a [[graph (mathematics)|simple connected graph]], ''G'', is equal to the [[electrical resistance|resistance]] between two equivalent points on an [[electrical network]], constructed so as to correspond to ''G'', with each [[graph (mathematics)|edge]] being replaced by a 1 [[ohm]] [[electrical resistance|resistance]]. It is a [[metric (mathematics)|metric]] on [[graph (mathematics)|graphs]].
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


==Definition==
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]]
* 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.


On a [[graph (mathematics)|graph]] ''G'', the '''resistance distance''' &Omega;<sub>''i'',''j''</sub> between two vertices ''v<sub>i</sub>'' and ''v<sub>j</sub>'' is
Registered users will be able to choose between the following three rendering modes:


:<math>
'''MathML'''
\Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i}\,
:<math forcemathmode="mathml">E=mc^2</math>
</math>


where &Gamma; is the [[Moore–Penrose inverse]] of the [[Laplacian matrix]] of ''G''. {{clarify|but we have not defined &Gamma; with subscripts|date=August 2014}}
<!--'''PNG'''  (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


==Properties of resistance distance==
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


If ''i'' = ''j'' then
<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].


:<math>\Omega_{i,j}=0.\,</math>
==Demos==


For an undirected graph
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:


:<math>
\Omega_{i,j}=\Omega_{j,i}=\Gamma_{i,i}+\Gamma_{j,j}-2\Gamma_{i,j}\,
</math>


===General sum rule===
* accessibility:
For any ''N''-vertex [[graph (mathematics)|simple connected graph]] ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') and arbitrary ''N''×''N'' [[matrix (mathematics)|matrix]] ''M'':
** 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.


:<math>\sum_{i,j \in V}(LML)_{i,j}\Omega_{i,j}=-2\operatorname{tr}(ML)\,</math>
==Test pages ==


From this generalized sum rule a number of relationships can be derived depending on the choice of ''M''. Two of note are;
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]]


:<math>\sum_{(i,j) \in E}\Omega_{i,j}=N-1</math>
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
:<math>\sum_{i<j \in V}\Omega_{i,j}=N\sum_{k=1}^{N-1} \lambda_{k}^{-1}</math>
==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 .
where the <math>\lambda_{k}</math> are the non-zero [[eigenvalues]] of the [[Laplacian matrix]]. This unordered sum {{math|&Sigma;<sub>i<j</sub>&Omega;</sub>i,j</sub>}} is called the Kirchhoff index of the graph.
 
===Relationship to the number of spanning trees of a graph===
 
For a simple connected graph ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E''), the '''resistance distance''' between two vertices may by expressed as a [[Function (mathematics)|function]] of the [[Set (mathematics)|set]] of [[spanning tree (mathematics)|spanning trees]], ''T'', of ''G'' as follows:
 
:<math>
\Omega_{i,j}=\begin{cases}
\frac{\left | \{t:t \in T, e_{i,j} \in t\} \right \vert}{\left |  T \right \vert},  & (i,j) \in E\\ \frac{\left | T'-T \right \vert}{\left |  T \right \vert},  &(i,j) \not \in E
\end{cases}
</math>
 
where <math>T'</math> is the set of spanning trees for the graph <math>G'=(V, E+e_{i,j})</math>.
 
===As a squared Euclidean distance===
Since the Laplacian <math>L</math> is symmetric and positive semi-definite, its pseudoinverse <math>\Gamma</math> is also symmetric and positive semi-definite.  Thus, there is a <math>K</math> such that <math>\Gamma = K K^T</math> and we can write:
 
:<math>\Omega_{i,j} = \Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i} = K_iK_i^T + K_jK_j^T - K_iK_j^T - K_jK_i^T = (K_i - K_j)^2</math>
 
showing that the square root of the resistance distance corresponds to the [[Euclidean distance]] in the space spanned by <math>K</math>.
 
===Connection with Fibonacci numbers ===
A fan graph is a graph on <math>n+1</math> vertices where there is an edge between vertex <math>i</math> and <math>n+1</math> for all <math>i = 1, 2, 3, ...n,</math> and there is an edge between vertex <math>i</math> and <math>i+1</math> for all <math>i = 1, 2, 3, ..., n-1.</math>
 
The resistance distance between vertex <math>n + 1</math> and vertex <math> i \in \{1,2,3,...,n\}</math>
is <math>\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} }</math> where <math>F_{j}</math> is the <math>j</math>-th Fibonacci number, for <math>j \geq 0</math>.<ref>http://link.springer.com/article/10.1007/s13226-010-0004-2</ref><ref>http://www.isid.ac.in/~rbb/somitnew.pdf</ref>
 
== See also ==
* [[Conductance (graph)]]
 
==References==
{{Reflist}}
* {{cite journal
|first1= D. J.
|last1=Klein
|first2=M. J.
|last2=Randic
|journal=J. Math. Chem.
|doi=10.1007/BF01164627
|title=Resistance Distance
|volume=12
|page=81
|year=1993
}}
* {{cite journal
|first1=Ivan
|last1=Gutman
|first2=Bojan
|last2=Mohar
|title=The quasi-Wiener and the Kirchhoff indices coincide
|year=1996
|journal=J. Chem. Inf. Comput. Sci.
|volume=36
|pages=982–985
|doi=10.1021/ci960007t
}}
* {{cite journal
|title=Closed-form formulas for the Kirchhoff index
|first1=Jose Luis
|last1=Palacios
|journal=Int. J. Quant. Chem.
|year=2001
|volume=81
|pages=135–140
|doi=10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G
}}
* {{cite journal
|first1=D.
|last1=Babic
|first2=D. J.
|last2=Klein
|first3=I.
|last3=Lukovits
|first4=S.
|last4=Nikolic
|first5=N.
|last5=Trinajstic
|title=Resistance-distance matrix: a computational algorithm and its application
|journal=Int. J. Quant. Chem.
|year=2002
|doi=10.1002/qua.10057
|volume=90
|number=1
|pages=166–167
}}
* {{cite journal
|url=http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf
|journal=Croatica Chem. Acta
|last1= Klein
|first1=D. J.
|title=Resistance Distance Sum Rules
|year=2002
|volume=75
|number=2
|pages=633–649
}}
* {{cite journal
|first1=Ravindra B.
|last1=Bapat
|first2=Ivan
|last2=Gutman
|first3=Wenjun
|last3=Xiao
|title=A simple method for computing resistance distance
|journal=Z. Naturforsch.
|year=2003
|volume=58a
|pages=494–498
|url=http://www.znaturforsch.com/aa/v58a/c58a.htm#No9
}}
* {{cite journal
|first1=Jose Luis
|last1=Placios
|title=Foster's formulas via probability and the Kirchhoff index
|journal=Method. Comput. Appl. Probal.
|year=2004
|volume=6
|number=4
|pages=381–387
|doi=10.1023/B:MCAP.0000045086.76839.54
}}
* {{cite journal
|first1=Enrique
|last1=Bendito
|first2=Angeles
|last2=Carmona
|first3=Andres M.
|last3=Encinas
|first4=Jose M.
|last4=Gesto
|title=A formula for the Kirhhoff index
|journal=Int. J. Quant. Chem.
|year=2008
|doi=10.1002/qua.21588
|pages=1200–1206
|volume=108
|number=6
|bibcode = 2008IJQC..108.1200B }}
* {{cite journal
|journal=Int. J. Quant. Chem.
|first1=Bo
|last1=Zhou
|title=The Kirchhoff index and the matching number
|first2=Nenad
|last2=Trinajstic
|volume=109
|year=2009
|pages=2978–2981
|doi=10.1002/qua.21915
|bibcode = 2009IJQC..109.2978Z }}
* {{cite journal
|first1=Bo
|last1=Zhou
|first2=Nenad
|last2=Trinajstic
|title=On resistance-distance and the Kirchhoff index
|journal=J. Math. Chem.
|year=2009
|volume=46
|pages=283–289
|doi=10.1007/s10910-008-9459-3
}}
* {{cite arXiv
|first1=Bo
|last1=Zhou
|title=On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs
|eprint=1102.1144
}}
 
* {{cite journal
|first1=Heping
|last1=Zhang
|first2=Yujun
|last2=Yang
|title=Resistance distance and Kirchhoff index in circulant graphs
|journal=Int. J. Quantum Chem.
|year=2007
|volume=107
|pages=330–339
|doi=10.1002/qua.21068
|bibcode = 2007IJQC..107..330Z }}
 
* {{cite journal
|first1=Yujun
|last1=Yang
|first2=Heping
|last2=Zhang
|title=Some rules on resistance distance with applications
|journal=J. Phys. A: Math. Theor.
|year=2008
|volume=41
|pages=445203
|doi=10.1088/1751-8113/41/44/445203
|bibcode = 2008JPhA...41R5203Y }}
 
[[Category:Graph theory]]

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"