- Resistance distance
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 anelectrical network , constructed so as to correspond to "G", with each edge being replaced by a 1ohm resistance. It is a metric on graphs.Definition
On a graph "G", the resistance distance Ω"i","j" between two vertices "vi" and "vj" is defined as
:Omega_{i,j}:=Gamma_{i,i}+Gamma_{j,j}-Gamma_{i,j}-Gamma_{j,i},
where Γ is the
Moore-Penrose inverse of theLaplacian 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}-2Gamma_{i,j},
General sum rule
For any "N"-vertex simple connected graph "G" = ("V", "E") and arbitrary "N"X"N" matrix "M":
:sum_{i,j in V}(LML)_{i,j}Omega_{i,j}=-2tr(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
where the lambda_{k} are the non-zero
eigenvalues of theLaplacian matrix .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}=egin{cases}frac{left | {t:t in T, e_{i,j} subseteq T} ight vert}{left | T ight vert}, & (i,j) in E\ frac{left | T^'-T ight vert}{left | T ight vert}, &(i,j) ot 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, it's pseudoinverse Gamma is also symmetric and positive semi-definite. Thus, there is a K such that Gamma = K K^T and we can write:
:Omega_{i,j} = Gamma_{i,i}+Gamma_{j,j}-Gamma_{i,j}-Gamma_{j,i} = K_iK_i^T + K_jK_j^T - K_iK_j^T - K_jK_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.Classical mechanics
In
classical mechanics , resistance distance is defined as the distance from the resistance (on alever ) to thefulcrum .References
* [http://www.springerlink.com/content/n66x902225127243/ Klein DJ, Randi M, "Resistance Distance", Journal of Mathematical Chemistry 12:81 ]
* [http://jagor.srce.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf Klein DJ, "Resistance Distance Sum Rules"]
Wikimedia Foundation. 2010.