International Journal of Mathematics Trends and Technology (IJMTT) - Volume 57 Issue 4- May 2018
Review of Applications of Graph Theory in
Engineering
1
S. N. Banasode, 2Y.M.Umathar.
1
. Department of Mathematics, R. L. Science Institute Belagavi, Karnataka, India.
2
Department of Mathematics, K.L.E.Technological University, Hubballi, Karnataka, India.
Abstract: The use of Mathematics is significant in every field of Engineering, like Computer Science engineering,
Networking, Electrical engineering, and many more That improves the effectiveness and applicability of existing
methods and algorithms. [3] Graphs are excellent mathematical tools that are used to model the various types of
relation between many physical circumstances. Most of the real world problem can be represented by graphs.
This paper explains the concepts of graph theory and its applications in different field of engineering, like
Network Engineering
Computer science engineering
Electrical Engineering etc
These applications demonstrate the objectives and importance of graph in Engineering. It explains the how the
graph can be used to model many engineering problems.
Key words: Graph, Connectivity, Path, Shortest path, Electronic circuit, Networking, truth Table, Link, Impendence
1. Introductions:
1.1. Graph theory is branch of mathematics that deals with the study of graph, that are considered to be the
mathematical structure helpful to have mathematical model with pair wise relation between objectives.
Graph is made up of two things. Set of vertices and set of edges Graphs give us many techniques and flexibility
while defining and solving real world problems. Graphs have many features such as,
Establishes relation between objects.
Helps in modeling
Helps in decision making.
As an example in networking Engineering, Network is system of points with distances between them. A network can
represent a road, pipeline, cables, etc. The problem with network involves finding the shortest path between one
point to another point in the network. [1]
2. Applications of graph in the various engineering field
2.1. Network Engineering: In [1] and [5] author have explained an application of graph in networking. In
addition to that, Graph theoretic concepts have many applications in network engineering, such as connectivity, data
gathering, Energy efficiency, traffic analysis, Finding shortest path and many more, where the term Graph and
Network are equivalent. In graph theory nodes and edges are used, in networking links and lines are
used. The term graph is used in mathematics and Network is used in Engineering. Particularly in
computer engineering.
Graph based representation for the network system makes the problem much easier and will provide much accurate
results.
2.1.1. Illustration: Graph representation of circuit network
Circuit network showing the Resistors in series and parallel
ISSN: 2231-5373 http://www.ijmttjournal.org Page 225
International Journal of Mathematics Trends and Technology (IJMTT) - Volume 57 Issue 4- May 2018
Figure 1
The logical truth table for the circuit can be shown as
𝑅1 𝑅2 𝑅3 𝑅4 𝑅5 𝑅6
𝑅1 0 1 1 1 0 1
𝑅2 1 0 1 1 1 0
𝑅3 1 1 0 0 1 1
𝑅4 1 1 0 0 1 1
𝑅5 0 1 1 1 0 1
𝑅6 1 0 1 1 1 0
Graph model that is used to represent circuit network
Figure 2
Again graph can be represented in one of the matrix form that is adjacency matrix taking the vertex set as
𝑉 = {𝑅1 , 𝑅2 , 𝑅3 , 𝑅4 , 𝑅5 , 𝑅6 }
0 1 1 1 0 1
1 0 1 1 1 0
𝐴= 1 1 0 0 1 1
1 1 0 0 1 1
0 1 1 1 0 1
1 0 1 1 1 0
From the adjacency matrix the energy of a graph, minimum dominating energy of a are defined. And the
energy of a graph is defined as absolute sum of the Eigen values of adjacency matrix of a graph. The characteristic
equation of adjacency matrix 𝐴 is
𝜆 1 1 1 0 1
1 𝜆 1 1 1 0
𝐴 − 𝜆𝐼 = 1 1 𝜆 0 1 1 = 0
1 1 0 𝜆 1 1
0 1 1 1 𝜆 1
1 0 1 1 1 𝜆
That is, the characteristic equation is 𝜆6 − 12𝜆4 − 16𝜆3 = 0 and eigen values are
ISSN: 2231-5373 http://www.ijmttjournal.org Page 226
International Journal of Mathematics Trends and Technology (IJMTT) - Volume 57 Issue 4- May 2018
𝜆 = 0, 0,0, −2, −2, 𝑎𝑛𝑑 4 . Therefore energy of a graph is
𝐸 𝐺 = 0 𝑡𝑟𝑒𝑒 𝑡𝑖𝑚𝑒𝑠 + −2 𝑡𝑤𝑜 𝑡𝑖𝑚𝑒𝑠 + 4 1 = 8
2.2. Electrical Engineering: Electrical Circuits are closed loop formed by Source, Wires, Load and Switches.
When switch is turned on electrical circuit is complete. Then current flows from negative terminal of source of
power. Here we apply the concept of Graph Theory to solve Electrical Circuit Problems. In [4] author have
discussed regarding an application of graph in electric circuits. Using the definition of a link and cycle matrix for the
graph, we consider one more application of graph in electric field.
2.2.1. Link: A branch of a graph which does not belongs to particular tree under consideration.
Figure 3
2.2.2. Cycle matrix (Loop matrix) : It is matrix with elements as 𝒃𝒊𝒋
1 𝐵𝑟𝑎𝑛𝑐 𝑏𝑗′ 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛 𝑖𝑛 𝑡𝑒 𝑙𝑜𝑜𝑝 𝑖𝑠 𝑠𝑎𝑚𝑒 𝑎𝑠 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑙𝑜𝑜𝑝
𝑏𝑖𝑗 = −1 𝐵𝑟𝑎𝑛𝑐 𝑏𝑗′ 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛 𝑖𝑛 𝑡𝑒 𝑙𝑜𝑜𝑝 𝑖𝑠 𝑜𝑝𝑝𝑜𝑠𝑖𝑡𝑒 𝑎𝑠 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑙𝑜𝑜𝑝
0 𝑊𝑒𝑛 𝑏𝑗 𝑖𝑠 𝑛𝑜𝑡 𝑖𝑛 𝑡𝑒 𝑙𝑜𝑜𝑝
Loop matrix is a 𝑖 × 𝑏 matrix where 𝑖 is the number of loops and 𝑏 is he number of branches. A set of
branches contained in a loop such that each loop contains one link and the remaining are the tree branches.
2.2.3. Illustration:
Figure 4
Selecting (2,4,5) as a tree and the co-tree is (1,3). For the above fig oriented cycle matrix (loop
1 1 0 −1 0
matrix) is 𝑀=𝐵=
0 1 1 0 −1
2.2.4. Impendence: Electric impendence is the measure of opposition that a circuit presents to a current when
voltage is applied.
Consider an electric circuit shown bellow, the graph for the circuit is shown.
Figure 5
ISSN: 2231-5373 http://www.ijmttjournal.org Page 227
International Journal of Mathematics Trends and Technology (IJMTT) - Volume 57 Issue 4- May 2018
Now we discuss the graphical method of finding branch currents
For the electric circuit shown in the figure 5, the graph for the circuit is shown.
Graph representing circuit Figure 6 Tree and Co-tre
𝑥 1 0 1 0 0 −1
The oriented cycle matrix is, 𝐵 = 𝑦 0 1 0 1 0 1
𝑧 0 0 −1 −1 1 0
If branch impendence matrix is denoted by 𝑍𝑏 , then (𝑖, 𝑗)𝑡 the elements of the matrix 𝑍𝑏 are defined as
𝑅𝑖 𝑓𝑜𝑟 𝑖 = 𝑗
𝑍𝑏 =
0 𝑓𝑜𝑟 𝑖 ≠ 𝑗
0.8 0.0 0.0 0.0 0.0 0.0
0.0 0.7 0.0 0.0 0.0 0. 0
0.0 0.0 2.0 0.0 0.0 0.0
⇒ Branch impendence matrix, 𝑍𝑏 =
0.0 0.0 0.0 3.0 0.0 0. 0
0.0 0.0 0.0 0.0 0.5 0.0
0.0 0.0 0.0 0.0 0.0 0.4
Then branch source voltage vector is obtained as the product of oriented cycle matrix and branch impendence
matrix, That is,
0.8 0 2 0 0 −4
𝐵𝑍𝑏 = 0 0.7 0 3 0 4 = 𝐸𝑔𝑏 (Say)
0 0 −2 −2 0.5 0
And the mess (loop) impendence matrix is defined as 𝐸𝑔𝑏 𝐵′
6.8 −4 −2
Therefore we get, 𝐸𝑔𝑏 𝐵′ = 𝐵𝑍𝑏 𝐵′ = −4 7.7 −3 = 𝑍𝑙 (𝑠𝑎𝑦)
−2 −3 5.5
Mess source voltage vector is given by 𝐵𝐸𝑏 which is obtained as the product of the matrix 𝐵
12
1 0 1 0 0 −1 0 12
0
And 𝐸𝑏 .That is 𝐵𝐸𝑏 = 0 1 0 1 0 1 = 0
0
0 0 −1 −1 1 0 0 0
0
𝑥
If 𝐼𝑙 represents the currents in the loops, then 𝐼𝑙 = 𝑦
𝑧
Loop equations are 𝑍𝑙 𝐼𝑙 = 𝐵𝐸𝑏
ISSN: 2231-5373 http://www.ijmttjournal.org Page 228
International Journal of Mathematics Trends and Technology (IJMTT) - Volume 57 Issue 4- May 2018
6.8 −4 −2 𝑥 12
⇒ −4 7.7 −3 𝑦 = 0
−2 −3 5.5 𝑧 0
⇒ 𝑥 = 6.672𝐴, 𝑦 = 5.602𝐴, 𝑧 = 5.482𝐴.
Hence proposed graph theoretical method can be applied to solve electrical circuit problems to branch
currents in the circuit.
2.3. Computer Science Engineering: Graph theory can be used in research areas of computer science. In [2]
[3] uses of graph in computer engineering are explained. Along with those few more application are explained.
Some of them are data structure, Image processing, Web designing, data mining, clustering, etc. Some of them are
discussed here.
2.3.1. Data structure: It is a systematic method of organizing and storing the data. It is designed to suit a
specific purpose so that it can be accessed and worked with appropriate ways. The selection of the model for the
data depends on the information of the real world and the structure should be simple enough that can effectively
process data whenever it is required.
2.3.2. Image processing: It is process of analysis and manipulation of digitized image, especially in order to
improve the quality of an image. It is a method by which the information from the image is extracted. Using graph
theory concept image processing method can be improved. The graph theory provides the calculation of alignment
of the picture. It finds the mathematical constraints using minimal spanning tree.
2.3.3. Web designing: Web designing is also method of creating the web site that encompasses several
different aspects including web page, layout, content production and graphic design. While the term web design and
web development are often used interchangeably. Web design is a subset of web development. Here web pages are
represented by the vertices and the links between the web pages are represented by the edges of the graph. In the
web community the vertices are representing the classes of objects and each vertex represents one nature of the
object and each vertex representing one type of object is connected to every vertex representing the other kind of the
object. In graph theory same concept is explained by complete bipartite graphs.
The concepts of weighted graph in graph theory, where weights have been assigned to the edges of the
graph are used to represent the structure, wherein the paired connections have numerical values. If the edges
represent the roads between the places then problem is to fond shortest path connecting all places which is solved by
minimum spanning tree. There are many methods of finding minimum spanning tree, the new and simple approach
that we propose is an Edge Elimination Method” is illustrated here.
Considering the weighted graph shown in the following figure
Figure 7 (weighted Graph)
The algorithm for the edge elimination method is
Step 1: The edge with highest weight from each smallest cycle is eliminated with care that graph is not
disconnected.
Step 2: step 1 repeated for the cycles formed after the step 1.
Step 3: Continue the process of elimination of edges of highest weight from each smallest cycle obtained in the step
2 using step 1, until no cycle remains in the graph. So that there are exactly (n-1) edges, n is the number of vertices.
The resulting graph is the minimum spanning tree as shown.
ISSN: 2231-5373 http://www.ijmttjournal.org Page 229
International Journal of Mathematics Trends and Technology (IJMTT) - Volume 57 Issue 4- May 2018
OR
Figure 8 (Minimum spanning tree of 37)
3. Conclusion: This paper is prepared to help the students of engineering to gain the depth knowledge of
graph theory and its relevance with other subject of engineering. In this paper we have focused on the application of
graph theory in few branches of engineering. We conclude that, this paper motivate not only the students of
engineering but also engineering faculty.
4. References:
1) B. Sadavare, R V Kulkarni, A Review of Application of Graph Theory for Network, International Journal of Computer science and
Information technologies, 3(6), 2012.
2) Ferozuddin Riaz, Khidir M Ali, Application of Graph Theory in Computer Science, 2011, International conference on Computational
Intelligence System and Network.
3) Rishi Pal Singh, Vandana, Application of Graph Theory in Computer Science and Engineering, 104(1), October 2014.
4) Samai’la Abdullah, An Application of Graph theory to the Electric Circuit Using Matrix Method, ISRO Journal of Mathematics, 10(2),Mar-
Apr 2014.
5) Suman Deswal and Anita Singhrova, Application of Graph Theory in Communication Networks, 1(2), October 2012.
ISSN: 2231-5373 http://www.ijmttjournal.org Page 230
