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.