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

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

Визначення

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

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

де $\Gamma$ — обернена матриця Мура — Пенроуза матриці Кірхгофа графа $G$.

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

Якщо $i=j$, то

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оскільки лапласіан $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}$

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

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

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

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

Див. також

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

Література

• 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.