www.wikidata.uk-ua.nina.az

Резистивна відстань Резисти вна ві дстань між двома вершинами простого зв язного графа G displaystyle G дорівнює опору м

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

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

Визначення ред.

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

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

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

Якщо , то

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також ред.

Примітки ред.

  1. Bapat, Gupta, 2010, с. 1–13.
  2. Источник. оригіналу за 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Rezisti vna vi dstan mizh dvoma vershinami prostogo zv yaznogo grafa G displaystyle G dorivnyuye oporu mizh dvoma ekvivalentnimi tochkami elektrichnogo kola pobudovanim zaminoyu kozhnogo rebra grafa na opir 1 Om rezistivni vidstani ye metrikoyu na grafah Zmist 1 Viznachennya 2 Vlastivosti rezistivnoyi vidstani 2 1 Zagalne pravilo sumi 2 2 Zv yazok z chislom kistyakovih derev grafa 2 3 Yak kvadrat evklidovoyi vidstani 2 4 Zv yazok iz chislami Fibonachchi 3 Div takozh 4 Primitki 5 LiteraturaViznachennya red Na grafi G displaystyle G nbsp rezistivna vidstan W i j displaystyle Omega i j nbsp mizh dvoma vershinami v i displaystyle v i nbsp i v j displaystyle v j nbsp dorivnyuye W i j G i i G j j G i j G j i displaystyle Omega i j Gamma i i Gamma j j Gamma i j Gamma j i nbsp de G displaystyle Gamma nbsp obernena matricya Mura Penrouza en matrici Kirhgofa grafa G displaystyle G nbsp Vlastivosti rezistivnoyi vidstani red Yaksho i j displaystyle i j nbsp to W i j 0 displaystyle Omega i j 0 nbsp Dlya neoriyentovanogo grafa W i j W j i G i i G j j 2 G i j displaystyle Omega i j Omega j i Gamma i i Gamma j j 2 Gamma i j nbsp Zagalne pravilo sumi red Dlya bud yakogo prostogo zv yaznogo grafa G V E displaystyle G V E nbsp z N displaystyle N nbsp vershinami ta dovilnoyu N N displaystyle N times N nbsp matrici M displaystyle M nbsp vikonuyetsya i j V L M L i j W i j 2 tr M L displaystyle sum i j in V LML i j Omega i j 2 operatorname tr ML nbsp Z cogo uzagalnenogo pravila sumi chislo zv yazku mozhna otrimati zalezhno vid viboru M displaystyle M nbsp Dva z nih i j E W i j N 1 i lt j V W i j N k 1 N 1 l k 1 displaystyle begin aligned sum i j in E Omega i j amp N 1 sum i lt j in V Omega i j amp N sum k 1 N 1 lambda k 1 end aligned nbsp de l k displaystyle lambda k nbsp nenulovi vlasni chisla matrici Kirhgofa Cyu sumu S i lt j W i j displaystyle Sigma i lt j Omega i j nbsp nazivayut indeksom Kirhgofa grafa Zv yazok z chislom kistyakovih derev grafa red Dlya prostogo zv yaznogo grafa G V E displaystyle G V E nbsp rezistivnu vidstan mizh dvoma vershinami mozhna viraziti yak funkciyu na mnozhini kistyakiv T displaystyle T nbsp grafa G displaystyle G nbsp W i j t t T e i j t T i j E T T T i j E displaystyle Omega i j begin cases frac left t t in T e i j in t right vert left T right vert amp i j in E frac left T T right vert left T right vert amp i j not in E end cases nbsp de T displaystyle T nbsp mnozhina kistyakovih derev grafa G V E e i j displaystyle G V E e i j nbsp Yak kvadrat evklidovoyi vidstani red Oskilki laplasian L displaystyle L nbsp simetrichnij i dodatno napivviznachenij jogo psevdoobernena matricya G displaystyle Gamma nbsp takozh simetrichna ta dodatno napivviznachena Todi isnuye K displaystyle K nbsp taka sho G K K T displaystyle Gamma KK textsf T nbsp i mozhna zapisati W i j G i i G j j G i j G j i K i K i T K j K j T K i K j T K j K i T K i K j 2 displaystyle 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 nbsp ce pokazuye sho kvadrat rezistivnoyi vidstani vidpovidaye evklidovij vidstani u prostori natyagnutomu na K displaystyle K nbsp Zv yazok iz chislami Fibonachchi red Viyalo ce graf z n 1 displaystyle n 1 nbsp vershinoyu v yakomu ye rebra mizh vershinami i displaystyle i nbsp ta n 1 displaystyle n 1 nbsp dlya bud yakogo i 1 2 3 n displaystyle i 1 2 3 n nbsp i ye rebro mizh vershinoyu i displaystyle i nbsp ta i 1 displaystyle i 1 nbsp dlya vsih i 1 2 3 n 1 displaystyle i 1 2 3 n 1 nbsp Rezistivna vidstan mizh vershinoyu n 1 displaystyle n 1 nbsp ta vershinami i 1 2 3 n displaystyle i in 1 2 3 n nbsp dorivnyuye F 2 n i 1 F 2 i 1 F 2 n displaystyle frac F 2 n i 1 F 2i 1 F 2n nbsp de F j displaystyle F j nbsp j displaystyle j nbsp e chislo Fibonachchi dlya j 0 displaystyle j geqslant 0 nbsp 1 2 Div takozh red Providnist grafaPrimitki red Bapat Gupta 2010 s 1 13 Istochnik Arhiv originalu za 30 serpnya 2021 Procitovano 7 lyutogo 2019 Literatura red Bapat R B Somit Gupta Resistance distance in wheels and fans Indian Journal of Pure and Applied Mathematics 2010 T 41 DOI 10 1007 s13226 010 0004 2 Klein D J Randic M J Resistance Distance J Math Chem 1993 T 12 S 81 95 DOI 10 1007 BF01164627 Ivan Gutman Bojan Mohar The quasi Wiener and the Kirchhoff indices coincide J Chem Inf Comput Sci 1996 T 36 vip 5 S 982 985 DOI 10 1021 ci960007t Jose Luis Palacios Closed form formulas for the Kirchhoff index Int J Quantum Chem 2001 T 81 vip 2 S 135 140 DOI 10 1002 1097 461X 2001 81 2 lt 135 AID QUA4 gt 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 T 90 S 166 167 DOI 10 1002 qua 10057 Klein D J Resistance Distance Sum Rules Croatica Chem Acta 2002 T 75 S 633 649 Arhivovano z dzherela 26 bereznya 2012 Ravindra B Bapat Ivan Gutman Wenjun Xiao A simple method for computing resistance distance Z Naturforsch 2003 T 58a vip 9 10 S 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 T 6 S 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 T 108 S 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 T 109 vip 13 S 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 T 46 S 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 T 62 S 611 619 arXiv 1102 1144 Heping Zhang Yujun Yang Resistance distance and Kirchhoff index in circulant graphs Int J Quantum Chem 2007 T 107 vip 2 S 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 T 41 vip 44 S 445203 Bibcode 2008JPhA 41R5203Y DOI 10 1088 1751 8113 41 44 445203 Otrimano z https uk wikipedia org w index php title Rezistivna vidstan amp oldid 36842078