Vzdálenost odporu - Resistance distance

v teorie grafů, vzdálenost odporu mezi dvěma vrcholy a jednoduchý připojený graf, G, se rovná odpor mezi dvěma ekvivalentními body na elektrická síť, postavený tak, aby odpovídal G, s každým okraj nahrazuje se 1 ohm odpor. Je to metrický na grafy.

Definice

Na graf G, vzdálenost odporu Ω_i,j mezi dvěma vrcholy proti_i a proti_j je^[1]

${ displaystyle Omega _ {i, j}: = Gamma _ {i, i} + Gamma _ {j, j} - Gamma _ {i, j} - Gamma _ {j, i}}$

kde ${ displaystyle Gamma = left (L + { frac {1} {| V |}} Phi right) ^ {+}}$, s ${ displaystyle ^ {+}}$ označující Moore – Penrose inverzní, ${ displaystyle L}$ the Laplaciánská matice z G, ${ displaystyle | V |}$ je počet vrcholů v G, a ${ displaystyle Phi}$ je ${ displaystyle | V | krát | V |}$ matice obsahující všechny 1 s.

Vlastnosti odporové vzdálenosti

Li i = j pak

${ displaystyle Omega _ {i, j} = 0.}$

Pro neorientovaný graf

${ displaystyle Omega _ {i, j} = Omega _ {j, i} = gama _ {i, i} + gama _ {j, j} -2 gama _ {i, j}}$

Obecné pravidlo součtu

Pro všechny N-vrchol jednoduchý připojený graf G = (PROTI, E) a libovolné N×N matice M:

${ displaystyle sum _ {i, j ve V} (LML) _ {i, j} Omega _ {i, j} = - 2 operatorname {tr} (ML)}$

Z tohoto obecného pravidla součtu lze odvodit řadu vztahů v závislosti na výběru M. Dva poznámky jsou;

${ displaystyle { begin {zarovnáno} součet _ {(i, j) v E} Omega _ {i, j} & = N-1 součet _ {i$

Kde ${ displaystyle lambda _ {k}}$ jsou nenulové vlastní čísla z Laplaciánská matice. Tato neuspořádaná částka Σ_{i Ωjá, j} se nazývá Kirchhoffův index grafu.

Vztah k počtu stromů v grafu

Pro jednoduchý připojený graf G = (PROTI, E), vzdálenost odporu mezi dvěma vrcholy lze vyjádřit jako a funkce z soubor z klenout se nad stromy, T, z G jak následuje:

${ displaystyle Omega _ {i, j} = { začátek {případů} { frac { vlevo | {t: t v T, e_ {i, j} v t } vpravo vert} { left | T right vert}}, & (i, j) in E { frac { left | T'-T right vert} { left | T right vert}} , & (i, j) ne v E end {případů}}}$

kde ${ displaystyle T '}$ je sada koster pro graf ${ displaystyle G '= (V, E + e_ {i, j})}$.

Jako čtvercová euklidovská vzdálenost

Od Laplacian ${ displaystyle L}$ je symetrický a pozitivní semi-definitivní, tak je ${ displaystyle left (L + { frac {1} {| V |}} Phi right)}$, tedy jeho pseudo-inverze ${ displaystyle Gamma}$ je také symetrický a pozitivní semi-definitivní. Existuje tedy ${ displaystyle K}$ takhle ${ displaystyle Gamma = KK ^ { textyf {T}}}$ a můžeme napsat:

${ displaystyle Omega _ {i, j} = Gamma _ {i, i} + Gamma _ {j, j} - Gamma _ {i, j} - Gamma _ {j, i} = K_ { i} K_ {i} ^ { textyf {T}} + K_ {j} K_ {j} ^ { textyf {T}} - K_ {i} K_ {j} ^ { textyf {T}} - K_ {j} K_ {i} ^ { textyf {T}} = vlevo (K_ {i} -K_ {j} vpravo) ^ {2}}$

což ukazuje, že druhá odmocnina vzdálenosti odporu odpovídá Euklidovská vzdálenost v prostoru překlenutém ${ displaystyle K}$.

Spojení s Fibonacciho čísly

Graf ventilátoru je graf zapnutý ${ displaystyle n + 1}$ vrcholy, kde je hrana mezi vrcholy ${ displaystyle i}$ a ${ displaystyle n + 1}$ pro všechny ${ displaystyle i = 1,2,3, ... n,}$ a mezi vrcholem je hrana ${ displaystyle i}$ a ${ displaystyle i + 1}$ pro všechny ${ displaystyle i = 1,2,3, ..., n-1.}$

Vzdálenost odporu mezi vrcholem ${ displaystyle n + 1}$ a vrchol ${ displaystyle i in {1,2,3, ..., n }}$je ${ displaystyle { frac {F_ {2 (n-i) +1} F_ {2i-1}} {F_ {2n}}}}$ kde ${ displaystyle F_ {j}}$ je ${ displaystyle j}$-té Fibonacciho číslo pro ${ displaystyle j geq 0}$.^[2][3]

Viz také

• Vodivost (graf)

Reference

• Klein, D. J .; Randic, M. J. (1993). "Vzdálenost odporu". J. Math. Chem. 12: 81–95. doi:10.1007 / BF01164627.
• Gutman, Ivan; Mohar, Bojan (1996). „Kvazi-Wienerovy a Kirchhoffovy indexy se shodují“. J. Chem. Inf. Comput. Sci. 36 (5): 982–985. doi:10.1021 / ci960007t.
• Palacios, Jose Luis (2001). "Uzavřené vzorce pro Kirchhoffův index". Int. J. Quantum Chem. 81 (2): 135–140. doi:10.1002 / 1097-461X (2001) 81: 2 <135 :: AID-QUA4> 3.0.CO; 2-G.
• Babic, D .; Klein, D. J .; Lukovits, I .; Nikolic, S .; Trinajstic, N. (2002). Msgstr "Matice odporu a vzdálenosti: výpočetní algoritmus a jeho aplikace". Int. J. Quantum Chem. 90 (1): 166–167. doi:10,1002 / qua.10057.
• Klein, D. J. (2002). "Pravidla pro součet vzdálenosti odporu" (PDF). Croatica Chem. Acta. 75 (2): 633–649. Archivovány od originál (PDF) dne 2012-03-26.
• Bapat, Ravindra B .; Gutman, Ivan; Xiao, Wenjun (2003). „Jednoduchá metoda výpočtu vzdálenosti odporu“. Z. Naturforsch. 58a (9–10): 494–498. Bibcode:2003ZNatA..58..494B. doi:10.1515 / zna-2003-9-1003.
• Placios, Jose Luis (2004). „Fosterovy vzorce pomocí pravděpodobnosti a Kirchhoffova indexu“. Metoda. Comput. Appl. Probab. 6 (4): 381–387. doi:10.1023 / B: MCAP.0000045086.76839.54.
• Bendito, Enrique; Carmona, Angeles; Encinas, Andres M .; Gesto, Jose M. (2008). "Vzorec pro Kirchhoffův index". Int. J. Quantum Chem. 108 (6): 1200–1206. Bibcode:2008IJQC..108.1200B. doi:10,1002 / qua.21588.
• Zhou, Bo; Trinajstic, Nenad (2009). "Kirchhoffův index a odpovídající číslo". Int. J. Quantum Chem. 109 (13): 2978–2981. Bibcode:2009IJQC..109.2978Z. doi:10,1002 / qua.21915.
• Zhou, Bo; Trinajstic, Nenad (2009). „Na odporovou vzdálenost a Kirchhoffův index“. J. Math. Chem. 46: 283–289. doi:10.1007 / s10910-008-9459-3. hdl:10338.dmlcz / 140814.
• Zhou, Bo (2011). "Na součtu sil Laplacianských vlastních čísel a Laplacian Estrada Index grafů". Match Commun. Matematika. Comput. Chem. 62: 611–619. arXiv:1102.1144.

• Zhang, Heping; Yang, Yujun (2007). "Vzdálenost odporu a Kirchhoffův index v grafech cirkulace". Int. J. Quantum Chem. 107 (2): 330–339. Bibcode:2007IJQC..107..330Z. doi:10,1002 / qua.21068.

• Yang, Yujun; Zhang, Heping (2008). Msgstr "Některá pravidla pro vzdálenost odporu s aplikacemi". J. Phys. A: Math. Teor. 41 (44): 445203. Bibcode:2008JPhA ... 41R5203Y. doi:10.1088/1751-8113/41/44/445203.