 Open Access
 Authors : Divya S, Pawan Bharadwaj
 Paper ID : IJERTV12IS100038
 Volume & Issue : Volume 12, Issue 10 (October 2023)
 Published (First Online): 28102023
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Graph Theoretic Analysis of Power Networks
Divya S1, Assistant Professor, Dept. of EEE, The National Institute of Engineering, Mysuru Pawan Bharadwaj2, Assistant Professor, Dept. of ECE, The National Institute of Engineering, Mysuru
ABSTRACT – The intensified interest in Graph Theory applied to the field of Power Engineering is due to its capability in predicting the behavior of electrical networks. A complex electrical network with many interconnected electrical elements and devices behaves differently to different inputs and its response which depends on various factors needs proper investigation. The use of Linear Graph Theory is significant in power system studies as it proves to be an excellent mathematical tool for deriving the representations of the electrical transmission network.
This paper presents the modelling of standard test system using graph theoretical concepts and thereby formulating network equations using different reference frames. The approach used provides an easy analytical solution if applied to bulky power networks in real time.
Keywords: Graph Theory, Power Systems, Modelling, Topology

INTRODUCTION
Graph Theory is a significant offshoot of Mathematics with wide range of applications in various domains [1]. Nowadays, Power Engineering and Graph theory combination has set a stage for the solution of large power networks. With the evolution of large, high speed digital computers there is a paradigm shift in the techniques used for solving large power networks. Digital computer solutions depend upon network equations formulated using graph theory.
The growing interest of Graph theory in Power Engineering is due to its application in the analysis and design of electrical networks for predicting its behaviour. A complex electrical network is an interconnection of various electrical elements or devices such as resistors, inductors, capacitors, power sources, diodes, transistors, power electronic switches, storage batteries, transformers, protective devices etc. The behaviour of these elements or devices depends on various factors like characteristics of each element in the network and their topology. i.e., how the elements are connected together in the network. These elements present in the network can be classified into different categories as oneport (two terminal elements) or multiport elements, passive or active elements, linear or nonlinear elements, lumped or distributed elements, time variant or time invariant elements, bilateral or unilateral elements, bipolar or unipolar elements, dependent or independent sources etc. In power system studies the electric transmission network with the interconnection of transmission lines, transformers, shunt reactors, Shunt capacitors can be modelled as a network of lumped, two terminal elements. Few potential applications of graph theory in power systems [2][3] which exist in the literature proves that linear graph theory can be an excellent and useful mathematical tool in deriving the representations of the electrical transmission network.
This paper presents the modelling of Standard Test System using graph theoretical concepts. Topological analysis of the electrical network is carried out to formulate network equations using different reference frames.
The paper is organized as follows. Section II reviews graph theory fundamentals. Elementary concepts of power system and standard test systems for modern power system analysis are discussed in Section III. Section IV presents the proposed network model formulation for a standard test system. Finally, Section V summarizes the work.

GRAPH THEORY FUNDAMENTALS
Graphs are useful in describing the topological properties of network. Network topology is a generalized approach in solving electric circuits which deals with the properties of a geometrical Figure which are unaffected when the Figure is physically distorted. The geometrical properties of a network are independent of the types of elements & their values. Each element in the network can be represented by line segments with dots at the ends, irrespective of its nature & value. The configuration thus obtained when all the elements in a network are replaced by lines with circles or dots at both ends is called the graph of the network.
The terminologies are used in network graph are as follows:
Branch: A line segment representing one network element or a combination of elements connected between two points is called a branch
Node: The point of intersection of two or more branches is called a node.
Degree of a Node: It indicates the number of branches incident to the node.
Tree: A tree is a subgraph of a graph without loops. A network can have several trees.
Twig: It is the branch of a tree
Chord: It is the branch of the graph that does not belong to a particular tree. It is also called link.
CoTree: The set of links removed to form a tree constitute a cotree.
Loop: Loop is the closed contour selected in a graph.
CutSet: It is the set of elements or branches of a graph that separates two main parts of a network.
Tie Set: Tie set is a set of branches contained in a loop. Each loop consists of a tree and a link
Incidence Matrix: Any directed graph can be described completely in a compact matrix form. Incidence matrix gives information about which branch is connected to which node.
If any row is deleted from a complete incident matrix the resulting matrix is called reduced incidence matrix.
Relation Between Twigs and Links:
The number of twigs on a tree is always one less than the number of nodes. In a graph with N nodes, the number of tree branches or twigs T is given by
T= N1 (1)
The number of links L is given by
L = B – T = B (N1) = BN + 1 (2)
where B represents total number of branches in a graph
A sample electrical network is shown below in Fig.1 with its directed graph in Fig.2.A graph may have many different trees. On such tree is given in Fig.3 with twigs and chords represented by bold and dotted lines respectively.
The complete incidence matrix [Ai] of Fig.4 is shown below.
The reduced incidence matrix is obtained after deleting node (4) such that 4th row is removed from the above matrix.
The reduced incidence matrix [A] of the Fig.4 is given below.
Branch and Node are also called Edge and Vertex respectively in graph theory. The two terminal electrical element represented by edge (ek) is associated with two edge variables edge voltage or cross variable vk(t) and edge current or through variable ik(t). These variables are directional, so every edge i.e, branch is assigned an arbitrary direction. In general, to analyse a network using graph theoretical principles, network variables are considered on voltage basis or on current basis.
The graph can be directed (oriented) or undirected, planar or nonplanar. A graph is said to be directed when all its nodes are named, all its branches are numbered and arbitrary orientations are assigned to the branches. The arbitrary orientation in the graph indicate the direction of branch currents.

POWER SYSTEMS AND STANDARD TEST SYSTEMS
Power system in general is a sophisticated system with a number of power stations of various types, interconnected by a system transmission lines & distribution network to supply different loads as per the consumer interest. Todays power networks are highly complicated with several buses interconnected by means of transmission lines. Power is injected int a bus from generators while the loads are tapped from it. In a power network there may be buses with only generators and no load or vice versa.
Different test systems, IEEE and CIGRE benchmarks have been used for power system analysis. These systems are available from small to large scale at various voltage and power levels. The benchmarks can be used for analysis of power system reliability, stability, protection, power quality, marketing, planning, observability, optimization etc. [4]
An overview of available standard test systems is given in the Table.1 below [4]
TABLE 1: AN OVERVIEW OF STANDARD TEST SYSTEMS 

TEST SYSTEM 
VOLTAGE (KV) 
AC/DC 
NUMBER OF BUSES 
NUMBER OF GENERATORS 
LOAD (MW, MVAR) 
COMMON APPLICATION 
TIME OF INTEREST FOR THE MOST COMMONLY USED APPLICATION 
IEEE 9 
13.8,16.5,18 and 230 
AC 
9 
3 
315, 115 
Stability 
From milliseconds to several seconds 
IEEE 14 
13.8,18 and 69 
AC 
14 
5 
259, 73.5 
State Estimation 

IEEE 30 
33,132 
AC 
30 
6 
283.4, 126.2 
Planning 
From a few hours to several years 
IEEE 39 
345 
AC 
39 
10 
6097, 1409 
Stability 
From milliseconds to several seconds 
IEEE 57 
138, 345 
AC 
57 
7 
1251, 336.4 
State Estimation 

IEEE 118 
138, 345 
AC 
118 
19 
3668, 1438 
Planning 
From a few hours to several years 
IEEE 300 
138, 230 and 345 
AC 
300 
69 
State Estimation 
IEEE RTS24 
230, 138 
AC 
24 
32 
3405, NA 
Reliability 
From a few minutes to several years 
RBTS 
230 
AC 
6 
11 
240, NA 
Reliability 
From several minutes to several years 
CIGRE B4 DC 
Â±400, Â±200,380 and 145 
DC 
7500, NA 
New Technologies 
From milliseconds to minutes 

CIGRE MV 
20 
AC 
14 
UTILITY 
43 
Control 
From milliseconds to seconds 
CIGRE LV 
0.4 
AC 
UTILITY 
New Technologies 
From milliseconds to minutes 

CIGRE 32 
130,220 and 400 
AC/dc 
74 
20 
11060, NA 
Control 
From milliseconds to seconds 
CIGRE HVDC 
345, 230 
DC 
2 
TWO UTILITY 
1000(BASE) 
Stability/Control 
From milliseconds to seconds 
NANot Applicable 
For power system studies of a real time large networks, it is essential to proceed systematically by first formulating the network model of the systems.
IV. NETWORK MODEL FORMULATION OF TEST SYSTEM
Standard IEEE 9 bus test system is considered for the application of graph theoretical concepts
. A single line diagram of the standard IEEE 9 bus test system is shown below in Fig.5. [4]
The geometrical interconnection of the elements of the network shown in Fig.5 is depicted in the Fig.6.below. Each bus is represented by a node and each element between buses i.e., transformer or transmission line is replaced by a single line segment.
Modelling of network elements:
In general, transmission lines are modelled by the nominal model with series impedance of the line as ZL= RL+ jXL and half line charging admittances as yc / 2. A transformer equivalent circuit will be a series impedance if shunt branch of the transformer is neglected. Between buses a transformer can be modelled as a line with admittance Yt =1/(Rt+ jXt ).The load at a particular ith bus can be modelled by an equivalent admittance YLi =( PLi jQLi ) /  Vi 2, where Vi is the ith bus voltage. Generators can be modelled as a voltage source or as a current source with generator admittance YG. Also any shunt element can be modelled as a line with admittance ysh.
Power networks are structured in such a way that out of m total number of nodes, one node is normally described by zero is always at ground potential and the remaining n = m 1 nodes are the buses. Considering the arbitrary directions, the oriented graph of the network shown in Fig.5 is given below with node v0 at ground potential.
The branchnode incidence matrix of the graph shown in Fig.7 is given below.
The bus incidence matrix Abi can be obtained by deleting the first row corresponding to reference node 0. The dimensions of Abi are (m1) x e, where e =12 & n= m1=9
The rows of matrix [Abi ] gives Kirchhoffs current law equations for example
i1 + i2 +i3 – i4 = 0 (3)
Similarly, for other rows KCL equations can be obtained. In matrix form,
[ Abi ] [ Ibr ] = 0 (4)where [Ibr] is a vector of branch currents of the order (12×1)
The branch voltages for the above network can be written as
Ve = [Abi ]T Ebus (5)
where Ve is a vector of branch voltages of the order 12×1 Ebus is a vector of node or bus voltages of the order 9×1.
The network equations derived from the above relation gives branch voltages in terms of the node voltages. For example,
V1= E1 (6)
V4 = E4 – E1 (7)
Different frames of reference can be considered to formulate the network equations of the above graph shown in Fig.7.
In Bus Frame of Reference there are n independent equations (n = no. of buses) relating the bus vectors of currents and voltages through the bus impedance matrix and bus admittance matrix
Ebus= Zbus Ibus (8)
Ibus = Ybus Ebus (9)
In Branch Frame of Reference there are b independent equations (b = no. of branches of a selected Tree of the system Graph) relating the branch vetors of currents and voltages through the branch impedance matrix and branch admittance matrix:
Ebr= Zbr Ibr (10)
Ibr = Ybr Ebr (11)
Similarly, in Loop Frame of Reference there are loop voltages & loop currents as vectors relating the impedance and admittance matrix.
Eloop= Zloop Iloop (12)
Iloop = Yloop Eloop (13)
Thus, using the network variables in any frame of reference the matrix pair [Y] and [Z] can be determined which forms the basis network models for power system studies.[5][6]
V. CONCLUSION
In this paper the application of graph theoretical principles in the analysis of a power network has been discussed. The modelling of Standard IEEE Test System is carried out using graph theoretical concepts. Matrix representation is obtained from the graph, using which relations between various parameters of the
network are analysed. The same approach can be applied to large scale power networks in real time to obtain a simple analytical solution.
REFERENCES
[1] Xie, Baozhuo, Chao Qi, Hongqi Ben, and Weixiong Yu. "The applications of graph theory in electric network." In 2019 International Conference on Sensing, Diagnostics, Prognostics, and Control (SDPC), pp. 780784. IEEE, 2019. [2] Kerur, Mr Prakash, and R. L. Chakrasali. "Graph Theory Algorithm to Find Minimum Cost Power Flow Path in Deregulated Scenario under Line Outage Contingency." International Journal of Applied Engineering Research 15, no. 7 (2020): 755761. [3] Saharuddin, Nur Zawani, Izham Zainal Abidin, Hazlie Mokhlis, Abdul Rahim Abdullah, and Kanendra Naidu. "A power system network splitting strategy based on contingency analysis." Energies 11, no. 2 (2018): 434. [4] Peyghami, Saeed, Pooya Davari, Mahmud FotuhiFiruzabad, and Frede Blaabjerg. "Standard test systems for modern power system analysis: An overview." IEEE Industrial Electronics Magazine 13, no. 4 (2019): 86105. [5] Sayeekumar, Nandhini, S. Prabhakar Karthikeyan, Sarat Kumar Sahoo, and I. Jacob Raglend. "Graph theory and its applications in power systemsa review." In 2015 International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT), pp. 154157. IEEE, 2015. [6] QuirÃ³sTortÃ³s, Jairo, and Vladimir Terzija. "A graph theory based new approach for power system restoration." In 2013 IEEE Grenoble Conference, pp. 16. IEEE, 2013.