Резистивное расстояние

Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.

Определение

На графе G резистивное расстояние Ω_i,j между двумя вершинами v_i и v_j равно

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

где Γ — обратная матрица Мура–Пенроуза^[англ.] матрицы Кирхгофа графа G.

Свойства резистивного расстояния

Если i=j то

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

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

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

Общее правило суммы

Для любого простого связного графа ${\displaystyle G=(V,E)}$ с N вершинами и произвольной ${\displaystyle N\times N}$ матрицы M выполняется

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

Из этого обобщённого правила суммы число связи может быть получено в зависимости от выбора M. Два из них

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

где ${\displaystyle \lambda _{k}}$ — ненулевые собственные числа матрицы Кирхгофа. Эта сумма ${\displaystyle \Sigma _{i<j}\Omega _{i,j}}$ называется индексом Кирхгофа графа.

Связь с числом остовных деревьев графа

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

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

где ${\displaystyle T'}$ — множество остовных деревьев графа ${\displaystyle G'=(V,E+e_{i,j})}$.

Как квадрат евклидова расстояния

Поскольку лапласиан ${\displaystyle L}$ симметричен и положительно полуопределён, его псевдопобратная матрица ${\displaystyle \Gamma }$ также симметрична и положительна полуопределена. Тогда существует ${\displaystyle K}$, такая, что ${\displaystyle \Gamma =KK^{\textsf {T}}}$ и мы можем записать:

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

это показывает, что квадрат резистивного расстояния соответствует евклидовому расстоянию в пространстве, натянутому на ${\displaystyle K}$.

Связь с числами Фибоначчи

Веер — это граф с ${\displaystyle n+1}$ вершинами, в котором есть рёбра между вершинами ${\displaystyle i}$ и ${\displaystyle n+1}$ для любого ${\displaystyle i=1,2,3,...n,}$ и есть ребро между вершиной ${\displaystyle i}$ и ${\displaystyle i+1}$ для всех ${\displaystyle i=1,2,3,...,n-1.}$

Резистивное расстояние между вершиной ${\displaystyle n+1}$ и вершинами ${\displaystyle i\in \{1,2,3,...,n\}}$ равно ${\displaystyle {\frac {F_{2(n-i)+1}F_{2i-1}}{F_{2n}}}}$, где ${\displaystyle F_{j}}$ — ${\displaystyle j}$-ое число Фибоначчи, для ${\displaystyle j\geqslant 0}$^[1][2].

См. также

• Проводимость графа