Distancia de resistencia

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Lítrico de resistencia eléctrica entre nodos

En teoría de grafos, la distancia de resistencia entre dos vértices de un gráfico simple y conectado, $G$ , es igual a la resistencia entre dos puntos equivalentes en una red eléctrica, construida de manera que corresponda a $G$ , con cada borde siendo reemplazado por una resistencia de un ohmio. Es una métrica en gráficos.

Definición

En un gráfico $G$ , la distancia de resistencia $Ω 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

{displaystyle Gamma =left(L+{frac {1}{|V|}}Phi right)^{+},}

con $+$ denota la inversa de Moore-Penrose, $L$ la matriz laplaciana de $G$ , $| V |$ es el número de vértices en $G$ , y $Φ$ es el estilo $| V | \times | V |$ matriz que contiene todos los unos.

Propiedades de distancia de resistencia

Si $i = j$ entonces $Ω i, j = 0$ . Para un gráfico no dirigido

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

Regla general de suma

Para cualquier $N$ - gráficos simples conectados $G = V, E)$ y arbitrarias $N \times N$ matriz $M$ :

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

A partir de esta regla de suma generalizada se pueden derivar una serie de relaciones dependiendo de la elección de $M$ . Dos dignos de mención son;

<math alttext="{displaystyle {begin{aligned}sum _{(i,j)in E}Omega _{i,j}&=N-1\sum _{i. . ()i,j)▪ ▪ EΩ Ω i,j=N− − 1. . ic)j▪ ▪ VΩ Ω i,j=N. . k=1N− − 1λ λ k− − 1{displaystyle {begin{aligned}sum _{(i,j)in E}Omega _{i,j} simultáneamente=N-1\\sum _{i:0in V} Omega... ################################################################################################################################################################################################################################################################ ¿Qué?<img alt="{displaystyle {begin{aligned}sum _{(i,j)in E}Omega _{i,j}&=N-1\sum _{i

Donde $λ k$ son los valores no cero de la matriz laplaciana. Esta suma no ordenada

<math alttext="{displaystyle sum _{i. . ic)jΩ Ω i,j{displaystyle sum _{iיj}Omega _{i,j}<img alt="{displaystyle sum _{i

se llama índice de Kirchhoff del gráfico.

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

Para un gráfico conexo simple $G = (V, E)$ , el La distancia de resistencia entre dos vértices se puede expresar como una función del conjunto de árboles de expansión, $T$ , de $G$ de la siguiente manera:

{displaystyle Omega _{i,j}={begin{cases}{frac {left|{t:tin T,,e_{i,j}in t}rightvert }{left|Trightvert }},&(i,j)in E\{frac {left|T'-Trightvert }{left|Trightvert }},&(i,j)not in Eend{cases}}}

Donde $T '$ es el conjunto de árboles de azotes para el gráfico $G ' = V, E + e i, j)$ . En otras palabras, para un borde ${displaystyle (i,j)in E}$ , la distancia de resistencia entre un par de nodos ${displaystyle i}$ y ${displaystyle j}$ es la probabilidad de que el borde ${displaystyle (i,j)}$ está en un árbol de azotes al azar ${displaystyle G}$ .

Relación con los paseos aleatorios

La distancia de resistencia entre vértices ${displaystyle u}$ y ${displaystyle u}$ es proporcional al Tiempo de conmutación ${displaystyle C_{u,v}}$ de un paseo al azar entre ${displaystyle u}$ y ${displaystyle v}$ . El tiempo de conmutación es el número esperado de pasos en un paseo aleatorio que comienza en ${displaystyle u}$ , visitas ${displaystyle v}$ , y regresa a ${displaystyle u}$ . Para un gráfico con ${displaystyle m}$ bordes, la distancia de resistencia y el tiempo de conmutación están relacionados como ${displaystyle C_{u,v}=2mOmega _{u,v}}$ .

Como distancia euclidiana al cuadrado

Dado que el laplaciano $L$ es simétrico y semidefinido positivo, también lo es

{displaystyle left(L+{frac {1}{|V|}}Phi right),}

así su pseudo-inverso $.$ es también simétrico y positivo semi-definido. Así, hay un $K$ tales que ${displaystyle Gamma =KK^{textsf {T}}}$ y podemos escribir:

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

mostrando que la raíz cuadrada de la distancia de resistencia corresponde a la distancia euclidiana en el espacio abarcado por $K$ .

Conexión con los números de Fibonacci

Un gráfico de abanico es un gráfico en $n + 1$ vértices donde hay un borde entre el vértice $i$ y $n + 1$ para todos los $i = 1, 2, 3,\dots, n$ , y hay un borde entre el vértice $i$ y $i + 1$ para todos los $i = 1, 2, 3,\dots, n - 1$ .

La distancia de resistencia entre el vértice $n + 1$ y el vértice $i \in { 1, 2, 3,\dots, n}$ es

{displaystyle {frac {F_{2(n-i)+1}F_{2i-1}}{F_{2n}}}}

donde $F j$ es el $j$ -ésimo número de Fibonacci, para $j \geq 0$ .

Contenido relacionado

Más resultados...