Motilal Nehru National Institute of Technology Allahabad Prayagraj

EEN14104: Networks & Systems

Unit-I: Graph Theory

Presented
by
Dr. Arvind Kumar Prajapati

(Assistant Professor)

Electrical Engineering Department

 Introduction
❖ When the network is complicated and has a large number of nodes and closed
paths, network analysis can be done conveniently by using ‘ Network Topology’.
❖ This theory does not make any distinction between different types of physical
elements of the network but makes the study based on a geometric pattern of the
network. The basic elements of this theory are nodes, branches, loops and meshes.
Node: It is defined as a point at which two or more elements have a common
connection.
Branch: It is a line connecting a pair of nodes, the line representing a single element
or series connected elements.
Loop: Whenever there is more than one path between two nodes, there is a circuit or
loop.
Mesh: It is a loop which does not contain any other loops within it.

2
 Introduction
❖ A linear graph is a collection of nodes and branches.

❖ The nodes are joined together by branches. The graph of a network is drawn by first
marking the nodes and then joining these nodes by lines which correspond to the
network elements of each branch.

❖ All the voltage and current sources are replaced by their internal impedances. The
voltage sources are replaced by short circuits as their internal impedances are zero
whereas current sources are replaced by open circuits as their internal impedances
are infinite.

❖ Nodes and branches are numbered. Each branch of a graph may be given an
orientation or a direction with the help of an arrow head which represents the
assigned reference direction for current. Such a graph is then referred to as a
directed or oriented graph.
3
 Introduction
❖ Branches whose ends fall on a node are said to be incident at that node.

❖ Degree of a node is defined as the number of branches incident to it. Branches 2, 3

and 4 are incident at Node 2 in Fig. (c). Hence, the degree of Node 2 is 3.

4
 Definitions Associated with a Graph
1. Planar Graph
A graph drawn on a two-dimensional plane is said to be planar if two branches do not
intersect or cross at a point which is other than a node.

2. Non-planar
Graph A graph drawn on a two-dimensional plane is said to be non-planar if there is
intersection of two or more branches at another point which is not a node.

5
 Introduction
3. Sub-graph
It is a subset of branches and nodes of a graph. It is a proper sub-graph if it contains
branches and nodes less than those on a graph. A sub-graph can be just a node or only
one branch of the graph.

4. Connected Graph A graph is said to be connected if there exists a path between any
pair of nodes. Otherwise, the graph is disconnected.
5. Rank of a Graph If there are n nodes in a graph, the rank of the graph is (n − 1).
6. Loop or Circuit A loop is a connected sub-graph of a connected graph at each node
of which are incident exactly two branches. If two terminals of a path are made to
coincide, it will result in a loop or circuit.

6
 Introduction
Loops of a graph have the following properties:
1. There are at least two branches in a loop.
2. There are exactly two paths between any pair of nodes in a circuit.
3. The maximum number of possible branches is equal to the number of nodes.
7. Tree
❑ A tree is a set of branches with every node connected to every other node in such a way
that removal of any branch destroys this property and is not having any closed path.
❑ Alternately, a tree is defined as a connected sub-graph of a connected graph containing
all the nodes of the graph but not containing any loops. Branches of a tree are called
twigs.
❑ A tree contains (n − 1) twigs where n is the number of nodes in the graph.

No. of possible tree of a graph= |[𝐴𝑇 . 𝐴]| = |[𝐴. 𝐴𝑇 ]|

Where A is reduced incident matrix.

7
 Introduction
Trees have the following properties:
1. There exists only one path between any pair of nodes in a tree.
2. A tree contains all nodes of the graph.
3. If n is the number of nodes of the graph, there are (n − 1) branches in the tree.
4. Trees do not contain any loops.
5. Every connected graph has at least one tree.
6. The minimum terminal nodes in a tree are two.
8. Co-tree
Branches which are not on a tree are called links or chords. All links of a tree together
constitute the compliment of the corresponding tree and is called the co-tree. A co-tree
contains b − (n − 1) links where b is the number of branches of the graph.

In Fig. (b) and (c) the links are {2, 3, 6}

and {1, 4, 6} respectively.

8
 Graph Theory
Example 1: Draw directed graph of the networks shown in Fig.

9
 Graph Theory
Solution 1: For drawing the directed graph,

1. replace all resistors, inductors and capacitors by line segments,

2. replace the voltage source by a short-circuit,

3. assume directions of branch currents, and

4. number all the nodes and branches. The directed graph for the two networks are shown in Fig.

10
 Graph Theory
Example 2: Figure shows a graph of the network. Show all the trees of this graph.

11
 Graph Theory
Solution 2: A graph has many trees. A tree is a connected sub-graph of a connected graph
containing all the nodes of the graph but not containing any loops. Figure shows various trees of
the given graph.

12
 Incidence Matrix
Complete Incidence Matrix (𝑨𝒂 )
For a graph with n nodes and b branches, the complete incidence matrix is a rectangular matrix of
order 𝑛 × 𝑏. The most convenient way in which the incidence information can be given is in a
matrix form.
Elements of this matrix have the following values:
𝑨𝒊𝒋 = 1, if branch 𝑗 is incident at node 𝑖 and is oriented away from node 𝑖.
= −1, if branch 𝑗 is incident at node 𝑖 and is oriented towards node 𝑖.
= 0, if branch 𝑗 is not incident at node 𝑖.

It is seen from the matrix 𝑨𝒂 that the sum of the elements in any column is zero. Hence, any one
row of the complete incidence matrix can be obtained by the algebraic manipulation of other
rows.
13
 Incidence Matrix
Properties of Complete Incidence Matrix
Each row of the incidence matrix corresponds to a node of the graph and has nonzero entries, i.e.,
± 1 in all those columns of the branches which are associated with that node. The entries in all
other columns of that row are zero.
1. The sum of the entries in any column is zero. As every branch is associated with two nodes,
every column contains exactly two nonzero entries, one of which is +1 and the other –1.
2. The rank of the complete incidence matrix of a connected graph is (n – 1).
3. The determinant of the complete incidence matrix of a closed loop is zero.
4. The complete incidence matrix of the closed graph is a square matrix

14
 Graph Theory
Example: Draw the oriented graph from the complete incidence matrix Aa given below.

Answer

15
 Graph Theory
Reduced Incidence Matrix (A)
❑ The reduced incidence matrix A is obtained from the complete incidence matrix Aa by
eliminating one of the rows. It is also called incidence matrix. It is of order (n − 1) × b.
❑ When a tree is selected for the graph, the incidence matrix is obtained by arranging a
column such that the first (n − 1) column corresponds to twigs of the tree and the last b − (n
− 1) branches corresponds to the links of the selected tree.

Where 𝑨𝒕 the is twig matrix and 𝑨𝒍 is the link matrix

16
 Graph Theory
Example: Find number of possible trees of a Graph whose reduced incident matrix is given
below:

17
 Graph Theory
Solution:

Number of possible trees = |A . 𝐴𝑇 |

18
 Isomorphic Graph
❑ Two graphs are said to be isomorphic if they have the same complete incidence matrix.
❑ This requires that they have the same number of nodes and branches and that there be a
one-to-one correspondence between the nodes and a one-to-one correspondence between
the branches, in a particular way that leads to the same complete incidence matrix.

19
 Loop Matrix Or Circuit Matrix 𝑩𝒂
❑ When a graph is given, it is possible to tell which branches constitute which loop or circuit.
Alternately, if a loop matrix or circuit matrix is given, we can reconstruct the graph.
❑ For a graph having n nodes and b branches, the loop matrix 𝑩𝒂 is a rectangular matrix of
order b columns and as many rows as there are loops. Its elements have the following
values:
𝒃𝒊𝒋 = 1, if branch j is in loop i and their orientations coincide.
= − 1, if branch j is in loop i and their orientations do not coincide.
= 0, if branch j is not in loop i.

20
 Loop Matrix Or Circuit Matrix 𝑩𝒂
❑ A graph and its loops are shown in Fig.

All the loop currents are

assumed to be flowing
in a clockwise direction.

21
 Loop Matrix Or Circuit Matrix 𝑩𝒂
❑ A graph and its loops are shown in Fig.

All the loop currents are

assumed to be flowing
in a clockwise direction.

22
 Fundamental Circuit (Tieset) and Fundamental
Circuit Matrix
❑ When a graph is given, first select a tree and remove all the links. When a link is replaced,
a closed loop or circuit is formed. Circuits formed in this way are called fundamental
circuits or f-circuits or tiesets.
❑ Orientation of an f-circuit is given by the orientation of the connecting link. The number of
f-circuits is same as the number of links for a graph.
❑ In a graph having b branches and n nodes, the number of f-circuits or tiesets will be (b − n
+ 1).

Here, b = 6 and n = 4.
Number of tiesets = b − n + 1 = 6 − 4 + 1 = 3
23
Fundamental Circuit Matrix (Tieset Matrix )
❑ f

24
Fundamental Circuit Matrix (Tieset Matrix )

25
Orthogonal Relationship between Matrix A
and Matrix B
For a linear graph, if the columns of the two matrices 𝐴𝑎 and 𝐵𝑎 are arranged in the same
order, it can be shown that
𝐴𝑎 𝐵𝑎𝑇 = 0

Or 𝐵𝑎 𝐴𝑇𝑎 = 0

The above equations describe the orthogonal relationship between the matrices 𝐴𝑎 and 𝐵𝑎 .

If the reduced incidence matrix A and the f-circuit matrix B are written for the same tree, it can
be shown that
𝐴𝐵𝑇 = 0

Or 𝐵𝐴𝑇 = 0

These two equations show the orthogonal relationship between matrices A and B.

26
 Cutset Matrix 𝑄𝑎
❑ By removing a set of branches without affecting the nodes, two connected sub-graphs are
obtained and the original graph becomes unconnected. The removal of this set of branches
which results in cutting the graph into two parts are known as a cutset.

❑ By removing a set of branches without affecting the nodes, two connected sub-graphs are
obtained and the original graph becomes unconnected. The removal of this set of branches
which results in cutting the graph into two parts are known as a cutset. The cutset separates
the nodes of the graph into two groups, each being in one of the two groups.

❑ The cut-set is a minimal set of branches of the graph, removal of which cuts the graph into
two parts. It separates the nodes of the graph into two groups, each being in one of the two
parts.

❑ The cutset separates the nodes of the graph into two groups, each being in one of the two
groups.

❑ The orientation of a cutset is made to coincide with orientation of defining branch.

27
 Cutset Matrix 𝑄𝑎
❑ For a graph having n nodes and b branches, the cutset matrix 𝑄𝑎 is a rectangular matrix of
order b columns and as many rows as there are cutsets. Its elements have the following
values:

❑ 𝑞𝑖𝑗 = 1, if the branch j is in the cutset i and the orientation coincide.

= −1, if the branch j is in the cutset i and the orientations do not coincide.

= 0, if the branch j is not in the cutset i.

28
Cutset Matrix 𝑄𝑎

29
 Fundamental Cutset and Fundamental
Cutset Matrix
❑ When a graph is given, first select a tree and note down its twigs. When a twig is removed
from the tree, it separates a tree into two parts (one of the separated part may be an isolated
node). Now, all the branches connecting one part of the disconnected tree to the other along
with the twig removed, constitutes a cutset. This set of branches is called a fundamental
cutset or f-cutset.

❑ A matrix formed by these f-cutsets is called an f-cutset matrix.

❑ The orientation of the f-cutset is made to coincide with the orientation of the defining
branch, i.e., twig. The number of f-cutsets is the same as the number of twigs for a graph.

30
Fundamental Cutset and Fundamental
Cutset Matrix

31
 Fundamental Cutset and Fundamental
Cutset Matrix
The f-cutset matrix Q is rearranged so that the first (n − 1) columns correspond to twigs and b −
(n − 1) columns to links of the selected tree.

32
 Orthogonal Relationship between Matrix B and
Matrix Q
For a linear graph, if the columns of the two matrices 𝐵𝑎 and 𝑄𝑎 are arranged in the same
order, it can be shown that
𝑄𝑎 𝐵𝑎𝑇 = 0
Or 𝐵𝑎 𝑄𝑎𝑇 = 0
The above equations describe the orthogonal relationship between the matrices 𝐵𝑎 and 𝑄𝑎 .

If the f-circuit matrix B and the f-cutset matrix Q are written for the same selected tree, it can
be shown that
𝐵𝑄𝑇 = 0
Or 𝑄𝐵𝑇 = 0
These two equations show the orthogonal relationship between matrices B and Q.

33
Relationship Among Submatrices of A, B And Q
Arranging the columns of matrices A, B and Q with twigs for a given tree first and then the links,
we get the partitioned forms as

34
Relationship Among Submatrices of A, B And Q

35
Example
Example 1: For the circuit shown in Fig., draw the oriented graph and write the (a) incidence
matrix, (b) tieset matrix, and (c) f-cutset matrix.

36
Example
Solution: For drawing the oriented graph, 1. replace all resistors, inductors and capacitors by line
segments, 2. replace the voltage source by short circuit and the current source by an open circuit,
3. assume the directions of branch currents arbitrarily, and 4. number all the nodes and branches.

37
Example
Solution:

38
Example
Example 2: For the network shown in Fig., draw the oriented graph and write the (a) incidence
matrix, (b) tieset matrix, and (c) f-cutset matrix.

39
Example
Solution 2: For drawing the oriented graph, 1. replace all resistors, inductors and capacitors by
line segments, 2. replace the voltage source by short circuit and the current source by an open
circuit, 3. assume the directions of branch currents arbitrarily, and 4. number all the nodes and
branches.

(a) Incidence Matrix (A)

40
Example
Solution: (b) Tieset Matrix (B) The oriented graph, selected tree and tiesets are shown in Fig.

(c) f-cutset Matrix (Q) The oriented graph, selected tree and f-cutsets are shown in Fig.

41
Example
Example 3: The reduced incidence matrix of an oriented graph is

(a) Draw the graph. (b) How many trees are possible for this graph? (c) Write the tieset and cutset
matrices.

42
Example
Solution 3: (a) First, writing the complete incidence matrix Aa such that the sum of all the entries
in each column of Aa is zero, we have

43
Example
(c) Tieset Matrix (B) The oriented graph, selected tree and tiesets are shown in Fig.

f-cutset Matrix (Q) The oriented graph, selected tree and f-cutsets are shown in Fig.

44
45
Kirchhoff’s Voltage Law

46
 Kirchhoff’s Current Law

If one node is taken as reference node or datum node, we can write

47
Relation Between Branch Voltage Matrix 𝑉𝑏 , Twig
Voltage Matrix 𝑉𝑡 and Node Voltage Matrix 𝑉𝑛

48
Relation Between Branch Current Matrix 𝐼𝑏 and
Loop Current Matrix 𝐼𝑙

49
Network Equilibrium Equation
1. KVL Equation
If there is a voltage source 𝑣𝑠𝑘 in the branch k having impedance 𝑧𝑘 and carrying current 𝑗𝑘 , as
shown in Fig

50
Network Equilibrium Equation
1. KVL Equation
1. If there is a voltage source 𝑣𝑠𝑘 in the branch k having impedance 𝑧𝑘 and carrying current 𝑗𝑘 ,
as shown in Fig

51
Network Equilibrium Equation

52
Network Equilibrium Equation
2 KCL Equation

53
Network Equilibrium Equation
2 KCL Equation

54
Network Equilibrium Equation

55
Network Equilibrium Equation

56
Network Equilibrium Equation

57
Network Equilibrium Equation

58
Network Equilibrium Equation

59
Example
Example 1: Write the incidence matrix of the graph of Figure and express branch voltages in
terms of node voltages. Write the tieset matrix and express branch currents in terms of loop
currents.

60
Example
Solution 1

61
Example
Solution 1 (c) Tieset Matrix

62
Example
Example 2: Branch current and loop-current relationships are expressed in matrix form as

63
Example

64
Example
Example 3: For the network shown in Fig., write down the tieset matrix and obtain the network
equilibrium equation in matrix form using KVL. Calculate loop currents.

65
Example

66
Example

67
Example

68
Thanks…

69