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

редактировать

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

Содержание

1 Определение
2 Свойства расстояния сопротивления
- 2.1 Общее правило сумм
- 2.2 Связь с количеством остовных деревьев графа
- 2.3 В квадрате евклидова расстояния
- 2.4 Связь с числами Фибоначчи
3 См. Также
4 ссылки

Определение

На графике G, то расстояние сопротивления Ω я, J между двумя вершинами v I и v J является

{\ displaystyle \ Omega _ {i, j}: = \ Gamma _ {i, i} + \ Gamma _ {j, j} - \ Gamma _ {i, j} - \ Gamma _ {j, i}}

{\ displaystyle \ Omega _ {i, j}: = \ Gamma _ {i, i} + \ Gamma _ {j, j} - \ Gamma _ {i, j} - \ Gamma _ {j, i}}

где, с обозначающим обратную Мура-Пенроуз, в лапласовскую матрицу из G, является числом вершин в G, и является матрицей, содержащей все 1s. ${\ Displaystyle \ Gamma = \ left (L + {\ frac {1} {| V |}} \ Phi \ right) ^ {+}}$ ${\ Displaystyle \ Gamma = \ left (L + {\ frac {1} {| V |}} \ Phi \ right) ^ {+}}$ ${\ displaystyle ^ {+}}$ ${\ displaystyle ^ {+}}$ ${\ displaystyle L}$ $L$ ${\ displaystyle | V |}$ $| V |$ ${\ displaystyle \ Phi}$ $\ Phi$ ${\ Displaystyle | V | \ раз | V |}$ ${\ Displaystyle | V | \ раз | V |}$

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

Если i = j, то

{\ displaystyle \ Omega _ {i, j} = 0.}

{\ displaystyle \ Omega _ {i, j} = 0.}

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

{\ displaystyle \ Omega _ {i, j} = \ Omega _ {j, i} = \ Gamma _ {i, i} + \ Gamma _ {j, j} -2 \ Gamma _ {i, j}}

{\ displaystyle \ Omega _ {i, j} = \ Omega _ {j, i} = \ Gamma _ {i, i} + \ Gamma _ {j, j} -2 \ Gamma _ {i, j}}

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

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

{\ displaystyle \ sum _ {i, j \ in V} (LML) _ {i, j} \ Omega _ {i, j} = - 2 \ operatorname {tr} (ML)}

{\ displaystyle \ sum _ {i, j \ in V} (LML) _ {i, j} \ Omega _ {i, j} = - 2 \ operatorname {tr} (ML)}

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

{\ Displaystyle {\ begin {align} \ sum _ {(i, j) \ in E} \ Omega _ {i, j} amp; = N-1 \\\ сумма _ {я lt;j \ in V} \ Omega _ {i, j} amp; = N \ sum _ {k = 1} ^ {N-1} \ lambda _ {k} ^ {- 1} \ end {выровнено}}}

{\ Displaystyle {\ begin {align} \ sum _ {(i, j) \ in E} \ Omega _ {i, j} amp; = N-1 \\\ сумма _ {я lt;j \ in V} \ Omega _ {i, j} amp; = N \ sum _ {k = 1} ^ {N-1} \ lambda _ {k} ^ {- 1} \ end {выровнено}}}

где есть ненулевые собственные о лапласовского матрицы. Эта неупорядоченная сумма Σ i lt;j Ω i, j называется индексом Кирхгофа графа. ${\ displaystyle \ lambda _ {k}}$ $\ lambda _ {k}$

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

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

{\ displaystyle \ Omega _ {i, j} = {\ begin {case} {\ frac {\ left | \ {t: t \ in T, e_ {i, j} \ in t \} \ right \ vert} {\ left | T \ right \ vert}}, amp; (i, j) \ in E \\ {\ frac {\ left | T'-T \ right \ vert} {\ left | T \ right \ vert}}, amp; (i, j) \ not \ in E \ end {case}}}

\ Omega _ {{i, j}} = {\ begin {cases} {\ frac {\ left | \ {t: t \ in T, e _ {{i, j}} \ in t \} \ right \ vert } {\ left | T \ right \ vert}}, amp; (i, j) \ in E \\ {\ frac {\ left | T'-T \ right \ vert} {\ left | T \ right \ vert} }, amp; (i, j) \ not \ in E \ end {case}}

где - множество остовных деревьев графа. ${\ displaystyle T '}$ $Т '$ ${\ displaystyle G '= (V, E + e_ {i, j})}$ $G '= (V, E + e _ {{i, j}})$

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

Так как лапласиан симметричен и положительно полуопределен, значит, он симметричен и положительно полуопределен. Таким образом, есть такое, что и мы можем написать: ${\ displaystyle L}$ $L$ ${\ displaystyle \ left (L + {\ frac {1} {| V |}} \ Phi \ right)}$ ${\ displaystyle \ left (L + {\ frac {1} {| V |}} \ Phi \ right)}$ ${\ displaystyle \ Gamma}$ $\Гамма$ ${\ displaystyle K}$ $K$ ${\ Displaystyle \ Gamma = KK ^ {\textf {T}}}$ ${\ Displaystyle \ Gamma = KK ^ {\textf {T}}}$

{\ displaystyle \ Omega _ {i, j} = \ Gamma _ {i, i} + \ Gamma _ {j, j} - \ Gamma _ {i, j} - \ Gamma _ {j, i} = K_ { i} K_ {i} ^ {\textf {T}} + K_ {j} K_ {j} ^ {\textf {T}} - K_ {i} K_ {j} ^ {\textf {T}} - K_ {j} K_ {i} ^ {\textf {T}} = \ left (K_ {i} -K_ {j} \ right) ^ {2}}

{\ displaystyle \ Omega _ {i, j} = \ Gamma _ {i, i} + \ Gamma _ {j, j} - \ Gamma _ {i, j} - \ Gamma _ {j, i} = K_ { i} K_ {i} ^ {\textf {T}} + K_ {j} K_ {j} ^ {\textf {T}} - K_ {i} K_ {j} ^ {\textf {T}} - K_ {j} K_ {i} ^ {\textf {T}} = \ left (K_ {i} -K_ {j} \ right) ^ {2}}

показывая, что квадратный корень из расстояния сопротивления соответствует евклидову расстоянию в пространстве, охватываемом. ${\ displaystyle K}$ $K$

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

Веерный граф - это граф на вершинах, в котором есть ребро между вершиной и для всех, и есть ребро между вершиной и для всех. ${\ displaystyle n + 1}$ $п + 1$ ${\ displaystyle i}$ $я$ ${\ displaystyle n + 1}$ $п + 1$ ${\ Displaystyle я = 1,2,3,... п,}$ $я = 1, 2, 3,... п,$ ${\ displaystyle i}$ $я$ ${\ displaystyle i + 1}$ $я + 1$ ${\ displaystyle i = 1,2,3,..., n-1.}$ $я = 1, 2, 3,..., п-1.$

Расстояние между вершиной сопротивления и вершиной находится где это -м числом Фибоначчи, для. ${\ displaystyle n + 1}$ $п + 1$ ${\ Displaystyle я \ в \ {1,2,3,..., п \}}$ $i \ in \ {1,2,3,..., n \}$ ${\ displaystyle {\ frac {F_ {2 (ni) +1} F_ {2i-1}} {F_ {2n}}}}$ $\ frac {F_ {2 (ni) +1} F_ {2i-1}} {F_ {2n}}$ ${\ displaystyle F_ {j}}$ $F_ {j}$ ${\ displaystyle j}$ $j$ ${\ displaystyle j \ geq 0}$ $j \ geq 0$

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

Проводимость (график)

Рекомендации

Кляйн, диджей; Randic, MJ (1993). «Расстояние сопротивления». J. Math. Chem. 12 : 81–95. DOI : 10.1007 / BF01164627.
Гутман, Иван; Мохар, Боян (1996). «Квазивинеровские индексы и Кирхгофа совпадают». J. Chem. Инф. Comput. Sci. 36 (5): 982–985. DOI : 10.1021 / ci960007t.
Паласиос, Хосе Луис (2001). «Замкнутые формулы для индекса Кирхгофа». Int. J. Quantum Chem. 81 (2): 135–140. DOI : 10.1002 / 1097-461X (2001) 81: 2 lt;135:: АИД-QUA4gt; 3.0.CO; 2-Г.
Бабич, Д.; Кляйн, диджей; Луковиц, И.; Николич, С.; Тринайстич, Н. (2002). «Матрица сопротивления-расстояния: вычислительный алгоритм и его применение». Int. J. Quantum Chem. 90 (1): 166–167. DOI : 10.1002 / qua.10057.
Кляйн, DJ (2002). «Правила суммирования расстояний сопротивления» (PDF). Croatica Chem. Acta. 75 (2): 633–649. Архивировано из оригинального (PDF) 26 марта 2012 года.
Bapat, Ravindra B.; Гутман, Иван; Сяо, Вэньцзюнь (2003). «Простой метод вычисления расстояния сопротивления». Z. Naturforsch. 58а (9–10): 494–498. Bibcode : 2003ZNatA..58..494B. DOI : 10.1515 / зна-2003-9-1003.
Пласиос, Хосе Луис (2004). «Формулы Фостера через вероятность и индекс Кирхгофа». Метод. Comput. Appl. Вероятно. 6 (4): 381–387. DOI : 10,1023 / Б: MCAP.0000045086.76839.54.
Бендито, Энрике; Кармона, Анхелес; Энсинас, Андрес М.; Гесто, Хосе М. (2008). «Формула индекса Кирхгофа». Int. J. Quantum Chem. 108 (6): 1200–1206. Bibcode : 2008IJQC..108.1200B. DOI : 10.1002 / qua.21588.
Чжоу, Бо; Тринайстич, Ненад (2009). «Индекс Кирхгофа и совпадающее число». Int. J. Quantum Chem. 109 (13): 2978–2981. Bibcode : 2009IJQC..109.2978Z. DOI : 10.1002 / qua.21915.
Чжоу, Бо; Тринайстич, Ненад (2009). «О дистанции сопротивления и индексе Кирхгофа». J. Math. Chem. 46 : 283–289. DOI : 10.1007 / s10910-008-9459-3. hdl : 10338.dmlcz / 140814.
Чжоу, Бо (2011). «О сумме степеней собственных значений лапласиана и индекса Эстрады графов». Матч Комм. Математика. Comput. Chem. 62 : 611–619. arXiv : 1102.1144.

Чжан, Хэпин; Ян, Yujun (2007). «Расстояние сопротивления и индекс Кирхгофа в циркулянтных графах». Int. J. Quantum Chem. 107 (2): 330–339. Bibcode : 2007IJQC..107..330Z. DOI : 10.1002 / qua.21068.

Ян, Юйцзюнь; Чжан, Хэпин (2008). «Некоторые правила по дистанции сопротивления с приложениями». J. Phys. A: Математика. Теор. 41 (44): 445203. Bibcode : 2008JPhA... 41R5203Y. DOI : 10.1088 / 1751-8113 / 41/44/445203.