Resistivt avstånd

Det resistiva avståndet mellan två hörn av en enkel sammankopplad graf G är lika med resistansen mellan två ekvivalenta punkter i en elektrisk krets konstruerad genom att ersätta varje kant av grafen med ett motstånd på 1 ohm . Resistiva avstånd är ett mått på grafer .

Definition

På graf G är det resistiva avståndet Ω i , j mellan två hörn v i och v j

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

där Γ är den inversa Moore–Penrose -matrisen av Kirchhoff-matrisen i grafen G .

Resistiva avståndsegenskaper

Om i = j då

\Omega _{i,j}=0.

För en oriktad graf

{\displaystyle \Omega _{i,j}=\Omega _{j,i}=\Gamma _{i,i}+\Gamma _{j,j}-2\Gamma _{i,j))

Den allmänna summaregeln

För en enkel sammankopplad graf med N hörn och en godtycklig matris M , $G=(V,E)$ $N \ gånger N$

\sum _{i,j\in V}(LML)_{i,j}\Omega _{i,j}=-2\operatörsnamn {tr} (ML)

Från denna generaliserade summaregel kan ett anslutningsnummer erhållas beroende på valet av M . Två av dem

{\begin{aligned}\sum _{(i,j)\in E}\Omega _{i,j}&=N-1\\\sum _{i<j\in V}\Omega _{i,j}&=N\summa _{k=1}^{N-1}\lambda _{k}^{-1}\end{aligned}}

var är egenvärden som inte är noll för Kirchhoff-matrisen . Denna summa kallas grafens Kirchhoff-index. $\lambda _{{k}}$ ${\displaystyle \Sigma _{i<j}\Omega _{i,j))$

Samband med antalet spännande träd i en graf

För en enkel sammankopplad graf kan det resistiva avståndet mellan två hörn uttryckas som en funktion på uppsättningen av spännande träd T i graf G : $G'=(V,E)$

\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)\inte \i E\end{cases}}

var är uppsättningen av spännande träd i grafen . $T'$ $G'=(V,E+e_{i,j})$

Som kvadraten på det euklidiska avståndet

Eftersom Laplacian är symmetrisk och positiv semidefinit, är dess pseudoinversa matris också symmetrisk och positiv semidefinit. Då finns det sådana att vi kan skriva: $L$ $\Gamma$ $K$ $\Gamma =KK^{\textsf {T}}$

\Omega _{i,j}=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i}=K_{ i}K_{i}^{\textsf {T}}+K_{j}K_{j}^{\textsf {T}}-K_{i}K_{j}^{\textsf {T}}-K_ {j}K_{i}^{\textsf {T}}=\left(K_{i}-K_{j}\right)^{2}

detta visar att kvadraten på det resistiva avståndet motsvarar det euklidiska avståndet i rymden som spänns av . $K$

Anslutning med Fibonacci-nummer

En fläkt är en graf med hörn, där det finns kanter mellan hörn och för alla och det finns en kant mellan hörn och för alla $n+1$ $i$ $n+1$ $i=1,2,3,...n,$ $i$ $i+1$ $i=1,2,3,...,n-1.$

Det resistiva avståndet mellan en vertex och hörn är , där är det -th Fibonacci-talet, för [1] [2] . $n+1$ ${\displaystyle i\in \{1,2,3,...,n\))$ ${\displaystyle {\frac {F_{2(ni)+1}F_{2i-1}}{F_{2n))))$ ${\displaystyle F_{j))$ $j$ $j\geqslant 0$

Se även

Konduktivitetsgraf

Anteckningar

↑ Bapat, Gupta, 2010 , sid. 1–13.
↑ Källa . Hämtad 7 februari 2019. Arkiverad från originalet 30 augusti 2021. (obestämd)

Litteratur

Bapat RB, Somit Gupta. Motståndsavstånd i hjul och fläktar // Indian Journal of Pure and Applied Mathematics. - 2010. - T. 41 . - doi : 10.1007/s13226-010-0004-2 .
Klein DJ, Randic MJ Resistance Distance // J. Math. Chem.. - 1993. - T. 12 . — S. 81–95 . - doi : 10.1007/BF01164627 .
Ivan Gutman, Bojan Mohar. De kvasi-Wiener- och Kirchhoff-indexen sammanfaller // J. Chem. inf. Comput. Sci .. - 1996. - T. 36 . — S. 982–985 . doi : 10.1021 / ci960007t .
Jose Luis Palacios. Formler i sluten form för Kirchhoff-index // Int. J. Quantum Chem.. - 2001. - V. 81 , nr. 2 . — S. 135–140 . - doi : 10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G .
Babic D., Klein DJ, Lukovits I., Nikolic S., Trinajstic N. Resistance-distance matrix: a computational algorithm and its application // Int. J. Quantum Chem.. - 2002. - T. 90 . — S. 166–167 . - doi : 10.1002/qua.10057 .
Klein DJ Resistance Distance Sum Rules // Croatica Chem. acta. - 2002. - T. 75 . — S. 633–649 . Arkiverad från originalet den 26 mars 2012.
Ravindra B. Bapat, Ivan Gutman, Wenjun Xiao. En enkel metod för att beräkna resistansavstånd // Z. Naturforsch .. - 2003. - T. 58a . — S. 494–498 . - doi : 10.1515/zna-2003-9-1003 . - .
Jose Luis Placios. Fosters formler via sannolikhet och Kirchhoff-index // Metod. Comput. Appl. Sannolikt.. - 2004. - T. 6 . — S. 381–387 . - doi : 10.1023/B:MCAP.0000045086.76839.54 .
Enrique Bendito, Angeles Carmona, Andres M. Encinas, Jose M. Gesto. En formel för Kirchhoff-index // Int. J. Quantum Chem.. - 2008. - T. 108 . - S. 1200-1206 . - doi : 10.1002/qua.21588 . — .
Bo Zhou, Nenad Trinajstic. Kirchhoff-indexet och matchningsnumret // Int. J. Quantum Chem.. - 2009. - V. 109 , nr. 13 . — S. 2978–2981 . - doi : 10.1002/qua.21915 . - .
Bo Zhou, Nenad Trinajstic. Om motståndsavstånd och Kirchhoff-index // J. Math. Chem.. - 2009. - T. 46 . — S. 283–289 . - doi : 10.1007/s10910-008-9459-3 .
Bo Zhou. På summan av potenserna för Laplacian egenvärden och Laplacian Estrada Index av grafer // Match Commun. Matematik. Comput. Chem. - 2011. - T. 62 . — S. 611–619 . - arXiv : 1102.1144 .

Heping Zhang, Yujun Yang. Motståndsavstånd och Kirchhoff-index i cirkulationsdiagram // Int. J. Quantum Chem.. - 2007. - V. 107 , nr. 2 . — S. 330–339 . - doi : 10.1002/qua.21068 . — .
Yujun Yang, Heping Zhang. Några regler om motståndsavstånd med applikationer // J. Phys. A: Matematik. Theor .. - 2008. - T. 41 , nr. 44 . - S. 445203 . - doi : 10.1088/1751-8113/41/44/445203 . - .