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

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

Визначення

На графі $G$ резистивна відстань ${\mathrm{\Omega }}_{i,j}$ між двома вершинами $v_i$ і $v_j$ дорівнює

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

де $\mathrm{\Gamma }$ — Шаблон:Не перекладено матриці Кірхгофа графа $G$.

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

Якщо $i=j$, то

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

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

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

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

Для будь-якого простого зв'язного графа $G=(V,E)$ з $N$ вершинами та довільною $N\times N$ матриці $M$ виконується

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

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

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

де ${\lambda }_k$ — ненульові власні числа матриці Кірхгофа. Цю суму ${\mathrm{\Sigma }}_{i<j}{\mathrm{\Omega }}_{i,j}$ називають індексом Кірхгофа графа.

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

Для простого зв'язного графа $G^{\prime }=(V,E)$ резистивну відстань між двома вершинами можна виразити як функцію на множині кістяків $T$ графа $G$:

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

де $T^{\prime }$ — множина кістякових дерев графа $G^{\prime }=(V,E+e_{i,j})$.

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

Оскільки лапласіан $L$ симетричний і додатно напіввизначений, його псевдообернена матриця $\mathrm{\Gamma }$ також симетрична та додатно напіввизначена. Тоді існує $K$, така, що $\mathrm{\Gamma }=K{K}^{\mathsf{\text{T}}}$ і можна записати:

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

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

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

Віяло — це граф з $n+1$ вершиною, в якому є ребра між вершинами $i$ та $n+1$ для будь-якого $i=1,2,3,...n,$ і є ребро між вершиною $i$ та $i+1$ для всіх $i=1,2,3,...,n-1.$

Резистивна відстань між вершиною $n+1$ та вершинами $i\in \{1,2,3,...,n\}$ дорівнює $\frac{F_{2(n-i)+1}{F}_{2i-1}}{F_{2n}}$, де $F_j$ — $j$-е число Фібоначчі, для $j⩾0$Шаблон:Sfn.

Див. також

• Провідність графа

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття