Ellenállás-távolság

A matematika, azon belül a gráfelmélet területén egy G összefüggő egyszerű gráf két csúcsa közötti ellenállás-távolság (resistance distance) értéke megegyezik a két csúcsnak megfelelő két pont közötti elektromos ellenállással, abban az elektromos hálózatban, mely a G gráfból állítható elő az élek 1 ohmos ellenállásra való cseréjével. Az ellenállás-távolság a gráfokon értelmezett metrika.

Definíció

G gráf v_i és v_j csúcsai közötti Ω_i,j ellenállás-távolság értéke:

${\displaystyle \Omega _{i,j}:=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i},}$

ahol Γ a G Laplace-mátrixának Moore–Penrose-inverze.

Tulajdonságok

Ha i = j, akkor

${\displaystyle \Omega _{i,j}=0.}$

Irányítatlan gráf esetén

${\displaystyle \Omega _{i,j}=\Omega _{j,i}=\Gamma _{i,i}+\Gamma _{j,j}-2\Gamma _{i,j}.}$

Általános összegzési szabály

Bármely N-csúcsú, G = (V, E) összefüggő egyszerű gráf és tetszőleges N×N méretű M mátrix esetében:

${\displaystyle \sum _{i,j\in V}(LML)_{i,j}\Omega _{i,j}=-2\operatorname {tr} (ML).}$

Ebből az általánosított összegzési szabályból több összefüggés levezethető M megválasztásától függően. Két figyelmet érdemlő közülük:

${\displaystyle {\begin{aligned}\sum _{(i,j)\in E}\Omega _{i,j}&=N-1\\\sum _{i<j\in V}\Omega _{i,j}&=N\sum _{k=1}^{N-1}\lambda _{k}^{-1}\end{aligned}}}$

ahol ${\displaystyle \lambda _{k}}$ a Laplace-mátrix nemnulla sajátértékeit jelenti. Ezt az Σ_i<jΩ_i,j összeget nevezik a gráf Kirchhoff-indexének.

Kapcsolat a gráf feszítőfáinak számával

A G = (V, E) egyszerű összefüggő gráfban két csúcs ellenállás-távolsága kifejezhető T feszítőfái halmazának függvényeként, a következőképpen:

${\displaystyle \Omega _{i,j}={\begin{cases}{\frac {\left|\{t:t\in T,e_{i,j}\in t\}\right\vert }{\left|T\right\vert }},&(i,j)\in E\\{\frac {\left|T'-T\right\vert }{\left|T\right\vert }},&(i,j)\not \in E\end{cases}}}$

ahol ${\displaystyle T'}$ a ${\displaystyle G'=(V,E+e_{i,j})}$ gráf feszítőfáinak halmaza.

Az euklideszi távolság négyzeteként

Mivel az ${\displaystyle L}$ Laplace-mátrix szimmetrikus és pozitív szemidefinit, pszeudoinverze, ${\displaystyle \Gamma }$ szintén szimmetrikus és pozitív szemidefinit. Tehát létezik olyan ${\displaystyle K}$, melyre ${\displaystyle \Gamma =KK^{\textsf {T}}}$, így leírható:

${\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},}$

ami megmutatja, hogy az ellenállás-távolság négyzetgyöke megfelel a ${\displaystyle K}$ által kifeszített térbeli euklideszi távolságnak.

Fibonacci-számokkal való kapcsolata

Egy legyezőgráf olyan, ${\displaystyle n+1}$ csúcsú gráf, melyben az ${\displaystyle i}$ csúcs és az ${\displaystyle n+1}$ csúcs között él húzódik minden ${\displaystyle i=1,2,3,...n,}$ értékre, továbbá az ${\displaystyle i}$ és ${\displaystyle i+1}$ csúcs között minden ${\displaystyle i=1,2,3,...,n-1}$ értékekre.

Az ${\displaystyle n+1}$ csúcs és ${\displaystyle i\in \{1,2,3,...,n\}}$ csúcs közötti ellenállás-távolság éppen ${\displaystyle {\frac {F_{2(n-i)+1}F_{2i-1}}{F_{2n}}}}$, ahol ${\displaystyle F_{j}}$ a ${\displaystyle j}$-edik Fibonacci-szám ${\displaystyle j\geq 0}$-ra.^[1][2]

Kapcsolódó szócikkek

• Konduktancia (gráfelmélet)

Fordítás

• Ez a szócikk részben vagy egészben a Resistance distance című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. (2010) „Resistance distance in wheels and fans”. Indian Journal of Pure and Applied Mathematics 41, 1–13. o. DOI:10.1007/s13226-010-0004-2. 
2. http://www.isid.ac.in/~rbb/somitnew.pdf

• (1993) „Resistance Distance”. J. Math. Chem. 12, 81–95. o. DOI:10.1007/BF01164627. 
• (1996) „The quasi-Wiener and the Kirchhoff indices coincide”. J. Chem. Inf. Comput. Sci. 36 (5), 982–985. o. DOI:10.1021/ci960007t. 
• (2001) „Closed-form formulas for the Kirchhoff index”. Int. J. Quant. Chem. 81 (2), 135–140. o. DOI:<135::AID-QUA4>3.0.CO;2-G 10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G. 
• (2002) „Resistance-distance matrix: a computational algorithm and its application”. Int. J. Quant. Chem. 90, 166–167. o. DOI:10.1002/qua.10057. 
• (2002) „Resistance Distance Sum Rules”. Croatica Chem. Acta 75, 633–649. o. [2012. március 26-i dátummal az eredetiből archiválva]. 
• (2003) „A simple method for computing resistance distance”. Z. Naturforsch. 58a (9–10), 494–498. o. DOI:10.1515/zna-2003-9-1003. 
• (2004) „Foster's formulas via probability and the Kirchhoff index”. Method. Comput. Appl. Probab. 6, 381–387. o. DOI:10.1023/B:MCAP.0000045086.76839.54. 
• (2008) „A formula for the Kirchhoff index”. Int. J. Quant. Chem. 108, 1200–1206. o. DOI:10.1002/qua.21588. 
• (2009) „The Kirchhoff index and the matching number”. Int. J. Quant. Chem. 109 (13), 2978–2981. o. DOI:10.1002/qua.21915. 
• (2009) „On resistance-distance and the Kirchhoff index”. J. Math. Chem. 46, 283–289. o. DOI:10.1007/s10910-008-9459-3. 
• (2011) „On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs”. Match Commun. Math. Comput. Chem 62, 611–619. o. 

• (2007) „Resistance distance and Kirchhoff index in circulant graphs”. Int. J. Quantum Chem. 107 (2), 330–339. o. DOI:10.1002/qua.21068. 

• (2008) „Some rules on resistance distance with applications”. J. Phys. A: Math. Theor. 41 (44), 445203. o. DOI:10.1088/1751-8113/41/44/445203.