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

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

ОпределениеПравить

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

${\mathrm{\Omega <!--\; \Omega \; -->}}_{i,j}:={\mathrm{\Gamma <!--\; \Gamma \; -->}}_{i,i}+{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{j,j}-<!--\; -\; -->{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{i,j}-<!--\; -\; -->{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{j,i}$$\Omega _{i,j}:=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i}$ ,

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

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

Если i=j то

${\mathrm{\Omega <!--\; \Omega \; -->}}_{i,j}=0.$$\Omega _{i,j}=0.$ 

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

${\mathrm{\Omega <!--\; \Omega \; -->}}_{i,j}={\mathrm{\Omega <!--\; \Omega \; -->}}_{j,i}={\mathrm{\Gamma <!--\; \Gamma \; -->}}_{i,i}+{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{j,j}-<!--\; -\; -->2{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{i,j}$$\Omega _{i,j}=\Omega _{j,i}=\Gamma _{i,i}+\Gamma _{j,j}-2\Gamma _{i,j}$ 

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

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

$\underset{i,j\in <!--\; \in \; -->V}{\sum <!--\; \sum \; -->}(LML{)}_{i,j}{\mathrm{\Omega <!--\; \Omega \; -->}}_{i,j}=-<!--\; -\; -->2\mathrm{tr}<!--\; \; -->(ML)$$\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}}$ 

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

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

Для простого связного графа $G^{\prime }=(V,E)$$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^{\prime }$$T'$  — множество остовных деревьев графа $G^{\prime }=(V,E+e_{i,j})$$G'=(V,E+e_{i,j})$ .

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

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

${\mathrm{\Omega <!--\; \Omega \; -->}}_{i,j}={\mathrm{\Gamma <!--\; \Gamma \; -->}}_{i,i}+{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{j,j}-<!--\; -\; -->{\mathrm{\Gamma <!--\; \Gamma \; -->}}_{i,j}-<!--\; -\; -->{\mathrm{\Gamma <!--\; \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}}}={\left(K_i-<!--\; -\; -->K_j\right)}^2$$\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$$K$ .

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

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

Резистивное расстояние между вершиной $n+1$$n+1$  и вершинами $i\in <!--\; \in \; -->\{1,2,3,...,n\}$$i\in \{1,2,3,...,n\}$  равно $\frac{F_{2(n-<!--\; -\; -->i)+1}{F}_{2i-<!--\; -\; -->1}}{F_{2n}}$${\frac {F_{2(n-i)+1}F_{2i-1}}{F_{2n}}}$ , где $F_j$$F_{j}$  — $j$$j$ -ое число Фибоначчи, для $j⩾<!--\; ⩾\; -->0$$j\geqslant 0$ .

См. такжеПравить

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