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:

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

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

Tulajdonságok

Ha i = j, akkor

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

Irányítatlan gráf esetén

${\mathrm{\Omega }}_{i,j}={\mathrm{\Omega }}_{j,i}={\mathrm{\Gamma }}_{i,i}+{\mathrm{\Gamma }}_{j,j}-2{\mathrm{\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}{\mathrm{\Omega }}_{i,j}=-2\mathrm{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{array}{cc}\sum _{(i,j)\in E}{\mathrm{\Omega }}_{i,j}& =N-1\\ \sum _{i<j\in V}{\mathrm{\Omega }}_{i,j}& =N\sum _{k=1}^{N-1}{\lambda }_k^{-1}\end{array}$

ahol ${\lambda }_k$ a Laplace-mátrix nemnulla sajátértékeit jelenti. Ezt az Sablon:Math ö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:

${\mathrm{\Omega }}_{i,j}=\{\begin{array}{cc}\frac{|\{t:t\in T,e_{i,j}\in t\}|}{\left|T\right|},& (i,j)\in E\\ \frac{|T^{\prime }-T|}{\left|T\right|},& (i,j)\in ̸E\end{array}$

ahol $T^{\prime }$ a $G^{\prime }=(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, $\mathrm{\Gamma }$ szintén szimmetrikus és pozitív szemidefinit. Tehát létezik olyan $K$, melyre $\mathrm{\Gamma }=K{K}^{\mathsf{\text{T}}}$, így leírható:

${\mathrm{\Omega }}_{i,j}={\mathrm{\Gamma }}_{i,i}+{\mathrm{\Gamma }}_{j,j}-{\mathrm{\Gamma }}_{i,j}-{\mathrm{\Gamma }}_{j,i}=K_i{K}_i^{\mathsf{\text{T}}}+K_j{K}_j^{\mathsf{\text{T}}}-K_i{K}_j^{\mathsf{\text{T}}}-K_j{K}_i^{\mathsf{\text{T}}}={(K_i-K_j)}^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\ge 0$-ra.

Kapcsolódó szócikkek

• Konduktancia (gráfelmélet)

Fordítás

• Sablon:Fordítás

Jegyzetek

• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal

• Sablon:Cite journal

• Sablon:Cite journal