WikiDer > Расстояние сопротивления

Resistance distance

В теория графов, то расстояние сопротивления между двумя вершины из простой связный граф, г, равно сопротивление между двумя эквивалентными точками на электрическая сеть, построенные так, чтобы соответствовать г, с каждым край заменяется 1 ом сопротивление. Это метрика на графики.

Определение

На график г, то расстояние сопротивления Ωя,j между двумя вершинами vя и vj является[1]

где , с участием обозначая Обратное преобразование Мура – ​​Пенроуза, то Матрица лапласа из г, это количество вершин в г, и это матрица, содержащая все единицы.

Свойства сопротивления расстояние

Если я = j тогда

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

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

Для любого N-вертекс простой связный граф г = (VE) и произвольные N×N матрица M:

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

где ненулевые собственные значения из Матрица лапласа. Эта неупорядоченная сумма Σя Ωя, j называется индексом Кирхгофа графа.

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

Для простого связного графа г = (VE), расстояние сопротивления между двумя вершинами можно выразить как функция из набор из остовные деревья, Т, из г следующим образом:

где множество остовных деревьев для графа .

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

Поскольку лапласиан симметрична и положительно полуопределена, как и , таким образом, его псевдообратный также является симметричным и положительно полуопределенным. Таким образом, существует такой, что и мы можем написать:

показывая, что квадратный корень из расстояния сопротивления соответствует Евклидово расстояние в пространстве, охваченном .

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

Веерный граф - это граф на вершины, между вершинами которых есть ребро и для всех и между вершиной есть ребро и для всех

Расстояние сопротивления между вершинами и вершина является где это -е число Фибоначчи, для .[2][3]

Смотрите также

использованная литература

  1. ^ https://mathworld.wolfram.com/ResistanceDistance.html
  2. ^ Bapat, R. B .; Гупта, Сомит (2010). «Расстояние сопротивления в колесах и вентиляторах». Индийский журнал чистой и прикладной математики. 41: 1–13. CiteSeerX 10.1.1.418.7626. Дои:10.1007 / s13226-010-0004-2.
  3. ^ http://www.isid.ac.in/~rbb/somitnew.pdf
  • Чжан, Хэпин; Ян, Yujun (2007). «Расстояние сопротивления и индекс Кирхгофа в циркулянтных графах». Int. J. Quantum Chem.. 107 (2): 330–339. Bibcode:2007IJQC..107..330Z. Дои:10.1002 / qua.21068.