Odległość oporu

W teorii grafów odległość rezystancji między dwoma wierzchołkami prostego , $połączonego$ grafu $G$ jest równa rezystancji między dwoma równoważnymi punktami sieci elektrycznej , skonstruowanej tak, aby odpowiadała G , przy czym każda krawędź jest zastąpiona rezystancją jeden om . Jest to metryka na wykresach .

Definicja

Na wykresie $G$ odległość rezystancji Ω $i, j między$ dwoma $j wierzchołkami$ $vi i$ v wynosi

{\ Displaystyle \ Omega _ {i, j}: = \ Gamma _ {i, i} + \ Gamma _ {j, j} - \ Gamma _ {i, j} - \ Gamma _ {j, i},} gdzie Γ

=

Displaystyle \ Gamma = \ lewo (L + {\frac {1}{|V|}}\Phi \right)^{+},}

gdzie $+$ oznacza $odwrotność$ Moore'a-Penrose'a , $L$ macierz Laplace'a G , $| V |$ to liczba wierzchołków w $G$ , a $Φ$ to $| V | \times | V |$ macierz zawierająca wszystkie 1s.

Własności odległości rezystancyjnej

Jeśli $ja = j$ to $Ω ja, j = 0$ . Dla grafów nieskierowanych

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

Ogólna zasada sumy

Dla dowolnego $N$ -wierzchołkowego prostego spójnego grafu $G = (V, E)$ i dowolnej macierzy $N \times N$ $M$ :

{\ Displaystyle \ suma _ {i, j \ w V} (LML) _ {i, j} \Omega _{i,j}=-2\nazwa operatora {tr} (ML)}

Z tej uogólnionej reguły sumy można wyprowadzić szereg zależności w zależności od wyboru $M$ . Dwa warte uwagi to;

{\ Displaystyle {\ rozpocząć {wyrównane} \ suma _{(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{wyrównane}}}

gdzie $λ k$ są niezerowymi wartościami własnymi macierzy Laplace'a . Ta nieuporządkowana suma

{\ Displaystyle \ suma _ {i <j} \ Omega _ {i, j}}

nazywa się indeksem Kirchhoffa wykresu.

Związek z liczbą drzew rozpinających grafu

Dla prostego spójnego grafu $G = (V, E)$ odległość rezystancji między dwoma wierzchołkami można wyrazić jako funkcję zbioru drzew rozpinających , T $,$ z $G$ w następujący sposób :

{\ Displaystyle \ Omega _ {i, j} = {\ rozpocząć {przypadki} {\ Frac {\ lewo|\ {t: t \ w T, e_ {i, j} \ w t \} \ prawo \ vert} {\left|T\right\vert }},&(i,j)\in E\\{\frac {\left|T'-T\right\vert }{\left|T\right\vert }} ,&(i,j)\nie \in E\end{przypadki}}}

gdzie $T'$ jest zbiorem drzew rozpinających dla grafu $G' = (V, E + e i, j)$ .

Jako kwadrat odległości euklidesowej

Ponieważ Laplace'owskie $L$ jest symetryczne i dodatnio półokreślone, tak też jest

{\ Displaystyle \ lewo (L + {\ Frac {1} {| V |}} \ Phi \ po prawej)}

zatem jego pseudo-odwrotność $Γ$ jest również symetryczna i dodatnio półokreślona. Zatem istnieje $K$ takie, że możemy napisać: ${\ Displaystyle \ Gamma = KK ^ {\ textsf {T}}}$

{\ Displaystyle \ Omega _ {i, j} = \ Gamma _ {i, i} + \ Gamma _ {j, j} - \ Gamma _ {i, j} - \ Gamma _ {j, i }=K_{i}K_{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}}

pokazując, że pierwiastek kwadratowy odległości rezystancji odpowiada odległości euklidesowej w przestrzeni rozpiętej przez $K$ .

Połączenie z liczbami Fibonacciego

Graf wachlarzowy to graf złożony z $n + 1$ wierzchołków, w którym istnieje krawędź między wierzchołkami $i$ a $n + 1$ dla wszystkich $i = 1, 2, 3, \dots, n$ , oraz krawędź między wierzchołkami $i$ i $i + 1$ dla wszystko $ja = 1, 2, 3, \dots, n - 1$ .

Odległość oporu między wierzchołkiem $n + 1$ a wierzchołkiem $i \in {1, 2, 3, \dots, n}$ wynosi

{\ Displaystyle {\ Frac {F_ {2 (ni) + 1} F_ {2i-1}} {F_ {2n}}}}

gdzie $Fj Fibonacciego$ jest $j -tą liczbą$ , dla $j \geq 0$ .

Zobacz też

Przewodnictwo (wykres)

Klein, DJ; Randic, MJ (1993). „Odległość oporu”. J. Matematyka. chemia . 12 : 81–95. doi : 10.1007/BF01164627 . S2CID 16382100 .
Gutman, Iwan; Mohar, Bojan (1996). „Indeksy quasi-Wienera i Kirchhoffa pokrywają się”. J. Chem. Inf. Oblicz. nauka . 36 (5): 982–985. doi : 10.1021/ci960007t .
Palacios, Jose Luis (2001). „Wzory w postaci zamkniętej dla indeksu Kirchhoffa”. Int. J. Quantum Chem . 81 (2): 135–140. doi : 10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G .
Babić, D.; Klein, DJ; Lukovits, I.; Nikolić, S.; Trinajstic, N. (2002). „Macierz rezystancji i odległości: algorytm obliczeniowy i jego zastosowanie”. Int. J. Quantum Chem . 90 (1): 166–167. doi : 10.1002/qua.10057 .
Klein, DJ (2002). „Zasady sumy odległości oporu” (PDF) . Croatica Chem. Akta . 75 (2): 633–649. Zarchiwizowane od oryginału (PDF) w dniu 2012-03-26.
Bapat, Ravindra B.; Gutman, Iwan; Xiao, Wenjun (2003). „Prosta metoda obliczania odległości rezystancji” . Z. Naturforsch . 58a (9–10): 494–498. Bibcode : 2003ZNatA..58..494B . doi : 10.1515/zna-2003-9-1003 .
Placios, Jose Luis (2004). „Wzory Fostera na podstawie prawdopodobieństwa i indeksu Kirchhoffa”. Metoda. Oblicz. Aplikacja Prawdopodobne . 6 (4): 381–387. doi : 10.1023/B:MCAP.0000045086.76839.54 . S2CID 120309331 .
Bendito, Enrique; Carmona, Angeles; Encinas, Andres M.; Gesto, Jose M. (2008). „Wzór na indeks Kirchhoffa”. Int. J. Quantum Chem . 108 (6): 1200-1206. Bibcode : 2008IJQC..108.1200B . doi : 10.1002/qua.21588 .
Zhou, Bo; Trinajstic, Nenad (2009). „Indeks Kirchhoffa i pasujący numer”. Int. J. Quantum Chem . 109 (13): 2978–2981. Bibcode : 2009IJQC..109.2978Z . doi : 10.1002/qua.21915 .
Zhou, Bo; Trinajstic, Nenad (2009). „O odległości oporu i indeksie Kirchhoffa”. J. Matematyka. chemia . 46 : 283–289. doi : 10.1007/s10910-008-9459-3 . hdl : 10338.dmlcz/140814 . S2CID 119389248 .
Zhou, Bo (2011). „O sumie potęg Laplacianowych wartości własnych i Laplacian Estrada Index grafów”. Dopasuj komunię. Matematyka Oblicz. chemia . 62 : 611–619. ar Xiv : 1102.1144 .

Zhang, Heping; Yang, Yujun (2007). „Odległość rezystancji i indeks Kirchhoffa na wykresach krążących”. Int. J. Quantum Chem . 107 (2): 330–339. Bibcode : 2007IJQC..107..330Z . doi : 10.1002/qua.21068 .

Yang, Yujun; Zhang, Heping (2008). „Niektóre zasady dotyczące odległości rezystancji z aplikacjami”. J. Fiz. O: Matematyka. teoria . 41 (44): 445203. Bibcode : 2008JPhA...41R5203Y . doi : 10.1088/1751-8113/41/44/445203 .