Резистивное расстояние

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.

Определение[править | править код]

На графе G резистивное расстояние Ωi,j между двумя вершинами vi и vj равно

,

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

Свойства резистивного расстояния[править | править код]

Если i=j то

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

Общее правило суммы[править | править код]

Для любого простого связного графа с N вершинами и произвольной матрицы M выполняется

Из этого обобщённого правила суммы число связи может быть получено в зависимости от выбора M. Два из них

где — ненулевые собственные числа матрицы Кирхгофа. Эта сумма называется индексом Кирхгофа графа.

Связь с числом остовных деревьев графа[править | править код]

Для простого связного графа резистивное расстояние между двумя вершинами может выражено как функция на множестве остовных деревьев T графа G:

,

где — множество остовных деревьев графа .

Как квадрат евклидова расстояния[править | править код]

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

это показывает, что квадрат резистивного расстояния соответствует евклидовому расстоянию в пространстве, натянутому на .

Связь с числами Фибоначчи[править | править код]

Веер — это граф с вершинами, в котором есть рёбра между вершинами и для любого и есть ребро между вершиной и для всех

Резистивное расстояние между вершиной и вершинами равно , где -ое число Фибоначчи, для [1][2].

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

  • 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. — С. 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. — С. 494–498. — doi:10.1515/zna-2003-9-1003. — Bibcode2003ZNatA..58..494B.
  • 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. — doi:10.1002/qua.21588. — Bibcode2008IJQC..108.1200B.
  • Bo Zhou, Nenad Trinajstic. The Kirchhoff index and the matching number // Int. J. Quantum Chem.. — 2009. — Т. 109, вып. 13. — С. 2978–2981. — doi:10.1002/qua.21915. — Bibcode2009IJQC..109.2978Z.
  • 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.