Резистивна відстань

Резисти́вна ві́дстань між двома вершинами простого зв'язного графа ${\displaystyle G}$ дорівнює опору між двома еквівалентними точками електричного кола, побудованим заміною кожного ребра графа на опір 1 Ом. резистивні відстані є метрикою на графах.

Визначення

На графі ${\displaystyle G}$ резистивна відстань ${\displaystyle \Omega _{i,j}}$ між двома вершинами ${\displaystyle v_{i}}$ і ${\displaystyle v_{j}}$ дорівнює

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

де ${\displaystyle \Gamma }$ — ^[en] матриці Кірхгофа графа ${\displaystyle G}$.

Властивості резистивної відстані

Якщо ${\displaystyle i=j}$, то

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

Для неорієнтованого графа

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

Загальне правило суми

Для будь-якого простого зв'язного графа ${\displaystyle G=(V,E)}$ з ${\displaystyle N}$ вершинами та довільною ${\displaystyle N\times N}$ матриці ${\displaystyle M}$ виконується

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

З цього узагальненого правила суми число зв'язку можна отримати залежно від вибору ${\displaystyle M}$. Два з них

${\displaystyle {\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}}}$

де ${\displaystyle \lambda _{k}}$ — ненульові власні числа матриці Кірхгофа. Цю суму ${\displaystyle \Sigma _{i<j}\Omega _{i,j}}$ називають індексом Кірхгофа графа.

Зв'язок з числом кістякових дерев графа

Для простого зв'язного графа ${\displaystyle G'=(V,E)}$ резистивну відстань між двома вершинами можна виразити як функцію на множині кістяків ${\displaystyle T}$ графа ${\displaystyle G}$:

${\displaystyle \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}}}$ ,

де ${\displaystyle T'}$ — множина кістякових дерев графа ${\displaystyle G'=(V,E+e_{i,j})}$.

Як квадрат евклідової відстані

Оскільки лапласіан ${\displaystyle L}$ симетричний і додатно напіввизначений, його псевдообернена матриця ${\displaystyle \Gamma }$ також симетрична та додатно напіввизначена. Тоді існує ${\displaystyle K}$, така, що ${\displaystyle \Gamma =KK^{\textsf {T}}}$ і можна записати:

${\displaystyle \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}}$

це показує, що квадрат резистивної відстані відповідає евклідовій відстані у просторі, натягнутому на ${\displaystyle K}$.

Зв'язок із числами Фібоначчі

Віяло — це граф з ${\displaystyle n+1}$ вершиною, в якому є ребра між вершинами ${\displaystyle i}$ та ${\displaystyle n+1}$ для будь-якого ${\displaystyle i=1,2,3,...n,}$ і є ребро між вершиною ${\displaystyle i}$ та ${\displaystyle i+1}$ для всіх ${\displaystyle i=1,2,3,...,n-1.}$

Резистивна відстань між вершиною ${\displaystyle n+1}$ та вершинами ${\displaystyle i\in \{1,2,3,...,n\}}$ дорівнює ${\displaystyle {\frac {F_{2(n-i)+1}F_{2i-1}}{F_{2n}}}}$, де ${\displaystyle F_{j}}$ — ${\displaystyle j}$-е число Фібоначчі, для ${\displaystyle j\geqslant 0}$.

Див. також

• Провідність графа

Примітки

1. Bapat, Gupta, 2010, с. 1–13.
2. Источник (PDF). (PDF) оригіналу за 30 серпня 2021. Процитовано 7 лютого 2019.

Література

• Bapat R. B., Somit Gupta. Resistance distance in wheels and fans // Indian Journal of Pure and Applied Mathematics. — 2010. — Т. 41. — DOI:10.1007/s13226-010-0004-2.
• Klein D. J., Randic M. J. Resistance Distance // J. Math. Chem.. — 1993. — Т. 12. — С. 81–95. — DOI:10.1007/BF01164627.
• Ivan Gutman, Bojan Mohar. The quasi-Wiener and the Kirchhoff indices coincide // J. Chem. Inf. Comput. Sci.. — 1996. — Т. 36, вип. 5. — С. 982–985. — DOI:10.1021/ci960007t.
• Jose Luis Palacios. Closed-form formulas for the Kirchhoff index // Int. J. Quantum Chem.. — 2001. — Т. 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. Resistance-distance matrix: a computational algorithm and its application // Int. J. Quantum Chem.. — 2002. — Т. 90. — С. 166–167. — DOI:10.1002/qua.10057.
• Klein D. J. Resistance Distance Sum Rules // Croatica Chem. Acta. — 2002. — Т. 75. — С. 633–649. з джерела 26 березня 2012.
• Ravindra B. Bapat, Ivan Gutman, Wenjun Xiao. A simple method for computing resistance distance // Z. Naturforsch.. — 2003. — Т. 58a, вип. 9–10. — С. 494–498. — Bibcode:2003ZNatA..58..494B. — DOI:10.1515/zna-2003-9-1003.
• Jose Luis Placios. Foster's formulas via probability and the Kirchhoff index // Method. Comput. Appl. Probab.. — 2004. — Т. 6. — С. 381–387. — DOI:10.1023/B:MCAP.0000045086.76839.54.
• Enrique Bendito, Angeles Carmona, Andres M. Encinas, Jose M. Gesto. A formula for the Kirchhoff index // Int. J. Quantum Chem.. — 2008. — Т. 108. — С. 1200–1206. — Bibcode:2008IJQC..108.1200B. — DOI:10.1002/qua.21588.
• Bo Zhou, Nenad Trinajstic. The Kirchhoff index and the matching number // Int. J. Quantum Chem.. — 2009. — Т. 109, вип. 13. — С. 2978–2981. — Bibcode:2009IJQC..109.2978Z. — DOI:10.1002/qua.21915.
• Bo Zhou, Nenad Trinajstic. On resistance-distance and the Kirchhoff index // J. Math. Chem.. — 2009. — Т. 46. — С. 283–289. — DOI:10.1007/s10910-008-9459-3.
• Bo Zhou. On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs // Match Commun. Math. Comput. Chem. — 2011. — Т. 62. — С. 611–619. — arXiv:1102.1144.
• Heping Zhang, Yujun Yang. Resistance distance and Kirchhoff index in circulant graphs // Int. J. Quantum Chem.. — 2007. — Т. 107, вип. 2. — С. 330–339. — Bibcode:2007IJQC..107..330Z. — DOI:10.1002/qua.21068.
• Yujun Yang, Heping Zhang. Some rules on resistance distance with applications // J. Phys. A: Math. Theor.. — 2008. — Т. 41, вип. 44. — С. 445203. — Bibcode:2008JPhA...41R5203Y. — DOI:10.1088/1751-8113/41/44/445203.