Topology (electrical circuits)

Graph theory has been used in the network analysis of linear, passive networks almost from the moment that Kirchhoff's laws were formulated. Gustav Kirchhoff himself, in 1847, used graphs as an abstract representation of a network in his loop analysis of resistive circuits.[13] This approach was later generalised to RLC circuits, replacing resistances with impedances. In 1873 James Clerk Maxwell provided the dual of this analysis with node analysis.[14][15] Maxwell is also responsible for the topological theorem that the determinant of the node-admittance matrix is equal to the sum of all the tree admittance products. In 1900 Henri Poincaré introduced the idea of representing a graph by its incidence matrix,[16] hence founding the field of algebraic topology. In 1916 Oswald Veblen applied the algebraic topology of Poincaré to Kirchhoff's analysis.[17] Veblen is also responsible for the introduction of the spanning tree to aid choosing a compatible set of network variables.[18]

Figure 2.1. Circuit diagram of a ladder network low-pass filter: a two-element-kind network

Comprehensive cataloguing of network graphs as they apply to electrical circuits began with Percy MacMahon in 1891 (with an engineer friendly article in The Electrician in 1892) who limited his survey to series and parallel combinations. MacMahon called these graphs yoke-chains.[note 1] Ronald M. Foster in 1932 categorised graphs by their nullity or rank and provided charts of all those with a small number of nodes. This work grew out of an earlier survey by Foster while collaborating with George Campbell in 1920 on 4-port telephone repeaters and produced 83,539 distinct graphs.[19]

For a long time topology in electrical circuit theory remained concerned only with linear passive networks. The more recent developments of semiconductor devices and circuits have required new tools in topology to deal with them. Enormous increases in circuit complexity have led to the use of combinatorics in graph theory to improve the efficiency of computer calculation.[18]

Figure 2.2. Graph of the ladder network shown in figure 2.1 with a four rung ladder assumed.

Networks are commonly classified by the kind of electrical elements making them up. In a circuit diagram these element-kinds are specifically drawn, each with its own unique symbol. Resistive networks are one-element-kind networks, consisting only of R elements. Likewise capacitive or inductive networks are one-element-kind. The RC, RL and LC circuits are simple two-element-kind networks. The RLC circuit is the simplest three-element-kind network. The LC ladder network commonly used for low-pass filters can have many elements but is another example of a two-element-kind network.[20]

Conversely, topology is concerned only with the geometric relationship between the elements of a network, not with the kind of elements themselves. The heart of a topological representation of a network is the graph of the network. Elements are represented as the edges of the graph. An edge is drawn as a line, terminating on dots or small circles from which other edges (elements) may emanate. In circuit analysis, the edges of the graph are called branches. The dots are called the vertices of the graph and represent the nodes of the network. Node and vertex are terms that can be used interchangeably when discussing graphs of networks. Figure 2.2 shows a graph representation of the circuit in figure 2.1.[21]

Graphs used in network analysis are usually, in addition, both directed graphs, to capture the direction of current flow and voltage, and labelled graphs, to capture the uniqueness of the branches and nodes. For instance, a graph consisting of a square of branches would still be the same topological graph if two branches were interchanged unless the branches were uniquely labelled. In directed graphs, the two nodes that a branch connects to are designated the source and target nodes. Typically, these will be indicated by an arrow drawn on the branch.[22]

Incidence is one of the basic properties of a graph. An edge that is connected to a vertex is said to be incident on that vertex. The incidence of a graph can be captured in matrix format with a matrix called an incidence matrix. In fact, the incidence matrix is an alternative mathematical representation of the graph which dispenses with the need for any kind of drawing. Matrix rows correspond to nodes and matrix columns correspond to branches. The elements of the matrix are either zero, for no incidence, or one, for incidence between the node and branch. Direction in directed graphs is indicated by the sign of the element.[18][23]

Graphs are equivalent if one can be transformed into the other by deformation. Deformation can include the operations of translation, rotation and reflection; bending and stretching the branches; and crossing or knotting the branches. Two graphs which are equivalent through deformation are said to be congruent.[24]

In the field of electrical networks, there are two additional transforms that are considered to result in equivalent graphs which do not produce congruent graphs. The first of these is the interchange of series connected branches. This is the dual of interchange of parallel connected branches which can be achieved by deformation without the need for a special rule. The second is concerned with graphs divided into two or more separate parts, that is, a graph with two sets of nodes which have no branches incident to a node in each set. Two such separate parts are considered an equivalent graph to one where the parts are joined by combining a node from each into a single node. Likewise, a graph that can be split into two separate parts by splitting a node in two is also considered equivalent.[25]

Figure 2.3. One possible tree of the graph in figure 2.2. Links are shown as dotted lines.

A tree is a graph in which all the nodes are connected, either directly or indirectly, by branches, but without forming any closed loops. Since there are no closed loops, there are no currents in a tree. In network analysis, we are interested in spanning trees, that is, trees that connect every node present in the graph of the network. In this article, spanning tree is meant by an unqualified tree unless otherwise stated. A given network graph can contain a number of different trees. The branches removed from a graph in order to form a tree are called links, the branches remaining in the tree are called twigs. For a graph with n nodes, the number of branches in each tree, t, must be;

${\displaystyle t=n-1\ }$

An important relationship for circuit analysis is;

${\displaystyle b=\ell +t\ }$

where b is the number of branches in the graph and ℓ is the number of links removed to form the tree.[26]

The goal of circuit analysis is to determine all the branch currents and voltages in the network. These network variables are not all independent. The branch voltages are related to the branch currents by the transfer function of the elements of which they are composed. A complete solution of the network can therefore be either in terms of branch currents or branch voltages only. Nor are all the branch currents independent from each other. The minimum number of branch currents required for a complete solution is l. This is a consequence of the fact that a tree has l links removed and there can be no currents in a tree. Since the remaining branches of the tree have zero current they cannot be independent of the link currents. The branch currents chosen as a set of independent variables must be a set associated with the links of a tree: one cannot choose any l branches arbitrarily.[27]

In terms of branch voltages, a complete solution of the network can be obtained with t branch voltages. This is a consequence the fact that short-circuiting all the branches of a tree results in the voltage being zero everywhere. The link voltages cannot, therefore, be independent of the tree branch voltages.[28]

Figure 2.4. A cut set of the graph in figure 2.2 derived from the tree of figure 2.3 by cutting branch 3.

A common analysis approach is to solve for loop currents rather than branch currents. The branch currents are then found in terms of the loop currents. Again, the set of loop currents cannot be chosen arbitrarily. To guarantee a set of independent variables the loop currents must be those associated with a certain set of loops. This set of loops consists of those loops formed by replacing a single link of a given tree of the graph of the circuit to be analysed. Since replacing a single link in a tree forms exactly one unique loop, the number of loop currents so defined is equal to l. The term loop in this context is not the same as the usual meaning of loop in graph theory. The set of branches forming a given loop is called a tie set.[note 2] The set of network equations are formed by equating the loop currents to the algebraic sum of the tie set branch currents.[29]

It is possible to choose a set of independent loop currents without reference to the trees and tie sets. A sufficient, but not necessary, condition for choosing a set of independent loops is to ensure that each chosen loop includes at least one branch that was not previously included by loops already chosen. A particularly straightforward choice is that used in mesh analysis in which the loops are all chosen to be meshes.[note 3] Mesh analysis can only be applied if it is possible to map the graph on to a plane or a sphere without any of the branches crossing over. Such graphs are called planar graphs. Ability to map onto a plane or a sphere are equivalent conditions. Any finite graph mapped onto a plane can be shrunk until it will map onto a small region of a sphere. Conversely, a mesh of any graph mapped onto a sphere can be stretched until the space inside it occupies nearly all of the sphere. The entire graph then occupies only a small region of the sphere. This is the same as the first case, hence the graph will also map onto a plane.[30]

There is an approach to choosing network variables with voltages which is analogous and dual to the loop current method. Here the voltage associated with pairs of nodes are the primary variables and the branch voltages are found in terms of them. In this method also, a particular tree of the graph must be chosen in order to ensure that all the variables are independent. The dual of the tie set is the cut set. A tie set is formed by allowing all but one of the graph links to be open circuit. A cut set is formed by allowing all but one of the tree branches to be short circuit. The cut set consists of the tree branch which was not short-circuited and any of the links which are not short-circuited by the other tree branches. A cut set of a graph produces two disjoint subgraphs, that is, it cuts the graph into two parts, and is the minimum set of branches needed to do so. The set of network equations are formed by equating the node pair voltages to the algebraic sum of the cut set branch voltages.[31] The dual of the special case of mesh analysis is nodal analysis.[32]

The nullity, N, of a graph with s separate parts and b branches is defined by;

${\displaystyle N=b-n+s\ }$

The nullity of a graph represents the number of degrees of freedom of its set of network equations. For a planar graph, the nullity is equal to the number of meshes in the graph.[33]

The rank, R of a graph is defined by;

${\displaystyle R=n-s\ }$

Rank plays the same role in nodal analysis as nullity plays in mesh analysis. That is, it gives the number of node voltage equations required. Rank and nullity are dual concepts and are related by;[34]

${\displaystyle R+N=b\ }$

Once a set of geometrically independent variables have been chosen the state of the network is expressed in terms of these. The result is a set of independent linear equations which need to be solved simultaneously in order to find the values of the network variables. This set of equations can be expressed in a matrix format which leads to a characteristic parameter matrix for the network. Parameter matrices take the form of an impedance matrix if the equations have been formed on a loop-analysis basis, or as an admittance matrix if the equations have been formed on a node-analysis basis.[35]

These equations can be solved in a number of well-known ways. One method is the systematic elimination of variables.[36] Another method involves the use of determinants. This is known as Cramer's rule and provides a direct expression for the unknown variable in terms of determinants. This is useful in that it provides a compact expression for the solution. However, for anything more than the most trivial networks, a greater calculation effort is required for this method when working manually.[37]

Two graphs are dual when the relationship between branches and node pairs in one is the same as the relationship between branches and loops in the other. The dual of a graph can be found entirely by a graphical method.[38]

The dual of a graph is another graph. For a given tree in a graph, the complementary set of branches (i.e., the branches not in the tree) form a tree in the dual graph. The set of current loop equations associated with the tie sets of the original graph and tree are identical to the set of voltage node-pair equations associated with the cut sets of the dual graph.[39]

The following table lists dual concepts in topology related to circuit theory.[40]

Figure 2.5. The dual graph of the graph in figure 2.2.

The dual of a tree is sometimes called a maze[note 4] It consists of spaces connected by links in the same way that the tree consists of nodes connected by tree branches.[41]

Duals cannot be formed for every graph. Duality requires that every tie set has a dual cut set in the dual graph. This condition is met if and only if the graph is mappable on to a sphere with no branches crossing. To see this, note that a tie set is required to "tie off" a graph into two portions and its dual, the cut set, is required to cut a graph into two portions. The graph of a finite network which will not map on to a sphere will require an n-fold torus. A tie set that passes through a hole in a torus will fail to tie the graph into two parts. Consequently, the dual graph will not be cut into two parts and will not contain the required cut set. Consequently, only planar graphs have duals.[42]

Duals also cannot be formed for networks containing mutual inductances since there is no corresponding capacitive element. Equivalent circuits can be developed which do have duals, but the dual cannot be formed of a mutual inductance directly.[43]

Operations on a set of network equations have a topological meaning which can aid visualisation of what is happening. Elimination of a node voltage from a set of network equations corresponds topologically to the elimination of that node from the graph. For a node connected to three other nodes, this corresponds to the well known Y-Δ transform. The transform can be extended to greater numbers of connected nodes and is then known as the star-mesh transform.[44]

The inverse of this transform is the Δ-Y transform which analytically corresponds to the elimination of a mesh current and topologically corresponds to the elimination of a mesh. However, elimination of a mesh current whose mesh has branches in common with an arbitrary number of other meshes will not, in general, result in a realisable graph. This is because the graph of the transform of the general star is a graph which will not map on to a sphere (it contains star polygons and hence multiple crossovers). The dual of such a graph cannot exist, but is the graph required to represent a generalised mesh elimination.[44]

Figure 2.6. A double-tuned circuit frequently used to couple stages of tuned amplifiers. A, the graph of the double-tuned circuit. B, an equivalent graph with the disjoint parts combined.

In conventional graph representation of circuits, there is no means of explicitly representing mutual inductive couplings, such as occurs in a transformer, and such components may result in a disconnected graph with more than one separate part. For convenience of analysis, a graph with multiple parts can be combined into a single graph by unifying one node in each part into a single node. This makes no difference to the theoretical behaviour of the circuit so analysis carried out on it is still valid. It would, however, make a practical difference if a circuit were to be implemented this way in that it would destroy the isolation between the parts. An example would be a transformer earthed on both the primary and secondary side. The transformer still functions as a transformer with the same voltage ratio but can now no longer be used as an isolation transformer.[45]

More recent techniques in graph theory are able to deal with active components, which are also problematic in conventional theory. These new techniques are also able to deal with mutual couplings.[46]

There are two basic approaches available for dealing with mutual couplings and active components. In the first of these, Samuel Jefferson Mason in 1953 introduced signal-flow graphs.[47] Signal-flow graphs are weighted, directed graphs. He used these to analyse circuits containing mutual couplings and active networks. The weight of a directed edge in these graphs represents a gain, such as possessed by an amplifier. In general, signal-flow graphs, unlike the regular directed graphs described above, do not correspond to the topology of the physical arrangement of components.[46]

The second approach is to extend the classical method so that it includes mutual couplings and active components. Several methods have been proposed for achieving this. In one of these, two graphs are constructed, one representing the currents in the circuit and the other representing the voltages. Passive components will have identical branches in both trees but active components may not. The method relies on identifying spanning trees that are common to both graphs. An alternative method of extending the classical approach which requires only one graph was proposed by Chen in 1965.[note 5] Chen's method is based on a rooted tree.[46]

Another way of extending classical graph theory for active components is through the use of hypergraphs. Some electronic components are not represented naturally using graphs. The transistor has three connection points, but a normal graph branch may only connect to two nodes. Modern integrated circuits have many more connections than this. This problem can be overcome by using hypergraphs instead of regular graphs.[48]

Figure 2.7. An example of a hypergraph. Regular edges are shown in black, hyperedges are shown in blue, and tentacles are shown in red.

In a conventional representation components are represented by edges, each of which connects to two nodes. In a hypergraph, components are represented by hyperedges which can connect to an arbitrary number of nodes. Hyperedges have tentacles which connect the hyperedge to the nodes. The graphical representation of a hyperedge may be a box (compared to the edge which is a line) and the representations of its tentacles are lines from the box to the connected nodes. In a directed hypergraph, the tentacles carry labels which are determined by the hyperedge's label. A conventional directed graph can be thought of as a hypergraph with hyperedges each of which has two tentacles. These two tentacles are labelled source and target and usually indicated by an arrow. In a general hypergraph with more tentacles, more complex labelling will be required.[49]

Hypergraphs can be characterised by their incidence matrices. A regular graph containing only two-terminal components will have exactly two non-zero entries in each row. Any incidence matrix with more than two non-zero entries in any row is a representation of a hypergraph. The number of non-zero entries in a row is the rank of the corresponding branch, and the highest branch rank is the rank of the incidence matrix.[50]

Classical network analysis develops a set of network equations whose network variables are homogeneous in either current (loop analysis) or voltage (node analysis). The set of network variables so found is not necessarily the minimum necessary to form a set of independent equations. There may be a difference between the number of variables in a loop analysis to a node analysis. In some cases the minimum number possible may be less than either of these if the requirement for homogeneity is relaxed and a mix of current and voltage variables allowed. A result from Kishi and Katajini in 1967[note 6] is that the absolute minimum number of variables required to describe the behaviour of the network is given by the maximum distance[note 7] between any two spanning forests[note 8] of the network graph.[46]

Graph theory can be applied to network synthesis. Classical network synthesis realises the required network in one of a number of canonical forms. Examples of canonical forms are the realisation of a driving-point impedance by Cauer's canonical ladder network or Foster's canonical form or Brune's realisation of an immittance from his positive-real functions. Topological methods, on the other hand, do not start from a given canonical form. Rather, the form is a result of the mathematical representation. Some canonical forms require mutual inductances for their realisation. A major aim of topological methods of network synthesis has been to eliminate the need for these mutual inductances. One theorem to come out of topology is that a realisation of a driving-point impedance without mutual couplings is minimal if and only if there are no all-inductor or all-capacitor loops.[51]

Graph theory is at its most powerful in network synthesis when the elements of the network can be represented by real numbers (one-element-kind networks such as resistive networks) or binary states (such as switching networks).[46]

Perhaps, the earliest network with an infinite graph to be studied was the ladder network used to represent transmission lines developed, in its final form, by Oliver Heaviside in 1881. Certainly all early studies of infinite networks were limited to periodic structures such as ladders or grids with the same elements repeated over and over. It was not until the late 20th century that tools for analysing infinite networks with an arbitrary topology became available.[52]

Infinite networks are largely of only theoretical interest and are the plaything of mathematicians. Infinite networks that are not constrained by real-world restrictions can have some very unphysical properties. For instance Kirchhoff's laws can fail in some cases and infinite resistor ladders can be defined which have a driving-point impedance which depends on the termination at infinity. Another unphysical property of theoretical infinite networks is that, in general, they will dissipate infinite power unless constraints are placed on them in addition to the usual network laws such as Ohm's and Kirchhoff's laws. There are, however, some real-world applications. The transmission line example is one of a class of practical problems that can be modelled by infinitesimal elements (the distributed-element model). Other examples are launching waves into a continuous medium, fringing field problems, and measurement of resistance between points of a substrate or down a borehole.[53]

Transfinite networks extend the idea of infinite networks even further. A node at an extremity of an infinite network can have another branch connected to it leading to another network. This new network can itself be infinite. Thus, topologies can be constructed which have pairs of nodes with no finite path between them. Such networks of infinite networks are called transfinite networks.[54]