Distanța rezistivă

Distanța rezistivă dintre două vârfuri ale unui grafic simplu conectat G este egală cu rezistența dintre două puncte echivalente ale unui circuit electric construit prin înlocuirea fiecărei margini a graficului cu o rezistență de 1 ohm . Distanțele rezistive sunt o metrică pe grafice .

Definiție

Pe graficul G , distanța rezistivă Ω i , j dintre două vârfuri v i și v j este

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

unde Γ este matricea inversă Moore–Penrose a matricei Kirchhoff a graficului G .

Proprietăți de distanță rezistivă

Dacă i = j atunci

\Omega _{i,j}=0.

Pentru un grafic nedirecționat

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

Regula generală a sumei

Pentru orice graf conex simplu cu N vârfuri și o matrice arbitrară M , $G=(V,E)$ $N \ori N$

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

Din această regulă generalizată a sumei, se poate obține un număr de conexiune în funcție de alegerea lui M . Doi dintre ei

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

unde sunt valori proprii diferite de zero ale matricei Kirchhoff . Această sumă se numește indicele Kirchhoff al graficului. $\lambda _{{k}}$ $\Sigma _{i<j}\Omega _{i,j)$

Relația cu numărul de arbori de acoperire ai unui grafic

Pentru un graf simplu conectat, distanța rezistivă dintre două vârfuri poate fi exprimată ca funcție pe mulțimea arborilor care se întind T din graficul 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)\în E\\{\frac {\left|T'-T\right\vert }{\left|T\right\vert )) ,&(i,j)\nu \în E\end{cazuri}}

unde este mulțimea arborilor care se întind ai graficului . $T'$ $G'=(V,E+e_{i,j})$

Ca pătrat al distanței euclidiene

Deoarece laplacianul este simetric și semidefinit pozitiv, matricea sa pseudoinversă este , de asemenea, simetrică și semidefinită pozitivă. Atunci există astfel încât să putem scrie: $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}

aceasta arată că pătratul distanței rezistive corespunde distanței euclidiene în spațiu acoperită de . $K$

Legătura cu numerele Fibonacci

Un evantai este un grafic cu vârfuri, în care există muchii între vârfuri și pentru oricare și există o muchie între vârfuri și pentru toate $n+1$ $i$ $n+1$ $i=1,2,3,...n,$ $i$ $i+1$ $i=1,2,3,...,n-1.$

Distanța rezistivă dintre un vârf și vârfuri este , unde este --lea număr Fibonacci, pentru [1] [2] . $n+1$ $i\in \{1,2,3,...,n\}$ ${\frac {F_{2(ni)+1}F_{2i-1}}{F_{2n)))$ $F_{j)$ $j$ $j\geqslant 0$

Vezi și

Graficul de conductivitate

Note

↑ Bapat, Gupta, 2010 , p. 1–13.
↑ Sursa . Preluat la 7 februarie 2019. Arhivat din original la 30 august 2021. (nedefinit)

Literatură

Bapat RB, Somit Gupta. Distanța de rezistență în roți și ventilatoare // 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. Chim.. - 1993. - T. 12 . — S. 81–95 . - doi : 10.1007/BF01164627 .
Ivan Gutman, Bojan Mohar. Indicii cvasi-Wiener și Kirchhoff coincid // J. Chem. inf. Calculator. Sci .. - 1996. - T. 36 . — S. 982–985 . doi : 10.1021 / ci960007t .
Jose Luis Palacios. Formule în formă închisă pentru indicele Kirchhoff // 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 . Arhivat din original pe 26 martie 2012.
Ravindra B. Bapat, Ivan Gutman, Wenjun Xiao. O metodă simplă de calcul a distanței de rezistență // Z. Naturforsch .. - 2003. - T. 58a . — S. 494–498 . - doi : 10.1515/zna-2003-9-1003 . - Cod .
Jose Luis Placios. Formulele lui Foster prin probabilitate și indicele Kirchhoff // Metoda. Calculator. Appl. Probabil.. - 2004. - T. 6 . — S. 381–387 . - doi : 10.1023/B:MCAP.0000045086.76839.54 .
Enrique Bendito, Angeles Carmona, Andres M. Encinas, Jose M. Gesto. O formulă pentru indicele Kirchhoff // Int. J. Quantum Chem.. - 2008. - T. 108 . - S. 1200-1206 . - doi : 10.1002/qua.21588 . — Cod .
Bo Zhou, Nenad Trinajstic. Indicele Kirchhoff și numărul de potrivire // Int. J. Quantum Chem.. - 2009. - V. 109 , nr. 13 . — S. 2978–2981 . - doi : 10.1002/qua.21915 . - Cod .
Bo Zhou, Nenad Trinajstic. Despre rezistență-distanță și indicele Kirchhoff // J. Math. Chim.. - 2009. - T. 46 . — S. 283–289 . - doi : 10.1007/s10910-008-9459-3 .
Bo Zhou. Pe suma puterilor valorilor proprii laplaciene și indicelui graficelor Laplacian Estrada // Match Commun. Matematică. Calculator. Chim. - 2011. - T. 62 . — S. 611–619 . - arXiv : 1102.1144 .

Heping Zhang, Yujun Yang. Distanța de rezistență și indicele Kirchhoff în grafice circulante // Int. J. Quantum Chem.. - 2007. - V. 107 , nr. 2 . — S. 330–339 . - doi : 10.1002/qua.21068 . — Cod .
Yujun Yang, Heping Zhang. Câteva reguli privind distanța de rezistență cu aplicații // J. Phys. A: Matematică. Theor .. - 2008. - T. 41 , nr. 44 . - S. 445203 . - doi : 10.1088/1751-8113/41/44/445203 . - Cod biblic .