Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.
Определение
На графе G резистивное расстояние Ωi,j между двумя вершинами vi и vj равно
,
где Γ — матрицы Кирхгофа графа G.
Свойства резистивного расстояния
Если i=j то
Для неориентированного графа
Общее правило суммы Для любого простого связного графа с N вершинами и произвольной матрицы M выполняется
Из этого обобщённого правила суммы число связи может быть получено в зависимости от выбора M. Два из них
где — ненулевые собственные числа матрицы Кирхгофа. Эта сумма называется индексом Кирхгофа графа.
Связь с числом остовных деревьев графа
Для простого связного графа резистивное расстояние между двумя вершинами может выражено как функция на множестве остовных деревьев T графа G:
,
где — множество остовных деревьев графа .
Как квадрат евклидова расстояния Поскольку лапласиан симметричен и положительно полуопределён, его псевдообратная матрица также симметрична и положительна полуопределена. Тогда существует , такая, что и мы можем записать:
это показывает, что квадрат резистивного расстояния соответствует евклидовому расстоянию в пространстве, натянутому на .
Связь с числами Фибоначчи Веер — это граф с вершинами, в котором есть рёбра между вершинами и для любого и есть ребро между вершиной и для всех
Резистивное расстояние между вершиной и вершинами равно , где — -ое число Фибоначчи, для .
См. также Проводимость графа
Примечания
Литература
Категория:Теория графов