Linear Spaces of a Graph, Part 2

Resistive Networks

How to contact me.
This material comes from some notes for a University of Waterloo course taught by Herb Shank. (c. 1975)
Back to Part 1.
When are Z and B disjoint?

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.

Proof. For any solution J, RHJ = H*RJ.

Since J in Z,
RHJ = R(wT1AT1 + wT2AT2 + ...)J
= R(wT1AT1J + wT2AT2J + ...)
= R(wT1J + wT2J + ...)

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.

Lemma 3. The spanning trees of G that do not contain the edge e are exactly the spanning trees of G-e. The edge sets of spanning trees of G which contain e consist of the union of {e} with the edge sets of spanning trees of Ge.
(Or, considering that we are using vector spaces, this union can be replaced by a sum, and the subsets replaced by vectors.)

Proof. Easy Exercise.

Corollary. N(G) = N(G-e) + N(Ge ).
Without pictures, the next little section is not as pretty as it could be. (As if html is a pretty way to display sums and other mathematical symbols.)

One can let a picture of the graph represent the number of spaning trees of the graph. Then the recursive equation given in the Corollary can be used to calculate the number of spanning trees of the graph. This method is frequently displayed in elementary texts on graph theory.

I do not suggest you use this method for large graphs. The
Matrix-Tree Theorem is far better computationally.
Lemma 4. If d in Z(G-e), then d in Z(G). If d in Z(Ge ), then d+ke in Z(G), for some k.

Proof. The first statement is easy. We prove only the second.

To distinguish between AT in G and in Ge, use aT for the latter. Thus, if T is a tree in Ge,
ATei = aTei + uie, where ui in {0,1,-1}.

We are given that d = x1aTe1 + x2aTe2 + ....

Thus, d + (x1u1 + x2u2 + ... )e = x1ATe1 + x2ATe2 + ....
Lemma 5. If d in B(Ge ), then d in B(G). If d in B(G-e), then d+ke in B(G), for some k.

Proof. Exercise.
Lemma 6. AT + BT* = I.

Proof. Look at
( (AT + BT*)ei , ej )
= (ATei,ej ) + (BT*ei , ej )
= (ATei,ej ) + (ei,BTej )

If i and j are distinct, these last two terms are either both zero, or they are of equal magnitude and opposite sign.

If i=j, and ei not in T, then (ATei,ej ) = 1 and (ei,BTej ) = 0.

If i=j, and ei in T, then (ATei,ej ) = 0 and (ei,BTej ) = 1.
When are Z and B disjoint?

Back to the Graph Theory Index.
Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436

Last modified November 3, 2000, by S.C. Locke.