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

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

Определение

На графе G резистивное расстояние Ω_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}$,

где Γ — Шаблон:Не переведено 5 матрицы Кирхгофа графа 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.

См. также

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

Литература

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

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