Distancia resistiva

La distancia resistiva entre dos vértices de un gráfico conexo simple G es igual a la resistencia entre dos puntos equivalentes de un circuito eléctrico construido reemplazando cada borde del gráfico con una resistencia de 1 ohm . Las distancias resistivas son una métrica en los gráficos .

Definición

En el gráfico G , la distancia resistiva Ω i , j entre dos vértices v i y v j es

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

donde Γ es la matriz inversa de Moore-Penrose de la matriz de Kirchhoff del gráfico G .

Propiedades de la distancia resistiva

Si i = j entonces

{\ estilo de visualización \ Omega _ {i, j} = 0.}

Para un grafo no dirigido

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

La regla general de la suma

Para cualquier gráfico conexo simple con N vértices y una matriz arbitraria M , $G=(V,E)$ $N \veces N$

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

A partir de esta regla de suma generalizada, se puede obtener un número de conexión dependiendo de la elección de M . Dos de ellos

{\begin{alineado}\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{alineado}}

donde son valores propios distintos de cero de la matriz de Kirchhoff . Esta suma se llama el índice de Kirchhoff del gráfico. $\lambda _{{k}}$ ${\ estilo de visualización \ Sigma _ {i <j} \ Omega _ {i, j}}$

Relación con el número de árboles de expansión de un gráfico

Para un gráfico conexo simple, la distancia resistiva entre dos vértices se puede expresar como una función en el conjunto de árboles de expansión T del gráfico G : ${\ estilo de visualización G' = (V, E)}$

\Omega _{i,j}={\begin{casos}{\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)\no\en E\end{casos}}

donde es el conjunto de árboles de expansión del gráfico . $T'$ $G'=(V,E+e_{i,j})$

Como el cuadrado de la distancia euclidiana

Dado que el laplaciano es simétrico y semidefinido positivo, su matriz pseudoinversa también es simétrica y semidefinida positiva. Entonces existe tal que podemos escribir: $L$ $\Gama$ $k$ $\Gamma =KK^{\textsf {T}}$

\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}

esto muestra que el cuadrado de la distancia resistiva corresponde a la distancia euclidiana en el espacio atravesado por . $k$

Conexión con los números de Fibonacci

Un abanico es un grafo con vértices, en el que hay aristas entre los vértices y para cualquiera y hay una arista entre el vértice y para todos $n+1$ $i$ $n+1$ $i=1,2,3,...n,$ $i$ $yo+1$ ${\ estilo de visualización i = 1,2,3,...,n-1.}$

La distancia resistiva entre un vértice y los vértices es , donde es el -ésimo número de Fibonacci, para [1] [2] . $n+1$ ${\displaystyle i\en \{1,2,3,...,n\))$ ${\displaystyle {\frac{F_{2(ni)+1}F_{2i-1}}{F_{2n))))$ $F_{j}$ $j$ ${\ estilo de visualización j \ geqslant 0}$

Véase también

Gráfico de conductividad

Notas

↑ Bapat, Gupta, 2010 , pág. 1–13.
↑ Fuente . Consultado el 7 de febrero de 2019. Archivado desde el original el 30 de agosto de 2021. (indefinido)

Literatura

Bapat RB, Somit Gupta. Distancia de resistencia en ruedas y ventiladores // Indian Journal of Pure and Applied Mathematics. - 2010. - T. 41 . -doi : 10.1007/ s13226-010-0004-2 .
Klein DJ, Randic MJ Distancia de resistencia // J. Math. Química.. - 1993. - T. 12 . — S. 81–95 . -doi : 10.1007/ BF01164627 .
Iván Gutman, Bojan Mohar. Los índices cuasi-Wiener y Kirchhoff coinciden // J. Chem. inf. computar Sci.. - 1996. - T. 36 . — S. 982–985 . doi : 10.1021 / ci960007t .
José Luis Palacios. Fórmulas de forma cerrada para el índice de Kirchhoff // Int. J. Quantum Chem.. - 2001. - V. 81 , no. 2 . — S. 135–140 . -doi : 10.1002 / 1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G .
Babic D., Klein DJ, Lukovits I., Nikolic S., Trinajstic N. Matriz de resistencia-distancia: un algoritmo computacional y su aplicación // Int. J. Quantum Chem.. - 2002. - T. 90 . — S. 166–167 . -doi : 10.1002/ qua.10057 .
Reglas de suma de distancia de resistencia de Klein DJ // Croatica Chem. acta - 2002. - T. 75 . — S. 633–649 . Archivado desde el original el 26 de marzo de 2012.
Ravindra B. Bapat, Ivan Gutman, Wenjun Xiao. Un método simple para calcular la distancia de resistencia // Z. Naturforsch .. - 2003. - T. 58a . — S. 494–498 . -doi : 10.1515 / zna-2003-9-1003 . - .
José Luis Placios. Fórmulas de Foster vía probabilidad y el índice de Kirchhoff // Método. computar aplicación Probablemente.. - 2004. - T. 6 . — S. 381–387 . -doi : 10.1023/B : MCAP.0000045086.76839.54 .
Enrique Bendito, Ángeles Carmona, Andrés M. Encinas, José M. Gesto. Una fórmula para el índice de Kirchhoff // Int. J. Quantum Chem.. - 2008. - T. 108 . - S. 1200-1206 . -doi : 10.1002/ qua.21588 . — .
Bo Zhou, Nenad Trinajstic. El índice de Kirchhoff y el número coincidente // Int. J. Quantum Chem.. - 2009. - V. 109 , no. 13 _ — S. 2978–2981 . -doi : 10.1002/ qua.21915 . - .
Bo Zhou, Nenad Trinajstic. Sobre la resistencia-distancia y el índice de Kirchhoff // J. Math. Química.. - 2009. - T. 46 . — S. 283–289 . -doi : 10.1007/ s10910-008-9459-3 .
Bo Zhou. Sobre suma de potencias de autovalores laplacianos y laplacianos Estrada Índice de grafos // Match Commun. Matemáticas. computar química - 2011. - T. 62 . — S. 611–619 . -arXiv : 1102.1144 . _

Heping Zhang, Yujun Yang. Distancia de resistencia e índice de Kirchhoff en gráficos circulantes // Int. J. Quantum Chem.. - 2007. - V. 107 , no. 2 . — S. 330–339 . -doi : 10.1002/ qua.21068 . — .
Yujun Yang, Heping Zhang. Algunas reglas sobre distancia de resistencia con aplicaciones // J. Phys. R: Matemáticas. Teor.. - 2008. - T. 41 , núm. 44 . - S. 445203 . -doi : 10.1088 / 1751-8113/41/44/445203 . - .