Frank Harary
Princeton University and Institute for Advanced Study
In this survey article, we describe the following topics on electric networks in graph theoretic terms: (1) Kirchhoff's Laws, his mesh and node equations, and his matrix tree theorem, (2) flow problems and Menger's theorem, (3) boolean functions and enumeration and synthesis problems, (b) twoterminal netsworks, (5) probabilistic problems, (6) sequential machines, and (7) some unsolved problems.
The graph of a network:
There have been several expositions containing this classical material, e.g., Eckmann [ll], Foster [17], Hohn [30], Kirchhoff [31], MacWillisms [34], Nerode and Shank [40], Reza [47], and Seshu [5l]. Our development is based mainly on the elegant treatment by MacWilliams. Given an electric network, it is often can effectively be done by means of a graph.responding graph G.
Figure1. A network N and its graph G.
The following terminology has been used by various authors:
1. Nodes and branches of a network,
2. Points and lines of a graph,
3. Vertices and edges of a linear graph,
4. 0-simplexes and 1-simplexes of a l-complex.
If the network is in on connected piece, we say that its convected. We note that the short circuit branches of the network are shrunk to a point in the graph.
An orientation of a graph is an arbitrary assignment of a direction to each of its lines. In
Figure 2, a particular orientation of the graph of Figure 1 is shown.
Figure 2. An oriented graph.
The letters are used for the points of this oriented graph, while letters indicate its lines. A l-chain on a graph G with p points and q lines is a formal sum of lines of the form
where the coefficients ck, are real numbers (complex number or rational numbers would also do). The set of all l-chains on G is a vector space V1. Since the set of all lines of G is a basis for V1. Since the set of all lines of G is a basis for V1, its dimension is q.
Similarly, a O-chain on G is a formal sum of its points:
where again we take the coefficients as real numbers. The set of all 0-chains on G is also a vector space, denoted V0; its dimension is p.
of all O-chains on G is also a vector
We now introduce the boundary operator which maps V1 into Vo and the coboundary operator which maps Vo into V1. We first define the boundary of an oriented line and then extend the operator to any l-chain X by taking it to be linear:
To define the coboundary operator, let b be a point of the oriented graph G for which the oriented lines , …, are directed toward b while are away from b. Then the coboundary is extended to any O-chain A by linearity:
Sometimes is called the bundle at b.
We now outline these concepts in order to develop some additional mathematical results in the modern terminology of combinatorial topology. Graph theory has been called l-dimensional combinatorial topology as for example in the subtitle of the classical book by König [32].
A topological cycle or more briefly a t-cycle is a l-chain whose boundary is 0. We shall use the symbol 0 for a l-chain, a O-chain, and the real number zero; the meaning will always be clear by context. A cycle of an oriented graph consists of n distinct points together with lines of the form It is known that every t-cycle is a linear combination of cycles, and every coboundary 1s a linear combination of bundles. Let C1 be the collection of all t-cycles. Then C1 is a vector subspace of V1 ; we call it the cycle space of G. (In the topological literature, “cycle” usually means our topological cycle and “primitive cycle” stands for our cycle; in circuit theory “mesh” or "loop" are often used for the latter.)
The inner product of two l-chains X and X’ or of two O-chains A and A’ is the sum of the products of the respseacients. Two l-chains or two X chains and X’ or two 0-chaie orthogonal if their inner product is 0.
A coboundarg of G (sometimes called a cocycle) is a l-chain X which is the coboundary of some O-chain. Let D1 be the set of all coboundaries of G; then D1 is also a vector subspace of V1. With these concept: available, the following theorems may now be developed. We omit all proofs here.
Theorems
1. For any O-chain A and l-chain X,
2. The inner product of a cycle and a coboundary is 0.
3. If a l-chain is both a cycle and a coboundary, then it is the O-vector of V1.
4. Any l-chain orthogonal to every coboundary is a cycle.
5. Any O-chain orthogonal to every cycle is a coboundary.
6. Every l-chain is expressible uniquely as the sum of a cycle and a coboundary.
7. The dimensions of the cycle and coboundary spaces of G are:
8. Over the field of integers modulo 2, a set of lines is a cut set if and only if it is a co- boundary.
1. Kirchhoff's laws, mesh and node equation, and matrix tree theorem:
Although the material in this section is expressed in a more modern formulation, it is either
implicitly or explicitly contained in the pioneering paper of Kirchhoff [31].
For simplicity, we now consider a network with voltage sources only. We denote the instantaneous value of the current in the branch or arc by . The orientation of is determined by assigning the direction so that the current is positive on that arc. We can now define a current l-chain,
Kirchhoff’s current law. The algebraic sum of the currents entering any node is zero:
Since only voltage sources are allowed, this can be translated to say that the l-chain
I is orthogonal to the coboundary of each point.
But by one of the theorems cited above, this may be restated as follows:
I is a topological cycle on G.
Consider the voltage l-chain, , and also the l-chain of impressed voltages, .
Kirchhoff's voltage law. The total voltage drop around a circuit (cycle) of a network is equal to the impressed voltage in circuit.
For any cycle Z of G, this voltage law may be written symbolically using inner products:
or .
But by one of the theorems, this may be restated: is a coboundary on G.
An entirely analogous development holds for the case of impressed currents only and no voltage sources. Also, the more general case of both impressed voltages and currents offers no additional conceptual difficulty. The coefficients of the voltage and current l-chains are related by Ohm's law.
Kirchhoff's mesh and node equations.
We again consider impressed voltages only. Let us express the same cycle 2 of G in terms of both aeyclebasis of C where in accordance with equation (6); and also as a l-chain, that is, as a linear combination of the oriented lines of G:
By a well-knoun result from the theory of linear vector spaces, there is a q by m matrix M such that when we regard Z as the column vector of the coefficients in equation (7) and X as the column vector of the coefficients in equation (
, we have X = MZ. In fact, the i, j element of matrix M is given by the inner product .
Now corresponding to the current l-chain I, let us take J to be the same l-chain as I but expressed in terms of the cycles
Then by the above considerations,
where I and J are both taken as column vectors.
Let be the transpose of M and let Y be any coboundary. It is readily shown that M'Y is a column vector of zeros:
For the purpose of deriving kirchhoff's mesh equations, we require Ohm's law:
where R is a q by q symmetric matrix which gives the instantaneous impedance in the arcs (branches) of the network whose graph is G. Now using equation (10) which holds for any coboundary Y and noting that V - E is a coboundsry, we have
.
When we multiply both sides of equation (11) by M' and combine this with (12) we get
Susbtituting from equation (9) we obtain
kirchhoff's mesh equations:
If the matrix M'RM has an inverse, then the mesh equations have a solution for J. this concise matrix eqution (13) becomes the usual from of the mesh equations when expanded. we omit the node equtions which are entirly analogous.
Kirchhoff's network theorems.
There are tow theorems to be developed. The first assumes a single impressed voltage on exactly one arc of a network and derives the current in each circiut. The secnd theorem involves exactly one impressed current and expressed thevoltage drop between each pair of adjacent points of the graphof the network. we do not derive all the details, but provide enough information so that the statements of the theorem are clear. this also serves to provide the electrical background for the matrix tree theorem.
A tree T of a connected graph G is a connected subgraph having the same point set as G in which there are no cycles. For any tree T of a given connected graph G, every line of G is either in T or not in T. If it is in T we call it a twing of T; if not in T it in chord of T. The word "chord" has already been used in the literature, e.g., Macwilliams [34], nerod and shank [40], and reza [47];"twig" is being introduced here. The numberof twings in a tree of Gis p - 1, hence the number of chords is q - p + 1. It is no coincidence that these are the dimensions of the coboundary space and the cycle space of G respectively.
On adding a chord αi to T, the resulting subgraph of G contains a single cycle Zi .We orient this cycle so that +Zi contains the oriented line +αi . Corresponding to a tree T of G, we define a linear mapping F of l-chains into l-chains:
or if is a twig or a chord.
For convenience, let the chords of T be , where m= q - p + l. Clearly, for i = l, ..., m. But any topological cycle Z can be written
Therefore, FT maps any topological cycle onto itself. Also, Ft maps any l-chain into a t-cycle.
The tree T may also be used to construct a base for D1, the coboundary space of G. We will see that each twig of T determines a unique coboundary Bi in G consisting of this twig (with positive orientation) and of certain chords of T. The construction of this coboundary is entirely analogous with the construction of a cycle of G determined by a single chord of T and certain twigs. We thus obtain p - l independent coboundaries. since each contains a line (its twig) which is none of the other coboundaries, they constitute a coboundary basis. This is accomplished by means of the following linear mapping HT of l-chains into l-chains:
or 0 if is a twig or chord.
It is easily seen that Ht is the identity map on all coboundaries.
To construct the coboundary defined by a twig , remove αi from T. Of the tow disjoint subtrees, let T1 be the one containing the terminal point of the oriented line . Let P1 be the set of points of T1. Then
.
We now consider the case where the matricx R of equation (11) is a diagonal matrix. Then for each arc , we have .
We associate with each tree T a weight WT
Where the product is taken over all the chords of T. We now define a mapping F of K into itself in terms of the maps FT of (14):
Where the summation is over all the trees of G. It is conventient to symbolize the weights of all the trees ; let
then
Now for simplicity, consider the situation in which there is exactly one voltage source e in the arc αi , and that we wish to find the current ik in the arc αk . with the help of the above results , a straightforward manipulation leads readily to the following aquation, which constitutes.
Kirchhoff’s network theorem for currents:
kirchoff’s network theorem for voltage is analogous. This time we consider a single current source I impressed into the arc αi and find the resulting voltage between the pairs of adjacent points of each arc αk of G. Let Y be the mapping of K1 onto itself defined by where is the instantaneous admittance of . With each tree T we associate a weight UT :
Where the product this is taken over all the twigs of T
We require the sum of these weights
Consider the mapping
then
We now have all the apparatus needed to express the voltage vk in the arc αk in terms of this single impressed current source and the trees T of G.
Kirchhoff’s network theorem for voltages:
There is now a five step procedure to find the node-pair voltage in the arc (and of course an analogous method for finding the current using equation (20))
1. Find all the trees T of the network graph G.
2. For each tree T find UT, the”branch admittance product”.
3. The sum D of these weights Ut is the denominator.
4. For each tree T of which is a twig, is a factor of U.
See whether line is contrained in the coboundary .
5. If it is, add to the numerator depending on their relative orientation.
The matrix tree theorem
This famous theorem gives in its simplest form a determinant formula for the number of trees in a graph. it is equal to the number D of equation (22) for a case that all the admittances Yk have the value 1. It is implicit in Kichhoff’s original paper [31] and has been rediscovered many times. Among the independent discoverers of this beautiful result, we find van Aardenne-Ehrenfest and de bruijn [1], brooks, Smith, Stone and Tatte [6], and Trent [56]. It has been extended to directed graphs first by Tutte [57] and then by Okada and Onodera [43] and B and Mayberry [5]. The result for directed graphs is also in the recent book on graph theory by Berge [4]. In view of its intimate relationship with Kirchhoff’s network theorems we state it here, first in its very simple form for ordinary graphs, then in the more general case of directed graphs.
Let G be an ordinary graph, in which none of the lines is oriented. Let be the points of G. The adjacency matrix A of G is a square matrix order p in which if the point ai and aj are adjacent, and is 0 otherwise. We note that the diagonal of matrix A consists entirely of zeros.
The degree of a point of G is the number of orther points of G to which it is adjacent. Thus the degree of is the i’th row sum of matrix A. let B be the degree matrix, which is a diagonal matrix.
[list=1][*]
الرئيسية 
