Русская Википедия:Резистивное расстояние
Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.
Определение
На графе G резистивное расстояние Ωi,j между двумя вершинами vi и vj равно
- <math>
\Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i} </math>,
где Γ — Шаблон:Не переведено 5 матрицы Кирхгофа графа G.
Свойства резистивного расстояния
Если i=j то
- <math>\Omega_{i,j}=0.</math>
Для неориентированного графа
- <math>
\Omega_{i,j}=\Omega_{j,i}=\Gamma_{i,i}+\Gamma_{j,j}-2\Gamma_{i,j} </math>
Общее правило суммы
Для любого простого связного графа <math>G=(V, E)</math> с N вершинами и произвольной <math>N \times N</math> матрицы M выполняется
- <math>\sum_{i,j \in V}(LML)_{i,j}\Omega_{i,j}=-2\operatorname{tr}(ML)</math>
Из этого обобщённого правила суммы число связи может быть получено в зависимости от выбора M. Два из них
- <math>\begin{align}
\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{align}</math>
где <math>\lambda_{k}</math> — ненулевые собственные числа матрицы Кирхгофа. Эта сумма <math>\Sigma_{i<j}\Omega_{i,j}</math> называется индексом Кирхгофа графа.
Связь с числом остовных деревьев графа
Для простого связного графа <math>G'=(V, E)</math> резистивное расстояние между двумя вершинами может выражено как функция на множестве остовных деревьев T графа G:
- <math>
\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} </math>,
где <math>T'</math> — множество остовных деревьев графа <math>G'=(V, E+e_{i,j})</math>.
Как квадрат евклидова расстояния
Поскольку лапласиан <math>L</math> симметричен и положительно полуопределён, его псевдопобратная матрица <math>\Gamma</math> также симметрична и положительна полуопределена. Тогда существует <math>K</math>, такая, что <math>\Gamma=KK^\textsf{T}</math> и мы можем записать:
- <math>\Omega_{i,j}=\Gamma_{i,i} + \Gamma_{j,j} - \Gamma_{i,j} - \Gamma_{j,i}=K_iK_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</math>
это показывает, что квадрат резистивного расстояния соответствует евклидовому расстоянию в пространстве, натянутому на <math>K</math>.
Связь с числами Фибоначчи
Веер — это граф с <math>n+1</math> вершинами, в котором есть рёбра между вершинами <math>i</math> и <math>n+1</math> для любого <math>i=1, 2, 3, ...n,</math> и есть ребро между вершиной <math>i</math> и <math>i+1</math> для всех <math>i=1, 2, 3, ..., n-1.</math>
Резистивное расстояние между вершиной <math>n + 1</math> и вершинами <math> i \in \{1,2,3,...,n\}</math> равно <math>\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} }</math>, где <math>F_{j}</math> — <math>j</math>-ое число Фибоначчи, для <math>j \geqslant 0</math>Шаблон:Sfn[1].
См. также
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
