Graph definition in graph theory | what is graph meaning in Theory and Network Equations | Subgraph meaning in electronics

what is graph meaning in Theory and Network Equations | Subgraph meaning in electronics Graph definition in graph theory ?
Graph Theory and Network Equations
Graph Theory For a simple network, we can easily find the response of a network using kirchhoff’s laws. in case of more complicated network, the solution may be difficult, but solution can be obtained easily by using network topology, which deals with the study of these graphs. using f-cut set matrix, KUL equations are obtained and from the f-circuit matrix KVL equations are obtained.
Definitions
A linear graph is a collection of points known as nodes and line segments known as branches, the nodes being joined together by branches.
Whenever any electric network is replaced by its equivalent linear graph, voltage source and current source is replaced by linear internal impedances. an ideal voltage source is to be replaced by a short circuit and an ideal current source by an open circuit. e.g.,
The branches and nodes of the graph have been numbered.
Oriented Graph and Un-oriented Graph
The arrows on the branches indicate the orientation of the branches and the graph is known as oriented graph or directed graph.
When the directions of the current are given but the graph is without such current directions such a graph is called unoriented graph.
Planar Graph and Non-planar Graph
A planar graph is a graph drawn on a two-dimensional plane so that no two branches intersect at a point which is not a node.
A non-planar graph is graph drawn on a two-dimensional plane such that two or more branches intersect at a point other than node on a graph. e.g.,
Sub graph
A subgraph is a subset of branches and nodes of a graph. it is of two types,
(i) Proper sub graph if the subgraph contains branches and nodes less in number than those on the graph.
(ii) Improper subgraph if the graph contains all the nodes and some of the branches then a subgraph is known as improper subgraph, e.g.,
Path
A path is a improper subgraph such that at the terminating node only one branch is incident and at the remaining nodes, two branches are incident. e.g.,
Connected and Disconnected Graph
A graph is said to be connected when there exists atleast one path between any two nodes. otherwise it is called disconnected.
Loop
It is subgraph of a graph wherein at each node exactly two branches are incident. A loop in a graph has the following properties:
1. there is atleast two branches in a loop.
2. Having exactly two paths between any pair of nodes in loop.
3. The number of branches equals the number of nodes. e.g.,
Tree
Tree is defined as the set of branches with all nodes not forming any loop or closed path. A are having the following praperties :
1. Contains all the nodes on the graph.
2. the rank of tree is same as the rank of graph (n – 1)
3. tree does not contain any closed path.
4. there exists only one path between any pair of nodes.
5. tree contains (n – 1) branches if n are the nodes of the tree. e.g.,
Twig
Branches of tree are called twig. if there are n number of noces on a graph then the tree of a graph contains (n-1) twigs.
e.g., for first tree, i.e., fig. 7 (b) twigs are
T = {(3), (5), (6)}
For second tree i.e., fig. 7 (c) twigs are
T = {(1), (4), (6)}
Co-tree
A set of branches forming a complement of tree is called co-tree.
number of branches of a co-tree = b – (n – 1)
where, b = number of branches of graph n = number of nodes of a graph
Link
Branches of the co-tree are called link.
e.g., for first tree i.e., fig. 7 (b) linkes are
L = {(1),(2), (4)}
For second tree i.e., fig. 7 (c) links are
L = {(2), (3), (5)}
Incidence Matrix
The information regarding the incidence of branches at various nodes and their orientation with respect to the nodes are described in the form of a matrix known as incidence matrix.
e.g., for a graph
The incidence matrix is given below.
This incidence matrix represents complete incidence matrix. in complete incidence matrix, the summation of elements in any column results in zero value.
The order of the incidence matrix is n x b.
any one row of the complete incidence matrix can be obtained by algebraic manipulation of other rows.
Properties of Complete Incidence Matrix
The properties are as follows :
1. sum of the entries in any column is zero.
2. Determinant of a loop of complete incident matrix is always zero.
3. Rank of complete incidence matrix of a connected graph is (n – 1).
Reduced Incidence Matrix
When any one row from the complete incidence matrix is eliminated, then the matrix is called reduced incidence matrix or incidence matrix. it is denoted by A. the order of the reduced incidence matrix is always equals to (n – 1) x b.
e.g., the incidence matrix is given as
Re-arranging the incidence matrix by putting elements corresponding to twigs of tree first followed by the links, we have
AT = square matrix of the order (n-1) x (n-1) whose columns corresponds to the twigs of the tree.
AI = matrix of the order (n-1) x [b – (n-1)] whose columns corresponds to the links.
By writing incidence matrix of an oriented graph, we can calculate the number of possible trees of an oriented graph. the number of possible trees is given by
Trees = det {[A][A]T}
e.g., incidence matrix of a graph
det {[A][A]T} = 16
Thus, number of possible trees are 16.
Loop Matrix
A loop matrix is a matrix which gives the information about the interconnection of branches which constitutes loop. a loop matrix or circuit matrix is represented by BA , e.g.,
For this example, there are seven possible loops
loop 1 [1, 2, 4], loop 2 [1, 3, 4], loop 3 [1, 3, 2], loop 4 [1, 2, 3, 4], loop 5 [2, 3, 4], loop 6 [1, 2, 4, 3], loop 7 [3, 2, 4, 1].
For avoiding clustering of arrows it is desirable to list all the loops with ordered nodes.
The loop matrix
for the circuit matrix, BA = [BIJ]
where, bij = 1 if branch j is in loop i and their orientations coincide.
bij = – 1 if branch j is in loop i and their orientations do not coincide
bij = 0, if branch j is not in loop i.
The rank of the loop matrix or circuit matrix BA is [b – (n-1)].
Fundamental Circuit or Tie Set Matrix (B)
It is a subset of circuit matrix. it is represented by BF . there is a graph given. e.g.,
Firstly, select ant tree and remove its all links.
Now, replace each link one at a time, it will form a closed path or loop. these circuits are called fundamental circuits or f-circuits or tie-sets.
Now, form a matrix considering these loops branches.
For a graph with b branches and n nodes, the possible f-circuits are given by [b – (n-1)]. hence, number of f-circuits are equal to the number of links.
in f loop, matrix can be partitioned as
BF = [BT,BI]
BF = [BT, U]
Cut Set Matrix
Cut set is defined as minimum set of branches of a connected graph whose removal causes the graph to become unconnected into exactly two connected subgraphs, e.g.,
The given graph is
The possible cut sets of the given graph are
By taking these graphs into considering, we get the cut set matrix
The number of rows in QA matrix is much more than those in the incidence matrix. and the complete cut set matrix is normally not required for solution of networks.
Fundamental Cut set (or f-cut set) Matrix (Q)
A fundamental cut set of a graph is a set of one twig and links at a node. for a graph with n nodes, the number of possible fundamental cut sets is equals to the number of twig which is (n-1).
The orientation of an f-cut set is chosen as the orientation of the corresponding twig e.g.,
Fundamental cut set matrix for the given cut set matrix will be
Relationship between Branch Currents and Loop Currents
[IB] = [BTIL]
Where, [BT] = transpose fundamental circuit matrix [b]
[IB] = branch current matrix
[IL] = loop current matrix,
for this graph, branch currents can be expressed in terms of loop currents as
[IB] = [BT] [IL]
From the above equations, we can write
i1 = I1 – I2, i4 = I1
i2 = I2 – I3, i5 = I2
i3 = I1 – I3, i6 = I3
Thus, with the help of this relation, we can find out the branch current in terms of loop current.
Relationship between Branch Voltage and Node Voltage
[VB] = [QT] [VN]
Where, [VB] = branch voltage matrix
[QT] = transpose of fundamental cut set matrix
[VN] = node voltage matrix
Interrelation among Various Matrices
The three different types of matrices from the graph of a network are not independent matrices. these are interralated by some relation. the relations between them are as
(i) Relation between incidence matrices and loop matrices
AR BTF = 0
Writing these matrices in terms of their sub-matrices corresponding to twigs and links,
[AT, AL] [BTT/I] = 0
BTT = – AT-1 AL
This means that the columns of BT are a linear combination of the rows of AL.
(ii) Relation between Incidence matrices and f-cut set matrices
IT = – QLIL
QL = AA-1AL
IB = IT/IL
A = [AT/AL]
Thus, the rows of f-cut set matrix are a linear combination of incidence matrix.
The branch impedance matrix.
ZB = [1 0 0 /0 s 0.5s/0 0.5s 2s]
Z = [B] [ZB] [BT] = [1 + S – 1.5s/ – 1.5s 4s]
the network equilibrium equation on loop basis is
[Z] [IL] = [B] [VS] – [ZB] [IB]= [B] [VS]
[IS] = 0
Therefore,
[1 + s -1.5s/-1.5s 4s] [I1/I3] = [1 -1 0/0 1 1] [0 0 1]= [0 1]
Hence, the network equilibrium equations are
(1 + s) I1 – 1.5s I3 = 0
-1.5 I1 + 4sIS = 0
Node or KCL equilibrium equations
The KCL equilibrium equations are based on nodal analysis. these equations are given as
QYB QTVT = Q (IS – YB VS)
Y = QYB QT
I = Q(IS – YBVS)
YVT = I
(iii) Relation between f-loop and f-cut set
Relation between f-loop matrix and f-cut set matrix can be obtained from two relations
QL = – BTT
QL = AT-1AL
B FQFT = 0
Q FBFT = 0
This shows that the f-cut set and f-loop matrices are also orthogonal to each other.
Network equilibrium equations in matrix form
With the help of loop analysis and node analysis, we can obtain the equilibrium equations for a network.
Loop or mesh or KVL equilibrium equations
The KVL equilibrium equations
BZBBT LL = B (VS – ZBIS)
Z = BZB BT
E = B (VS – ZB IS)
ZIL = E
Where, B = f-circuit or tie set matrix of order
(b – n + 1) x b
ZB = branch impedance matrix of order b x b
IL = column matrix of loop currents of order (b – n + 1) x 1
VS = column matrix of voltage source of order b x 1
Z = loop impedance matrix or coefficient matrix of order (b – n + 1) x (b – n + 1)
Example 1. Draw the oriented graph for the circuit shown in figure. write the network eqquilibrium equations.
Sol. the directed graph of the above network
so, number of tree branches = number of nodes – 1
= 3 – 1 = 2
and number of links = b – n + 1
= 4 – 3 + 1 = 2
for the f-cut set, consider the following tree
by this tree, the possible fundamental cut set will be
now, the f-cut set matrix is formed as
f-cut set 1 2 3 4
Q = 2 -1 +1 +1 0
4 -1 +0 +1 +1
Q = [-1 1 1 0/1 0 1 1]
Where, Q = f-cut set matrix of order (n-1) x b
YB = branch admittance matrix of order b x b
VT = column matrix of tree branch voltages of order (n-1) x 1
IS = column matrix of branch input current sources of order b x1
VS = column matrix of branch input voltage source
Y = node admittance matrix of order (n-1) x (n-1)
I = column matrix of order (n-1) x 1 which represents algebraic sum of current sources.
Duality
The two networks are said to be dual network of each other if the mesh (loop) equations of given network are the node equations of other network.
Thus, dual networks are based on KVL and KCL. the dual networks can be drawn for AC as well as DC circuits as well as for resistances and impedances.
Applying KVL to the above circuit,
– I . R – L dt/dt – 1/c |I dt + V = 0
V = I . R + L dI/dt + 1/c |I . dt ………………(1)
Consider RLC paralle circuit shown in fig. 14 (b) by applying KCL.
I = IG + IC + IL
I = G . V + C dV/dt + 1/L | Vdt …………….(2)
The eqs. (1) and (2) are similar, the V of series circuit corresponds to I in the parallel RLC circuit.
Construction of Dual Networks
Mathematical Method
Applying KVL to the above circuit, we haven
e(t) = I (t) . R + L dt (t)/dt + 1/c | I (t) dt ……………….(1)
writing dual elements for each and every element in eq. (1), we have
I (T) = G .e (t) + C de(t)/dt + 1/L |e(t) dt …………………(2)
[Dual network constructed from Eq. (2)]
Graphical Method
Procedure for drawing dual networks
1. first identify independent loops in a given network.
2. place a non-zero node inside each independent loop and name them.
3. place a zero potential node (datum node) outside a given network.
4. if the element is exclusively in a mesh (1), then that element should be connected between datum node and node. (1) draw a dotted line from datum node to the node inside mesh through the element.
5. if the element is common between mesh (1) and mesh (2) then in dual network, that dual element should be connected between two nodes (1) and (2).
6. consider branch containing active source as a separate branch.
7. while travelling in a closed path, i.e., mesh in direction of loop current, if it is voltage rise then in the network the current source should be shown such that current flows towards node. if there is a voltage drop then current should be flown away from node in dual network.
The procedure for drawing dual network is as shown in below in figure.
Intro Exercise – 2
1. for any network having n nodes, number of trees possible for that network is
(a) 2n
(b) 22n
(c) n2
(d) nn-2
2. the number of equations to solve for V1 and value of V1 are respectively,
(a) 2, 18 v
(b) 2, 6 v
(c) 1, 6 v
(d) 1, 8 v
3. identify which of the following is not a tree of the graph shown in the figure
(a) begh
(b) defg
(c) adhg
(d) aegh
4. the number of trees possible in the graph shown below is
(a) 5
(b) 6
(c) 7
(d) 8
5. match the following list I with list II and select the correct answers using the codes given below the lists.
list I List II
A. Loop 1. link
B. Twig 2. node
C. mesh 3. cut-set
codes A B C
(a) 1 2 3
(b) 1 3 2
(c) 3 1 2
(d) 3 2 1
6. the tie set matrix gives the relation between
(a) branch currents and loop currents
(b) branch voltages and loop currents
(c) branch voltages and node currents
(d) none of the above
7. the cut set schedule gives the relation between
(a) branch currents and link currents
(b) branch voltages and tree branch voltages
(c) branch voltages and link voltages
(d) branch currents and tree currents
8. for a graph with n nodes and b branches total independent currents and total independent voltages are, respectively
(a) b,n
(b) b – 1, n-1
(c) b – n + 1, n
(d) b – n + 1, n – 1
9. the minimum number of equations required to analyze the circuit shown in the figure is
(a) 3
(b) 4
(c) 6
(d) 7
10. consider the following graphs :
non-planar graph(s) is/are
(a) 1 and 3
(b) 4 only
(c) 3 only
(d) 3 and 4
11. a graph has 6 nodes and 9 branches. the independent loops are
(a) 3
(b) 4
(c) 5
(d) 6
12. the incidence matrix of a graph is as given below
the number of possible trees are
(a) 11
(b) 14
(c) 16
(d) 8
13. the incidence matrix of a graph is as given below
14. for the graph shown in figure, the incidence matrix A is given by
15. in the following non-planar graph, number of independent loop equations are
(a) 8
(b) 12
(c) 7
(d) 5
16. relative to a given fixed tree of a network
(a) link currents form an independent set
(b) branch voltages form an independent set
(c) link voltage form an independent set
(d) branch currents form an independent set
17. a network of independent loops for a network with n nodes and b branches is
(a) n – 1
(b) b – n
(c) b – n + 1
(d) independent of the number of nodes
18. A network contains linear resistors and ideal voltage sources. if values of all the resistors are doubled, then the voltage across each resistor is
(a) halved
(b) doubled
(c) increased by four times
(d) not changed
19. in which of the following, the principle of graph theory cannot be applied?
(a) designing-printed circuit boards
(b) simulating electrical circuits
(c) simulating travelling salesmen problem
(d) none of the above
20. which of the following is not a dual of the other?
(a) G – R
(b) KCL – KVL
(c) CCVS – VCVS
(d) C dVC(T)/dt – L dll(t)/dt
21. the konigsberg bridge problem explains which of the following principles?
(a) electromagnetic induction
(b) graph theory
(c) superposition
(d) none of the above
22. which of the following is a correct representation of expression for a basic cut-set incidence matrix
(a) [CL] = [AL][AB]
(b) [CL] = [AL]-1[AB]
(c) [CL] = [AL][K]T
(d) [CL] = [AL][K]
23. Which of the following is required to form a basic loop?
(a) one link and two branches
(b) one link and one branch
(c) two links and one branch
(d) none of the above
24. which of the folowing showed that graph topology can be represented incidence matrices?
(a) lenz
(b) euler
(c) faraday
(d) kirchhoff
Answers with Solutions
1. (d)
number of possible trees of that network = (nn-2)
2. (d)
there are only two nodes in the network, number of equations to solve for VI is (number of nodes – 1) = (2 – 1) = 1
after reducing the figure,
REQ = 12||6||2
REQ = 3 , So (1, 18)
from the figure,
V1 – 60/7 + V1/3 = 0
3V1 – 180 + 7V1 = 0
10V1 = 180
V1 = 18 V
3. (c)
adhg form a closed path, so it is not a tree.
4. (d)
the number of trees possible in the graph is 8.
5. (c)
loop – cut-set
twig – link
mesh – node
6. (a)
tie-set matrix is to represent branch currents and loop currents
IB = BTIL
IB = Branch current
BT = transpose of tie-st matrix
IL = Loop current
7. (b)
cut-sat matrix is to repersent branch voltages and tree branch voltages
VB = QTVT
VB = branch voltages
QT = transpose of cut-set matrix
VT = tree branch voltages
8. (d)
for a graph,
total independent currents = number of links = b – n + 1
total independent voltages = number of tree branches = n – 1
(because one node out of n nodes is a reference node.
9. (b)
number of equations = b – n + 1
= 7 – 4 + 1 = 4
n = number of nodes
b = number of branches
10. (b)
fourth circuit cannot be drawn on plane, like these three circuits are
11. (b)
link = independent loop
I = b – (n – 1)
I = 9 – (6 – 1)
I = 9 – 5
I = 4
12. (b)
this is a complete incidence matrix because sum of every column is 0. number of possible trees, det [ARART]
13. (c)
with the help of incidence matrix, orientation of branches are
by inspection of incidence matrix
node 4 to node 1 (A, B, C)
node 1 to node 3 (B, C)
node 1 to node 2 (B, C)
node 2 to node 3 (B, C)
node 2 to node 4 (B,C)
node 3 to node 4 (C)
14. (a)
15. (d)
number of independent loop equations are
L = B – N + 1
L = 12 – 8 + 1
L = 5
16. (a, d)
link currents and branch voltages form an independent set.
17. (c)
the number of independent loops for a network
I = b- n + 1
b = branches
n = nodes
18. (d)
according to ohm’s law V/I ratio is constant R.
when r is doubled, current becomes half. hence, voltage across each resistor does not change.
19. (d)
the principle of graph theory can be applied to all the given options.
20. (c)
dual of CCVS is VCCS.
21. (b)
konigsberg bridge problem explains the principle of graph theory.
22. (c)
basic cut-set incidence matrix is [CL] = [AL][K]T
23. (a)
with the help of one link and two branches we can form a loop.
24. (d)
kirchhoff showed that graph topology can be represented by incidence matrices.