This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000695230 Reproduction Date:
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.
On a graph G, the resistance distance Ω_{i,j} between two vertices v_{i} and v_{j} is
where Γ is the Moore–Penrose inverse of the Laplacian matrix of G.
If i = j then
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 \lambda_{k} are the non-zero eigenvalues of the Laplacian matrix. This unordered sum Σ_{iΩ}i,j is called the Kirchhoff index of the 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:
where T' is the set of spanning trees for the graph G'=(V, E+e_{i,j}).
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 = K K^T 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 \in \{1,2,3,...,n\} is \frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} } where F_{j} is the j-th Fibonacci number, for j \geq 0.^{[1]}^{[2]}
Graph theory, Computer science, Graph drawing, Category theory, Mathematics
Computer science, Mathematics, Topology, Combinatorics, Numerical analysis
Mathematics, Graph theory, Graph enumeration, Undirected graph, Edge (graph theory)
Gallery of named graphs, On-Line Encyclopedia of Integer Sequences, Cubic graph, Distance (graph theory), 6-j Symbol
Graph theory, Random walk, Percolation, Graph (mathematics), Uniform distribution (discrete)
Switch, Electric current, Voltage, Battery (electricity), Ampere
Electromagnetism, Authority control, Frequency, Magnetism, Maxwell's equations