Resistance distance

From Wikipedia, the free encyclopedia

In graph theory, the resistance distance between two vertices of a simple connected graph, G, is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to G, with each edge being replaced by a 1 ohm resistance. It is a metric on graphs.

Definition

On a graph G, the resistance distance Ωi,j between two vertices vi and vj is

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

where Γ is the Moore–Penrose inverse of the Laplacian matrix of G.

Properties of resistance distance

If i = j then

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

For an undirected graph

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

General sum rule

For any N-vertex simple connected graph G = (V, E) and arbitrary N×N matrix M:

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

From this generalized sum rule a number of relationships can be derived depending on the choice of M. Two of note are;

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

where the \lambda _{{k}} are the non-zero eigenvalues of the Laplacian matrix. This unordered sum Σi<jΩi,j is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

For a simple connected graph G = (V, E), the resistance distance between two vertices may by expressed as a function of the set of spanning trees, T, of G as follows:

\Omega _{{i,j}}={\begin{cases}{\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)\not \in E\end{cases}}

where T' is the set of spanning trees for the graph G'=(V,E+e_{{i,j}}).

As a squared Euclidean distance

Since the Laplacian L is symmetric and positive semi-definite, its pseudoinverse \Gamma is also symmetric and positive semi-definite. Thus, there is a K such that \Gamma =KK^{T} and we can write:

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

showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by K.

See also

References

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.