Loading AI tools
Graph metric of electrical resistance between nodes 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 resistance of one ohm. It is a metric on graphs.
On a graph G, the resistance distance Ωi,j between two vertices vi and vj is[1]
with + denotes the Moore–Penrose inverse, L the Laplacian matrix of G, |V| is the number of vertices in G, and Φ is the |V| × |V| matrix containing all 1s.
If i = j then Ωi,j = 0. For an undirected graph
For any N-vertex simple connected graph G = (V, E) and arbitrary N×N matrix M:
From this generalized sum rule a number of relationships can be derived depending on the choice of M. Two of note are;
where the λk are the non-zero eigenvalues of the Laplacian matrix. This unordered sum
is called the Kirchhoff index of the graph.
For a simple connected graph G = (V, E), the resistance distance between two vertices may be expressed as a function of the set of spanning trees, T, of G as follows:
where T' is the set of spanning trees for the graph G' = (V, E + ei,j). In other words, for an edge , the resistance distance between a pair of nodes and is the probability that the edge is in a random spanning tree of .
The resistance distance between vertices and is proportional to the commute time of a random walk between and . The commute time is the expected number of steps in a random walk that starts at , visits , and returns to . For a graph with edges, the resistance distance and commute time are related as .[2]
Since the Laplacian L is symmetric and positive semi-definite, so is
thus its pseudo-inverse Γ is also symmetric and positive semi-definite. Thus, there is a K such that and we can write:
showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by K.
A fan graph is a graph on n + 1 vertices where there is an edge between vertex i and n + 1 for all i = 1, 2, 3, …, n, and there is an edge between vertex i and i + 1 for all i = 1, 2, 3, …, n – 1.
The resistance distance between vertex n + 1 and vertex i ∈ {1, 2, 3, …, n} is
where Fj is the j-th Fibonacci number, for j ≥ 0.[3]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.