Application of Graph Theory in 2023

Introduction

The era of graph theory began with Euler in the year 1735 to solve the well-known problem of the Königsberg Bridge.  In the modern age, graph theory is an integral component of computer science, artificial engineering, machine learning, deep learning, data science, and social networks.  Modern Applications of Graph Theory discusses many cutting-edge applications of graph theory, such as traffic networks, navigable networks and optimal routing for emergency response, and graph-theoretic approaches to molecular epidemiology.

What is Graph Theory? 

A graph G(V, E) is a non-linear data structure, which consists of pair of sets (V, E) where V is the non-empty set of vertices (points or nodes). E is the set of edges (lines or branches) such that there is a mapping f: E →V    i.e., from the set E to the set of ordered or unordered pairs of elements of V. The number of called the order of the graphs and the number of edges is called the size of graph G (V, E). 

Graphs are of three types Undirected Graphs, Directed graphs, and weighted graphs.

• Undirected graphs: In Undirected Graphs, the edges are associated with an unordered pair of vertices. A graph G (V, E) without a loop and parallel edges is called a simple graph. A graph that has more than one edge between any pair of vertices is called a multigraph. Again if any multigraph contains loops then the graph is a Pseudo graph. According to structure, there are different types of undirected graphs, such as Null graphs, complete graphs, Regular graphs, bipartite graphs, Cycles, Wheels, Eulerian graphs, and Hamiltonian graphs.
• Directed Graph: A directed or digraph graph G consists of a set V of vertices and a set E of edges such that eϵE is associated with an ordered pair of vertices i.e., each edge has a direction. There are different types of directed graphs. Symmetric directed graphs, simple directed graphs, complete directed graphs, quasi-transitive digraphs, and oriented graphs.
• Weighted Graphs: Many graphs can have edges containing a weight associated to represent real-world implications such as cost, distance, and quantity. Weighted graphs could be directed or undirected graphs.
• Trees are one of the most commonly used sub-categories of graphs. In computing, trees are useful for organizing and storing data in a database. A tree is a connected acyclic graphic with no cycle. A tree T with n vertices has n-1 edges. A subgraph T a connected graph G (V, E) is called a spanning tree if T is a tree and if includes every vertex of G. There are two algorithms a) BFS (Breadth-first search) and b) DFS (Depth-first Search) for constructing the spanning trees of a given undirected graph G. For weighted graphs one can construct the minimal spanning tree using Prim’s and Kruskal’s algorithm. The Binary trees having one vertex of degree two and the other vertices of degree one or degree three, are used to represent an algebraic expression and storage representation. Storage Representation of Binary tree has two ways a) Sequential representation and b) Link representation.

Ex. Use a binary tree to represent the expression ((a + b)* c) + (d/e)

How does Graph Theory Work?

Graph theory is ultimately about studying the relationships between different nodes (vertices) and connections (edges). The study of graphs across a structure provides answers to numerous problems in layout, networking, optimization, matching, and operation.

Graph Colouring Problems 

Graph coloring is one of the most useful techniques in which adjacent vertices obtain different colors. The minimum number of colors used for the correct coloring of the graph is our goal which is an optimization problem.

The problem of graph coloring has many applications, such as Making a Schedule or Time Table, Mobile Radio Frequency Assignment, Sudoku, Register Allocation, and Map Coloring.

Time Scheduling Problem 

Think about a specific semester; there are students taking each of the following combinations of topics. In this problem, our aim is to find the minimum number of examination days for scheduling the examination in the 8 subjects so that students taking any of the given combinations of the subject have no conflict.

In addition, find an available schedule using a minimum number of days.

Table: Combinations of Subjects

The outcome of the problem

Some Classical Problems of graph theory

• An old problem is to connect four houses H1, H2, H3, and H4 to three utilities each – water (W), gas (G), electricity (E), and TV cable line (C). Can each service be connected to each of the four houses without having two cross-connections between them?

• Travelling Salesman Problem:

Suppose that the territory of a seller includes several cities with highways linking some pairs of these cities. He should visit every city once. Graph theory can be useful in solving this transport system. The problem can be represented graphically by a graph G whose vertices correspond to the cities. The two vertices are joined by an edge if and only if a highway connects the corresponding cities. Starting at vertex a, the salesman can visit by taking the edges e1,e2, e3, e4, e5, and e6 and back to vertex a.

Algorithm for Modern Real-life application 

Google Maps

Google maps use graphs for construction and transport systems.  The intersection of two (or more) roads is considered a vertex, and the road connecting two vertices is considered an edge. Their navigation system then uses the algorithm to calculate the shortest path between two vertices.  In GPS we also use different shortest path algorithms such as DFS (Depth first search) and BFS (Breath first search) algorithm. By the Dijkstra algorithm, one can find the shortest route between a given node (source node) and all other nodes (destination node) in a graph. This algorithm uses edge weights to find a way to reduce the total distance (weight) between the source node and all other nodes.

Facebook and LinkedIn

Ever wonder how Facebook knows how a person is your mutual friend or how LinkedIn knows if a connection is a second or third one? Facebook and LinkedIn model their users as a graph in which each vertex is a user profile.  The edge between two persons is the fact that they are friends among themselves or follow one another. Facebook and LinkedIn Friend suggestion algorithm uses graph theory. Facebook is one example of an undirected graph. 

World Wide Web

On the World Wide Web, web pages are considered vertices. There is an edge between page ‘u’ and another page ‘v’ if there is a link from page ‘v’ to page ‘u’. That’s an example of a directed graph. That is the basic concept behind Google Page Rank Algorithm.

Social Network

On social networking sites, we use graphs to track user information. Liked showing preferred post suggestions, recommendations, etc. Thus, the development of algorithms to manage graphs is of great interest in the field of information technology.

Conclusion

Due to growing the application of Artificial Intelligence, Machine Learning, Deep Learning, Data Science, and Cryptography in various fields like Health Science, Social Science, Manufacturing Industry, Defence services, and different government activities, the graph theoretical approach, and its application is a very demanding subject for the researcher. After finishing the study of graph theory, students may be able to apply their knowledge of graph theory in various fields of modern science.