Back to the
Graph
Theory Index.
As an application of Theorem 3, we consider a problem in resistive networks. The model is a connected graph together with a voltage source ci and a positive resistance ri on each edge ei. The problem is to determine the resulting current ji and voltage drop vi on edge ei, assuming that the network is subject to conditions known as Ohm's law and Kirchhoff's voltage and current laws.
Let V = v1e1 + v2e2 + ...,
J = j1e1 + j2e2 + ...,
c = c1e1 + c2e2 + ..., and let R : C -> C be linear with Rei = riei. In these terms, the resistive network problem is: given c and R, find V and J subject to V=RJ (Ohm's law) (V-c,z)=0, for each z in Z (Kirchhoff's voltage law) (J,þni )=0, for each vertex ni (Kirchhoff's current law).
(Kirchhoff's voltage law says that the sum of the voltage changes around each closed path is zero; Kirchhoff's current law says that the sum of the ji entering a vertex has to be the same as the sum leaving that vertex.)
Theorem 4.The solution to the resistive network problem is unique and is given by
J = D-1R-1H*c,
V = RJ,
where
D = wT1 + wT2 + ...; the sum being taken over all spanning trees of the graph.
Since RJ-c in B, and since
AT*b=0 for any b in B (look at linear products: bATei=0 for each edge ei), it follows that
H*RJ=H*c.
Now, RDJ = H*c and J = D-1R-1H*c.
Taking inner products of each side of the above equation with an edge ei yields ji =
D-1ri-1
(wT1(AT1ei,c) +
wT1(AT1ei,c) +
... ),
and this is the original form of the result (modulo my typsetting), due to Kirchhoff (1847). Existence and uniqueness of currents in a resistive network appears to have been proven first by H. Weyl (1923).
We now establish some facts about spanning trees.
Let G-e denote the graph obtained from G by deleting the edge e and let Ge denote the graph obtained from G by contracting the edge e. Note that the contraction operation may result in multiple edges. Let N(G) denote the number of spanning trees of G.