Incidence Matrix - Graph Theory For Electrical Networks

This is my second article on electrical network graphs. In previous article I explain how to draw a network graph. This article is related to incidence matrix (Aa) of a graph. An incidence matrix is a convenient way of expressing an oriented graph in form of matrix. The entities of Incidence matrix gives information about which branch is connected to which node and its orientation. If the incidence matrix is given then you can easily convert it into graph. The incidence matrix is helpful for evaluation of current flowing through each branch. The article is all about this.

Key Questions:

What is incidence matrix?
Properties of incidence matrix
Reduced incidence matrix
How to get an incidence matrix from a given graph?
How to draw a graph from a given incidence matrix?
How to get KCL equations from incidence matrix?
How to get KVL equations from Incidence matrix?

Incidence Matrix (Aa):

A directed graph can be expressed in a compact matrix form. The branches are connected with each other with the help of nodes. A directed branch connected to a node is called incidence. It represents the orientation of the branches and the number of branches incident to a node. The number of branches incident to a node is called degree of node. We can redraw the graph if the incidence matrix is given. It is the coefficient matrix of KCL equations. The complete set of incidence matrix is called augmented incidence matrix.

Properties of incidence matrix:

Algebraic sum of the column entries of an incidence matrix is zero.
The determinant of a closed loop is 0
The determinant of incidence matrix of a tree is +1/-1

Order of incidence matrix: If there are 'n’ nodes and 'b’ branches in a network graph, then incidence matrix have 'n’ rows and 'b’ columns. So order of the incidence matrix in nxb.

Elements of the incidence matrix:

If the matrix with n rows and b columns then each entry of the matrix is aij , where i is the number of row and j is the number of columns.

The element aij = 1, if the branch j incident at node i, and leaves away from node i
The element aij = -1, if the branch j incident at node j, and enters the node i
The element aij = 0, if branch j is not the part of node i

Reduced incidence matrix (A): When any one row is completely deleted from the matrix then this is called reduced incidence matrix. The order of this matrix is (n-1)xb. This reduction results from mathematical manipulation.

Example#1: Obtain incidence matrix of the following graph.

Fig 1 Example

The above graph contain 4 nodes and 7 branches. Let's start writing Incidence matrix by considering each node separately.

Node a: branches 1 and 5 are oriented away from node a and branch 3 is incident at node a

Node b: branches 6 and 7 are oriented away from node b and branches 1 and 4 incident at node b

Node c: branch 3 is oriented away from node c and branches 2,5 and 6 incident at node c

Node d: branches 2 and 4 are oriented away from node d and branch 7 is incident at node d

Order of matrix:
There are 4 nodes, so there will be 4 rows. There 7 branches, so there will be 7 columns. Order is 4x7

$\begin{bmatrix} +1 &0 & -1 &0 & +1 & 0 &0 \\ -1 &0 & 0 &-1 &0 & +1 &+1 \\ 0 &-1 &+ 1 &0 & -1 & -1 &0 \\ 0 &+1 & 0 & +1 & 0 & 0 & -1 \end{bmatrix}$

Fig 2 Incidence Matrix of the graph in Fig 1

Example#2: Obtain reduced incidence matrix from the augmented incidence matrix which is evaluated in the above example

$\begin{bmatrix} +1 &0 & -1 &0 & +1 & 0 &0 \\ -1 &0 & 0 &-1 &0 & +1 &+1 \\ 0 &-1 &+ 1 &0 & -1 & -1 &0 \\ 0 &+1 & 0 & +1 & 0 & 0 & -1 \end{bmatrix}\Rightarrow \begin{bmatrix} +1 &0 & -1 & 0 &+1 & 0 & 0\\ -1& 0 & 0 & -1 & 0 & +1 &+1 \\ 0 & -1 & +1 & 0 & -1 & -1 & 0 \end{bmatrix}$

Fig 3 Reduced Incidence Matrix

Example#3: Obtain network graph from the given incidence matrix.

$\begin{bmatrix} +1 & +1 & 0 & -1 & -1 & 0\\ 0&0 &+1 & 0 & +1 &0 \\ -1& -1 & 0 &0 & 0 &-1 \\ 0 & 0 &-1 & +1 & 0 & +1 \end{bmatrix}$

Fig 4 Incidence Matrix

Fig 5 Graph drawn from incidence matrix

How incidence matrix is helpful for determining KCL equations?

First of all we pick any one node as reference node. By picking a node as reference all of its elements becomes 0.

Label any node as datum/ground node while label the remaining node as a,b,c
Label the branches from 1 to b

Aai = 0

Where Aa is incidence matrix, it is the coefficient matrix of KCL equation. i is the branch current vector. There are 6 branches and we have to determine current through each branch.

From the given graph in fig 5 and incidence matrix in fig 4, evaluate KCL equations

Consider node d as a reference/ground node. So row 4 becomes 0.

Apply KCL at node a, node b and node c.

Aai = 0

$\begin{bmatrix} +1 & +1 & 0 & -1 & -1 & 0\\ 0 &0 &+1 & 0 & +1 & 0\\ -1& -1 & 0 & 0 & 0 & -1\\ 0& 0 & 0 & 0 & 0 & 0 \end{bmatrix}\cdot\begin{bmatrix} i_{1}\\ i_{2}\\ i_{3} \\ i_{4}\\ i_{5}\\ i_{6} \end{bmatrix}=0$

Fig 6

i1+i2-i4-i5= 0 equation 1

i5+i3 = 0 equation 2

i6+i4-i3= 0 equation 3

So there are (n-1) independent KCL equations. From above 3 equations evaluate branch currents.

i1 = i4 + i5 - i2

i2 = i4 + i5 - i1

i3 = - i5

i4 = i3 - i6

i6 = i3 - i4

How incidence matrix is helpful for determining KVL equations?

For determining branch voltages, consider anyone node as reference or ground node.

Label any node as datum/ground node while label the remaining node as a,b,c
Label the branches from 1 to b

v = AaT . e

Where v is the branch voltage vector, AaT is the transpose matrix of Incidence matrix Aa and e is the node voltages.

From the given graph in fig 5 and incidence matrix in fig 4, evaluate KVL equations

Fig 7 branch voltages

Select node d as reference node and all entries of row 4 becomes 0.

The network has 6 branches and 6 independent KVL equations

v = AaT . e

$\begin{bmatrix} v_{1}\\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \end{bmatrix} = \begin{bmatrix} 1 &0 & -1 &0 \\ 1 &0 &-1 &0 \\ 0& +1 &0 &-1 \\ -1 & 0 &0 &+1 \\ -1 & +1 & 0 &0 \\ 0& 0 & -1 & +1 \end{bmatrix}\cdot\begin{bmatrix} e_{a} \\ e_{b} \\ e_{c}\\ e_{d} \end{bmatrix}$

Fig 8

v1 = ea - ec equation 4

v2 = ea - ec equation 5

v3 = -eb equation 6

v4 = ea. equation 7

v5 = eb- ea equation 8

v6 = -ec. equation 9

You can write the above branch voltage equations either by using graph or by solving matrix multiplication.

Isomorphic Graphs:

If two graphs have same incidence matrix then they said to be isomorphic. If same incidence matrix it means that they have same number of nodes (rows) and branches (columns).