# 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 *c*_{i} and a positive resistance *r*_{i} on each edge *e*_{i}. The problem is to determine the resulting current *j*_{i} and voltage drop *v*_{i} on edge *e*_{i}, assuming that the network is subject to conditions known as Ohm's law and Kirchhoff's voltage and current laws.

Let *V = v*_{1}e_{1} + v_{2}e_{2} + ...,
*J = j*_{1}e_{1} + j_{2}e_{2} + ...,
*c = c*_{1}e_{1} + c_{2}e_{2} + ..., and let *R : C -> C* be linear with *Re*_{i} = r_{i}e_{i}. 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,þn*_{i} )=0, for each vertex *n*_{i} (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 *j*_{i} 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*^{-1}R^{-1}H^{*}c,
*V = RJ*,

where
*D = w*_{T1} + w_{T2} + ...; 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(w*_{T1}A_{T1} + w_{T2}A_{T2} + ...)J

= R(w_{T1}A_{T1}J + w_{T2}A_{T2}J + ...)

= R(w_{T1}J + w_{T2}J + ...)

= RDJ.

Since *RJ-c* in *B*, and since
*A*_{T}^{*}b=0 for any *b* in *B* (look at linear products: *bA*_{T}e_{i}=0 for each edge *e*_{i}), it follows that
*H*^{*}RJ=H^{*}c.

Now, *RDJ = H*^{*}c and *J = D*^{-1}R^{-1}H^{*}c.

Taking inner products of each side of the above equation with an edge *e*_{i} yields

*j*_{i} =
D^{-1}r_{i}^{-1}
(w_{T1}(A_{T1}e_{i},c) +
w_{T1}(A_{T1}e_{i},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 *G*_{e} 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 *G*_{e}.

(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(G*_{e} ).

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(G*_{e} ), then *d+ke* in *Z(G)*, for some *k*.

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

To distinguish between *A*_{T} in *G* and in *G*_{e}, use *a*_{T} for the latter. Thus, if *T* is a tree in *G*_{e},

*A*_{T}e_{i} = a_{T}e_{i} + u_{i}e, where *u*_{i} in *{0,1,-1}*.

We are given that *d = x*_{1}a_{T}e_{1} +
x_{2}a_{T}e_{2} + ....

Thus, *d + (x*_{1}u_{1} +
x_{2}u_{2} + ... )e =
x_{1}A_{T}e_{1} +
x_{2}A_{T}e_{2} + ....

**Lemma 5**.
If *d* in *B(G*_{e} ), then *d* in *B(G)*. If
*d* in *B(G-e)*, then *d+ke* in *B(G)*, for some *k*.

**Proof**. Exercise.

**Lemma 6**. *A*_{T} + B_{T}^{*} = I.

**Proof**. Look at

*( (A*_{T} + B_{T}^{*})e_{i} , e_{j} )

= (A_{T}e_{i},e_{j} ) +
(B_{T}^{*}e_{i} , e_{j} )

= (A_{T}e_{i},e_{j} ) +
(e_{i},B_{T}e_{j} ).

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 *e*_{i} not in *T*, then
*(A*_{T}e_{i},e_{j} ) = 1 and
*(e*_{i},B_{T}e_{j} ) = 0.

If *i=j*, and *e*_{i} in *T*, then
*(A*_{T}e_{i},e_{j} ) = 0 and
*(e*_{i},B_{T}e_{j} ) = 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

USA**
Office: Room 286, Science & Engineering**

Phone: (561) 297-3350

Fax: (561) 297-2436

URL: http://www.math.fau.edu/locke/linspace.htm

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