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

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

Определение

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

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

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

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

Если i=j то

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

это показывает, что квадрат резистивного расстояния соответствует евклидовому расстоянию в пространстве, натянутому на $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\geqslant 0$.

См. также

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