Резистивное расстояние
Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.
Определение
На графе G резистивное расстояние Ωi,j между двумя вершинами vi и vj равно
- ,
где Γ — обратная матрица Мура–Пенроуза матрицы Кирхгофа графа G.
Свойства резистивного расстояния
Если i=j то
Для неориентированного графа
Общее правило суммы
Для любого простого связного графа с N вершинами и произвольной матрицы M выполняется
Из этого обобщённого правила суммы число связи может быть получено в зависимости от выбора M. Два из них
где — ненулевые собственные числа матрицы Кирхгофа. Эта сумма называется индексом Кирхгофа графа.
Связь с числом остовных деревьев графа
Для простого связного графа резистивное расстояние между двумя вершинами может выражено как функция на множестве остовных деревьев T графа G:
- ,
где — множество остовных деревьев графа .
Как квадрат евклидова расстояния
Поскольку лапласиан симметричен и положительно полуопределён, его псевдопобратная матрица также симметрична и положительна полуопределена. Тогда существует , такая, что и мы можем записать:
это показывает, что квадрат резистивного расстояния соответствует евклидовому расстоянию в пространстве, натянутому на .
См. также
Примечания
Литература
- 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. — .