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

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

Определение

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

,

где Γобратная матрица Мура–Пенроуза матрицы Кирхгофа графа 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. — .
  • 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. — .
  • 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. — .
  • 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. 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. doi:10.1088/1751-8113/41/44/445203. — .
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.