2. Network Topology and Graph-Theoretic Formulation

Introduction and Context

Network topology provides the structural language through which an electrical network can be described independently of the particular numerical values of its elements. In circuit analysis, Kirchhoff’s current law (KCL) and Kirchhoff’s voltage law (KVL) are usually introduced as physical laws. Graph theory converts these laws into systematic algebraic procedures that remain effective for large, sparsely connected, and computer-oriented networks.

A circuit graph represents the interconnection of branches and nodes. Once a suitable tree, set of links, and orientation are selected, the topology can be expressed through incidence, tie-set, and cut-set matrices. These matrices expose the dependence among branch currents and voltages and lead directly to nodal, mesh, and modified nodal formulations. The approach is therefore foundational for network synthesis, power-system computation, circuit simulation, sensitivity analysis, and automated equation generation.

The essential distinction is between topology and element behavior. Topology specifies which terminals are connected; constitutive relations specify how a resistor, inductor, capacitor, voltage source, or current source behaves. A complete network model requires both.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Represent an electrical network as an oriented graph.

2. Distinguish nodes, branches, loops, trees, links, cut sets, and tie sets.

3. Construct reduced incidence, fundamental tie-set, and fundamental cut-set matrices.

4. Explain the rank and dependence properties of topological matrices.

5. Derive systematic nodal, mesh, and modified nodal equations.

6. Select an appropriate formulation for networks containing independent or dependent sources.

7. Identify common modelling errors and verify equations using topological tests.

8. Interpret the role of sparse matrix methods and computer-aided network formulation.

From a Circuit Diagram to an Oriented Graph

A graph G consists of a set of vertices (nodes) and a set of edges (branches) joining pairs of vertices. In an electrical network, a node is a set of points at the same electrical potential, while a branch is a two-terminal element or a series combination treated as one topological connection. A branch is assigned an arbitrary reference direction. This orientation does not impose a physical current direction; it only determines the signs used in equations.

If a branch is directed from node i to node j, its branch voltage may be defined as

v_b = V_i - V_j,

and its branch current is positive from i to j. Reversing the reference direction changes the signs of both variables but does not change the physical solution.

A graph is connected if a path exists between every pair of nodes. Most ordinary circuits are connected, although multiport and disconnected network models may require separate treatment. Parallel branches are distinct edges even when they join the same two nodes. Self-loops are uncommon in elementary circuit diagrams but can arise in abstract formulations and require special attention.

Important terminology includes:

• Node: A junction or electrically equipotential set of points.
• Branch: A network element represented by one graph edge.
• Degree of a node: The number of incident branches, counting parallel branches separately.
• Path: A sequence of branches connecting two nodes.
• Loop or circuit: A closed path.
• Connected graph: A graph in which every node is reachable from every other node.
• Subgraph: A graph formed from selected nodes and branches of the original graph.

For a connected graph with n nodes and b branches, the number of independent topological loops is

l = b - n + 1.

This quantity is also called the cyclomatic number or the number of links relative to a tree. It is central to mesh analysis.

Trees, Links, and Fundamental Structures

A tree is a connected subgraph containing all n nodes but no closed path. Consequently, a tree has n − 1 branches. These branches are called twigs. Any branch not belonging to the selected tree is called a link or chord. The number of links is therefore

b - (n - 1) = b - n + 1 = l.

A graph may possess many different trees. The electrical network does not change when the tree changes; only the algebraic organization of the equations changes.

Adding one link to a tree creates exactly one independent closed path. This path is called a fundamental loop or fundamental tie set associated with that link. The link is the reference branch of the tie set. Since each link creates one fundamental loop, the number of fundamental tie sets equals l.

Removing one twig from a tree separates the graph into two connected components. The set of all branches crossing between these components is a fundamental cut set, or fundamental cutset, associated with that twig. Each fundamental cut set contains its defining twig and possibly several links. There are n − 1 fundamental cut sets.

The tree is more than a visual aid. It partitions the network variables into a set that can serve as independent coordinates and a complementary set that is determined by topology. In nodal formulations, node voltages are primary variables. In loop formulations, link currents or mesh currents may serve as independent variables, depending on the selected representation.

Incidence Matrices and Kirchhoff’s Laws

Let A be the node-branch incidence matrix. Using the convention that a branch leaving a node contributes +1 and a branch entering a node contributes −1, each column of A contains one +1 and one −1 for an ordinary branch. All other entries are zero. If the branch-current vector is i, KCL can be written as

A i = 0.

The sum of all rows of A is zero because every branch has one departure and one arrival node. Therefore, for a connected graph, rank(A) = n − 1. One row is redundant. Deleting the row corresponding to a reference node produces the reduced incidence matrix A_r, which has full row rank n − 1.

The branch-voltage vector v is related to the node-voltage vector e by

v = A_r^T e,

provided branch voltage polarity is consistent with the incidence convention. The transpose relation is significant: node voltages generate branch voltage differences, while incidence applied to branch currents generates node current balances.

The identity

A_r A_r^T

is the reduced graph Laplacian. In resistive networks, it appears in the nodal conductance matrix and inherits symmetry and positive-semidefinite properties under appropriate element assumptions.

The incidence matrix provides a compact representation of KCL, but it does not by itself contain element laws. For a linear admittance branch model,

i = Y_b v + i_s,

where Y_b is a diagonal matrix of branch admittances and i_s represents current-source contributions. Substitution into KCL gives

A_r Y_b A_r^T e = -A_r i_s,

with sign changes depending on the selected source convention. This is the matrix form of nodal analysis.

Tie-Set Matrices and KVL

A tie-set matrix B_f describes the orientation of fundamental loops. Its rows correspond to fundamental tie sets and its columns to branches. An entry is +1 when a branch belongs to the tie set with the same orientation as the selected loop direction, −1 when it has the opposite orientation, and 0 when it is absent.

Because the algebraic sum of branch voltages around every closed path is zero, KVL becomes

B_f v = 0.

The link columns of B_f can be arranged as an identity matrix if each fundamental loop is oriented in the direction of its defining link. The twig columns then describe the tree path connecting the endpoints of that link. This arrangement makes the independence of the fundamental loops explicit.

A general loop matrix B satisfies

B A_r^T = 0.

This orthogonality expresses the fact that the sum of potential differences around a closed path is zero. It also shows that the loop-voltage space is orthogonal to the branch-voltage space generated by node potentials.

For a network with branch impedance relation

v = Z_b i + v_s,

KVL gives

B_f Z_b i + B_f v_s = 0.

If branch currents are represented by independent loop currents, the corresponding mesh or loop impedance equations follow. In planar networks, the familiar mesh matrix is a special, geometrically convenient form of a tie-set formulation. Tie-set analysis, however, is not restricted to planar circuits.

Cut Sets and Current Relations

A cut set is a minimal set of branches whose removal separates a connected graph into two parts. Applying KCL to the boundary between these parts gives an algebraic sum of cut-set currents equal to zero. If Q_f denotes the fundamental cut-set matrix, then

Q_f i = 0.

A fundamental cut-set matrix has n − 1 rows. With consistent tree and link ordering, it can be written in the form

Q_f = [I Q_l],

where the identity columns correspond to twigs. The fundamental cut-set and tie-set matrices satisfy the orthogonality relation

Q_f B_f^T = 0.

This relation is a powerful checking tool. A sign error in either matrix commonly causes nonzero products.

The matrix relationships among the three topological descriptions may be summarized as follows:

• A_r i = 0 represents KCL at independent nodes.
• B_f v = 0 represents KVL in independent loops.
• v = A_r^T e represents branch voltages generated by node potentials.
• Q_f i = 0 represents independent cut-set current relations.
• Q_f B_f^T = 0 expresses cut-set/tie-set orthogonality.

Deriving Nodal, Mesh, and Modified Nodal Equations

Nodal formulation

The nodal method selects node voltages relative to a reference node as unknowns. For a linear network with resistive or admittance branches, each branch current is expressed in terms of node voltages. Matrix assembly is especially systematic:

Y_n = A_r Y_b A_r^T.

The equation

Y_n e = j_n

contains the nodal admittance matrix Y_n, node-voltage vector e, and injected-current vector j_n. For passive reciprocal branches, Y_n is generally symmetric. Its diagonal entries are sums of admittances incident at a node; off-diagonal entries are the negatives of admittances directly connecting two nonreference nodes.

A voltage source between two nonreference nodes cannot be represented by an ordinary admittance branch. It imposes a voltage constraint and leads naturally to modified nodal analysis.

Mesh and loop formulation

In a planar circuit, mesh currents are assigned to elementary faces. Branch currents are obtained by adding or subtracting adjacent mesh currents. KVL around each mesh yields

Z_m i_m = v_m,

where Z_m is the mesh impedance matrix. In a general graph, fundamental loop currents can replace planar mesh currents. If the branch current vector is represented as

i = B_f^T i_l,

then substitution into branch impedance relations and application of KVL gives a loop equation. The precise source sign depends on the orientation conventions, but the topology is independent of those choices.

Mesh analysis is attractive when there are relatively few independent loops and voltage sources dominate. Nodal analysis is usually preferable when there are fewer essential nodes or many current sources.

Modified nodal analysis

Modified nodal analysis (MNA) retains node voltages as unknowns and adds currents through voltage sources as additional unknowns. For a network containing p independent voltage sources, a common linear form is

[ G A_v ; A_v^T 0 ] [ e ; i_v ] = [ j ; v_s ].

Here G contains conductance contributions, A_v is the incidence submatrix for voltage-source branches, i_v is the vector of source currents, j is the vector of current injections, and v_s is the source-voltage vector. The lower block imposes voltage constraints; the upper block expresses KCL including the unknown source currents.

The zero block reflects the fact that an ideal voltage source has no direct current-voltage admittance relation. The MNA matrix may be symmetric but indefinite. Dependent voltage and current sources can be incorporated by adding controlled-source coefficients to the appropriate blocks.

MNA is the standard foundation of many circuit simulators because it handles mixed element types, algebraic constraints, initial conditions, and dynamic companion models in a unified way.

An Illustrative Network Formulation

Consider three nonreference nodes, a, b, and c, with a reference node 0. Suppose conductances g1, g2, and g3 connect a–0, b–0, and c–0, respectively; conductance g4 connects a–b; conductance g5 connects b–c; and an independent current source injects current J into node a and extracts it at node c.

The reduced incidence matrix can be formed by assigning a direction to every branch. Without writing every branch column explicitly, the resulting nodal equations are

[ g1+g4 −g4 0 ] [Va] [ J]

[ −g4 g2+g4+g5 −g5 ] [Vb] = [ 0]

[ 0 −g5 g3+g5 ] [Vc] [−J].

The diagonal terms are sums of incident conductances. Each off-diagonal term is the negative of the conductance directly linking the corresponding nodes. This pattern is not a memorized rule independent of topology; it is the numerical manifestation of A_r Y_b A_r^T.

If an ideal voltage source V_s is inserted between nodes a and b, its current becomes an additional unknown I_s. The first two KCL equations acquire the source-current terms, while a fourth equation imposes

Va − Vb = V_s.

MNA therefore avoids the artificial replacement of the voltage source by an equivalent resistance or the awkward formation of a supermesh.

A Graph-Theoretic Applied Case: Automated Formulation of a Converter Subnetwork

Background

Consider an illustrative power-electronic converter subnetwork containing a DC-link capacitor, two controlled switches represented temporarily by ideal voltage-source constraints, a load resistor, and current injection from a filter inductor model. The circuit is to be simulated repeatedly under different switching states.

Problem

Manual re-derivation of nodal equations for every switching state is error-prone. In particular, voltage-source branches change the constraint structure, and a branch that is present in one state may be absent or replaced by another model in a different state.

Analysis and approach

The modelling procedure begins by assigning a node number and an orientation to every possible branch. A sparse incidence matrix is generated from the connectivity list. Conductive branches contribute to G through the product A_r Y_b A_r^T. Voltage-source branches are collected in A_v and produce MNA current unknowns. The source vector is assembled according to branch orientation.

For each switching state, the simulator updates only the element-value and constraint data while preserving the graph-based assembly procedure. Before solving, it checks that the active graph is connected where required, that no prohibited ideal-source loop has been created, and that the dimensions and ranks of the assembled matrices are consistent.

Outcome

The same formulation supports DC operating-point analysis, small-signal linearization, and time-domain simulation using companion models for capacitors and inductors. Sparse storage reduces memory use because each branch modifies only a small number of matrix entries. The topology also supports automatic reporting of floating nodes, disconnected subcircuits, and redundant constraints.

Learning points

The important result is not a particular numerical waveform but a reliable workflow: represent connectivity once, separate topology from constitutive data, assemble equations algorithmically, and validate rank and sign conventions before numerical solution. This principle applies to circuit simulators, power-system tools, and network optimization software.

Verification, Difficulties, and Professional Practice

Topological formulations are systematic but not immune to modelling errors. The most frequent mistakes are inconsistent branch orientations, omission of a reference node, incorrect treatment of parallel branches, and use of a voltage-source branch as though it were an admittance. Sign errors can often be isolated by checking individual columns of the incidence matrix and verifying that every ordinary column contains one +1 and one −1.

A connected graph must have rank(A) = n − 1. If the reduced incidence matrix has deficient rank, either the graph is disconnected or the node list is incorrect. Similarly, the expected number of independent loops is b − n + 1. A mismatch between this number and the row rank of a proposed tie-set matrix indicates dependence or omission.

Ideal-source configurations may produce singular or inconsistent equations. Examples include a voltage-source loop with incompatible prescribed voltages and a current-source cut set with incompatible current injections. Such situations are not merely numerical problems; they may represent an ill-posed ideal model. Practical parasitic resistances or more realistic device models can regularize the formulation, but the modelling decision should be documented.

In engineering software, matrix conditioning, sparsity, scaling, and pivoting are as important as symbolic correctness. A structurally correct matrix can still yield inaccurate results if element values differ by many orders of magnitude. Engineers should preserve sign conventions in documentation, maintain traceability from each matrix entry to a physical branch, and validate models using limiting cases and conservation checks.

Professional practice also requires awareness of software verification. Automated equation generation should be tested against hand-derived small networks, known passive-network properties, and independent implementations. In safety-critical power or control applications, a solver result should not be accepted solely because the numerical algorithm converged; topology, source constraints, and physical plausibility must also be reviewed.

Digital Formulation and Emerging Directions

Graph-based circuit modelling is naturally suited to digital tools. Netlists are essentially machine-readable connectivity descriptions. Sparse matrix assembly, symbolic elimination, automatic differentiation, and graph-partitioning algorithms are used in modern circuit and power-system programs. Automatic differentiation can obtain sensitivities of currents, voltages, or performance measures with respect to component values, while graph partitioning supports parallel computation.

Large-scale electrical systems increasingly combine circuit, electromagnetic, thermal, and control models. Multi-domain graph representations allow common nodes and ports to connect models from different physical domains, although the constitutive variables and conservation laws must be defined carefully. Data-driven and AI-assisted tools may help identify topology errors or estimate parameters, but they do not replace physical constraints. Any automated inference must remain subject to KCL, KVL, device limits, and engineering validation.

Chapter Summary

Graph theory separates the connectivity of a network from the constitutive laws of its elements. An oriented graph consists of nodes and branches; a tree contains all nodes and n − 1 twigs, while the remaining links generate the independent fundamental loops. A connected network with n nodes and b branches has b − n + 1 independent loops.

The reduced incidence matrix expresses KCL and generates branch voltages from node voltages. Tie-set matrices express KVL, while cut-set matrices express independent current relations. Their ranks and orthogonality relationships provide both theoretical insight and practical checks. Combining topological matrices with admittance or impedance laws yields systematic nodal and loop equations. Modified nodal analysis extends nodal formulation to ideal voltage sources by introducing their currents as unknowns and their voltage constraints as equations.

These methods are central to automated circuit formulation. Their professional use requires careful orientation, rank verification, treatment of singular ideal-source configurations, attention to numerical conditioning, and validation against physical laws.

Key Terms

Node: An electrically equipotential junction or set of connected points.

Branch: A two-terminal network element represented by one graph edge.

Oriented graph: A graph in which each branch has an assigned reference direction.

Incidence matrix: A matrix describing the connection and orientation of branches to nodes.

Reduced incidence matrix: An incidence matrix with one reference-node row removed.

Tree: A connected subgraph containing all nodes and no closed path.

Twig: A branch belonging to a selected tree.

Link: A branch not belonging to the selected tree.

Fundamental loop: The unique loop formed by adding one link to a tree.

Cut set: A minimal branch set whose removal disconnects a connected graph.

Fundamental cut set: The cut set associated with removal of one tree twig.

Tie-set matrix: A matrix describing branch membership and orientation in independent loops.

Cyclomatic number: The number b − n + 1 of independent loops in a connected graph.

KCL: The law stating that algebraic current sum at a node is zero.

KVL: The law stating that algebraic voltage sum around a closed path is zero.

Nodal analysis: A method using node voltages as primary unknowns.

Mesh analysis: A planar-network method using currents around independent meshes.

Modified nodal analysis: Nodal analysis augmented with currents through voltage sources and constraint equations.

Graph Laplacian: The matrix A_r A_r^T, or its weighted form, representing node connectivity.

Sparse matrix: A matrix in which most entries are zero, as commonly occurs in large network models.

Review Questions

Short Answer Questions

1. Why is one row removed when forming the reduced incidence matrix of a connected graph?

2. Define a tree, twig, and link.

3. What is the relationship between the number of branches, nodes, and independent loops?

4. State the matrix forms of KCL and KVL using incidence and tie-set matrices.

5. Why are additional current unknowns required in modified nodal analysis for ideal voltage sources?

Long Answer Questions

1. Explain how an oriented graph is constructed from an electrical network and discuss the significance of branch orientation.

2. Derive the nodal admittance matrix in the form A_r Y_b A_r^T and interpret its diagonal and off-diagonal entries.

3. Describe the construction and properties of fundamental tie-set and cut-set matrices.

4. Compare nodal, mesh, tie-set, and modified nodal formulations for different classes of electrical networks.

5. Explain the role of rank, orthogonality, and sparsity checks in computer-aided network formulation.

Analytical / Application Questions

1. A connected network has 8 nodes and 14 branches. Determine the number of twigs in any tree and the number of independent loops. Explain how these quantities guide equation selection.

2. Formulate the MNA equations for a two-node resistive network containing one conductance between the nodes, a current source to ground, and an ideal voltage source from the first node to ground.

3. A proposed incidence matrix for a connected six-node graph has rank 4. Diagnose the likely modelling issue and state the expected rank of the full and reduced incidence matrices.

22. Multiple Choice Questions with Answers

Question 1

For a connected graph with n nodes and b branches, the number of independent loops is

A. b + n − 1

B. b − n + 1

C. n − b + 1

D. b − n − 1

Correct Answer: B. b − n + 1

Question 2

Which matrix equation directly represents KCL for branch-current vector i?

A. A_r^T i = 0

B. B_f v = 0

C. A_r i = 0

D. Q_f v = 0

Correct Answer: C. A_r i = 0

Question 3

A tree of a connected graph containing n nodes has

A. n branches

B. n + 1 branches

C. n − 1 branches

D. b − n branches

Correct Answer: C. n − 1 branches

Question 4

The defining property of a fundamental tie set is that it is formed by

A. removing one link from the graph

B. adding one link to a tree

C. removing every twig from a tree

D. adding one node to a cut set

Correct Answer: B. adding one link to a tree

Question 5

For a connected graph, the rank of the full node-branch incidence matrix is

A. n

B. b

C. n − 1

D. b − n + 1

Correct Answer: C. n − 1

Question 6

Which relation expresses orthogonality between fundamental cut-set and tie-set matrices?

A. Q_f B_f^T = 0

B. Q_f A_r^T = I

C. B_f Q_f^T = I

D. A_r Q_f^T = 0

Correct Answer: A. Q_f B_f^T = 0

Question 7

In modified nodal analysis, the current through an ideal voltage source is

A. always set to zero

B. replaced by its conductance

C. introduced as an additional unknown

D. computed only after deleting the source

Correct Answer: C. introduced as an additional unknown

Question 8

For branch admittance matrix Y_b, the nodal admittance matrix generated by topology is

A. A_r^T Y_b A_r

B. A_r Y_b A_r^T

C. B_f Y_b B_f^T

D. Y_b A_r A_r^T

Correct Answer: B. A_r Y_b A_r^T

Question 9

A voltage-source loop with incompatible prescribed voltages most directly causes

A. an automatically passive network

B. an inconsistent or singular ideal model

C. a larger tree

D. a reduction in node count

Correct Answer: B. an inconsistent or singular ideal model

Question 10

Which formulation is generally most suitable when ideal voltage sources are present between nonreference nodes?

A. Ordinary nodal analysis without constraints

B. Modified nodal analysis

C. Incidence analysis without element laws

D. Cut-set analysis only

Correct Answer: B. Modified nodal analysis