Graph Theory

Graph theory forms the mathematical foundation for systematic analysis of electrical networks. Instead of working directly with circuit elements, graph theory abstracts a network into nodes and branches, enabling the application of powerful matrix methods to solve complex circuits. Concepts like incidence matrices, loop matrices, and cutset matrices are used to organize Kirchhoff's laws into matrix equations that can be solved algorithmically.

Core Concept: Graph Representation of Networks

A network graph is obtained by replacing every circuit element with a line segment called a branch and every junction point with a dot called a node. The resulting graph captures the topological connectivity of the circuit without regard to the actual element values. This separation of topology from element values is the power of graph theory in network analysis.

Each branch in the graph corresponds to a circuit element or a group of elements connected in series between two nodes. Each node represents an electrical node in the circuit. The graph preserves all information about how elements are connected, and this structural information is sufficient to write down Kirchhoff's voltage and current laws systematically using matrix methods.

A directed graph assigns a reference direction (arrow) to each branch, representing the assumed positive current direction. This direction is arbitrary but must be fixed before writing matrix equations. Once fixed, KCL and KVL can be expressed in consistent matrix form using the incidence and loop matrices.

Tree, Co-tree, and Loops

A tree of a graph is a connected subgraph that includes all nodes of the graph but contains no closed loops. For a graph with n nodes, a tree has exactly n-1 branches. The branches in the tree are called twigs. The remaining branches (those not in the tree) are called links or chords, and they form the co-tree.

If a graph has b branches and n nodes, then the number of links L = b - n + 1. Adding each link to the tree creates exactly one closed loop called a fundamental loop or independent loop. Thus, the number of independent loops equals the number of links, which equals b - n + 1. This number determines the number of independent KVL equations needed.

Similarly, the number of independent KCL equations is n - 1, since one node equation is always dependent on the others (the sum of all node equations must equal zero by KCL for the entire network). This gives the two key numbers: n-1 independent KCL equations and b-n+1 independent KVL equations, which together equal b total equations needed to solve for b unknown branch voltages or currents.

Incidence Matrix

The incidence matrix A of a directed graph is a matrix with n rows (one per node) and b columns (one per branch). Each entry A(i,j) is defined as: +1 if branch j leaves node i, -1 if branch j enters node i, and 0 if branch j is not connected to node i. The complete incidence matrix has the property that the sum of all entries in any column is zero (each branch enters one node and leaves another).

The reduced incidence matrix is obtained by deleting one row (corresponding to the reference node) from the complete incidence matrix. This reduced matrix has n-1 rows and b columns, and its rows are linearly independent. KCL for the network can be written as A * I_b = 0 where I_b is the vector of branch currents, and KVL as V_b = A^T * V_n where V_n is the vector of node voltages.

Loop Matrix and Cutset Matrix

The fundamental loop matrix (or tie-set matrix) B has one row for each fundamental loop and one column for each branch. An entry B(i,j) is +1 if branch j is in loop i with the same orientation as the link that defines the loop, -1 if branch j is in loop i but with opposite orientation, and 0 if branch j is not in loop i. KVL can be written as B * V_b = 0.

The fundamental cutset matrix (or f-cutset matrix) Q has one row per fundamental cutset and one column per branch. A cutset is a minimal set of branches whose removal splits the graph into two separate connected parts. KCL for cutsets is Q * I_b = 0. These three matrices A, B, and Q are all related and encode the complete topological information needed to analyze the network.

Given:
A network with n=3 nodes (1,2,3 with node 3 as reference) and b=3 branches.
Branch 1: from node 1 to node 3
Branch 2: from node 2 to node 3
Branch 3: from node 1 to node 2

Why this formula applies:
Use the incidence matrix to verify KCL and find independent equations.
n=3 nodes, b=3 branches, n-1=2 independent KCL equations.
Links = b - n + 1 = 3 - 3 + 1 = 1 independent loop.

Formula:
Complete incidence matrix A (n x b = 3 x 3):
Rows = nodes 1, 2, 3. Columns = branches 1, 2, 3.

Substitution:
Branch 1 leaves node 1, enters node 3:
  A(1,1)=+1, A(2,1)=0, A(3,1)=-1
Branch 2 leaves node 2, enters node 3:
  A(1,2)=0, A(2,2)=+1, A(3,2)=-1
Branch 3 leaves node 1, enters node 2:
  A(1,3)=+1, A(2,3)=-1, A(3,3)=0

Calculation:
Complete incidence matrix A:
       b1  b2  b3
Node1: +1   0  +1
Node2:  0  +1  -1
Node3: -1  -1   0

Column sum check: col1: 1+0-1=0 (correct), col2: 0+1-1=0 (correct), col3: 1-1+0=0 (correct)
Reduce by deleting row 3 (reference node 3):
Reduced A (2x3):
       b1  b2  b3
Node1: +1   0  +1
Node2:  0  +1  -1

KCL: A*I_b = 0
=> I1 + I3 = 0 (for node 1) and I2 - I3 = 0 (for node 2)
=> I3 = -I1 and I2 = I3 = -I1 (consistent with KCL).

Final Answer with units:
n=3, b=3, tree branches = n-1 = 2, links = b-n+1 = 1 (one independent loop).
Reduced incidence matrix is 2x3. Rank = 2. KCL gives 2 independent equations.

Exam Tip: For a connected graph with n nodes and b branches, always remember: tree branches = n-1, links = b-n+1, independent KCL equations = n-1, independent KVL equations = b-n+1. These four quantities completely define the complexity of the network equations.

• A network graph abstracts circuit topology: nodes replace junctions, branches replace elements.
• For n nodes and b branches: tree has n-1 twigs, co-tree has b-n+1 links.
• Independent KCL equations = n-1. Independent KVL equations = b-n+1 = number of links = number of fundamental loops.
• Incidence matrix A: size (n-1) x b. KCL: A*I_b = 0. KVL: V_b = A^T * V_n.
• Loop matrix B: size (b-n+1) x b. KVL: B*V_b = 0.
• Cutset matrix Q: size (n-1) x b. KCL: Q*I_b = 0.

Quick Revision

• Graph: nodes (n) + branches (b). Directed graph assigns reference direction to each branch.
• Tree: connected subgraph with all nodes, no loops. Twigs = n-1.
• Co-tree (links) = b - n + 1. Each link creates one fundamental loop.
• Independent KCL = n-1. Independent KVL = b-n+1. Total = b (matches unknowns).
• Incidence matrix A entry: +1 (branch leaves node), -1 (branch enters node), 0 (not connected).
• KCL in matrix: A * I_b = 0. KVL in matrix: V_b = A^T * V_n.
• GATE trap: Do not confuse n (nodes including reference) with n-1 (independent equations). Always subtract 1 for the reference node.