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:

$\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

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

Irányítatlan gráf esetén

$\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:

$\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:

${\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 $\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:

$\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 $T'$ a $G'=(V,E+e_{i,j})$ gráf feszítőfáinak halmaza.

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

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

$\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 $K$ által kifeszített térbeli euklideszi távolságnak.

Fibonacci-számokkal való kapcsolata

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

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

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

• (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.