Resistance distance
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
.
G, the resistance distance Ωi,j between two vertices vi and vj is
where Γ is the Moore–Penrose inverse of the Laplacian matrix
of G.
For an undirected graph
G = (V, E) and arbitrary NXN 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
are the non-zero eigenvalues of the Laplacian matrix
.
of the set of spanning trees
, T, of G as follows:
where T' is the set of spanning trees for the graph
.
is symmetric and positive semi-definite, its pseudoinverse 
is also symmetric and positive semi-definite. Thus, there is a 
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
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the resistance distance between two vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
of a simple connected graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, G, is equal to the resistance
Electrical resistance
The electrical resistance of an electrical element is the opposition to the passage of an electric current through that element; the inverse quantity is electrical conductance, the ease at which an electric current passes. Electrical resistance shares some conceptual parallels with the mechanical...
between two equivalent points on an electrical network
Electrical network
An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, transmission lines, voltage sources, current sources and switches. An electrical circuit is a special type of network, one that has a closed loop giving a return path for the current...
, constructed so as to correspond to G, with each edge
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
being replaced by a 1 ohm
Ohm
The ohm is the SI unit of electrical resistance, named after German physicist Georg Simon Ohm.- Definition :The ohm is defined as a resistance between two points of a conductor when a constant potential difference of 1 volt, applied to these points, produces in the conductor a current of 1 ampere,...
resistance
Electrical resistance
The electrical resistance of an electrical element is the opposition to the passage of an electric current through that element; the inverse quantity is electrical conductance, the ease at which an electric current passes. Electrical resistance shares some conceptual parallels with the mechanical...
. It is a metric
Metric (mathematics)
In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...
on graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
.
Definition
On a graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G, the resistance distance Ωi,j between two vertices vi and vj is
where Γ is the Moore–Penrose inverse of the Laplacian matrix
Laplacian matrix
In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
of G.
Properties of resistance distance
If i = j thenFor an undirected graph
General sum rule
For any N-vertex simple connected graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G = (V, E) and arbitrary NXN matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
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
are the non-zero eigenvalues of the Laplacian matrixLaplacian matrix
In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
.
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 functionFunction (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
of the set of spanning trees
Spanning tree (mathematics)
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
, T, of G as follows:
where T' is the set of spanning trees for the graph
.As a squared Euclidean distance
Since the Laplacian is symmetric and positive semi-definite, its pseudoinverse is also symmetric and positive semi-definite. Thus, there is a such that and we can write:showing that the square root of the resistance distance corresponds to the Euclidean distance
Euclidean distance
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
in the space spanned by
.