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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Визначення

[ред. | ред. код]

На графі резистивна відстань між двома вершинами і дорівнює

,

де  — обернена матриця Мура — Пенроуза[en] матриці Кірхгофа графа .

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

[ред. | ред. код]

Якщо , то

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

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

[ред. | ред. код]

Для будь-якого простого зв'язного графа з вершинами та довільною матриці виконується

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

де  — ненульові власні числа матриці Кірхгофа. Цю суму називають індексом Кірхгофа графа.

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

[ред. | ред. код]

Для простого зв'язного графа резистивну відстань між двома вершинами можна виразити як функцію на множині кістяків графа :

,

де  — множина кістякових дерев графа .

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

[ред. | ред. код]

Оскільки лапласіан симетричний і додатно напіввизначений, його псевдообернена матриця також симетрична та додатно напіввизначена. Тоді існує , така, що і можна записати:

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

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

[ред. | ред. код]

Віяло — це граф з вершиною, в якому є ребра між вершинами та для будь-якого і є ребро між вершиною та для всіх

Резистивна відстань між вершиною та вершинами дорівнює , де  — -е число Фібоначчі, для [1][2].

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  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.