Introduction

The era of graph theory began with Euler within the 12 months 1735 to resolve the well-known problem of the Königsberg Bridge.  In the trendy 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, corresponding to traffic networks, navigable networks and optimal routing for emergency response, and graph-theoretic approaches to molecular epidemiology.

What’s 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’s a mapping f: E →V    i.e., from the set E to the set of ordered or unordered pairs of elements of V. The variety of called the order of the graphs and the variety of edges is named the scale of graph G (V, E). 

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

• Undirected graphs: In Undirected Graphs, the perimeters are related to an unordered pair of vertices. A graph G (V, E) and not using a loop and parallel edges is named an easy graph. A graph that has multiple edge between any pair of vertices is named a multigraph. Again if any multigraph accommodates loops then the graph is a Pseudo graph. In line with structure, there are several types of undirected graphs, corresponding to 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 related to an ordered pair of vertices i.e., each edge has a direction. There are several types of directed graphs. Symmetric directed graphs, easy 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 corresponding to cost, distance, and quantity. Weighted graphs may very well be directed or undirected graphs.
• Trees are one of the 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 named 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 opposite 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 quite a few problems in layout, networking, optimization, matching, and operation.

Graph Colouring Problems 

Graph coloring is one of the useful techniques wherein adjoining vertices obtain different colours. The minimum variety of colours used for the right coloring of the graph is our goal which is an optimization problem.

The issue of graph coloring has many applications, corresponding to Making a Schedule or Time Table, Mobile Radio Frequency Project, Sudoku, Register Allocation, and Map Coloring.

Time Scheduling Problem 

Take into consideration a particular semester; there are students taking each of the next combos of topics. On this problem, our aim is to seek out the minimum variety of examination days for scheduling the examination within the 8 subjects in order that students taking any of the given combos of the topic don’t have any conflict.

As well as, find an available schedule using a minimum variety of days.

Table: Combos of Subjects

The end result of the issue

Some Classical Problems of graph theory

• An old problem is to attach 4 houses H1, H2, H3, and H4 to 3 utilities each – water (W), gas (G), electricity (E), and TV cable line (C). Can each service be connected to every of the 4 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 those cities. He should visit every city once. Graph theory will be useful in solving this transport system. The issue will be represented graphically by a graph G whose vertices correspond to the cities. The 2 vertices are joined by an edge if and provided that a highway connects the corresponding cities. Starting at vertex a, the salesperson can visit by taking the perimeters 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 taken into account a vertex, and the road connecting two vertices is taken into account 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 corresponding to 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 seek out a method to reduce the whole distance (weight) between the source node and all other nodes.

Facebook and LinkedIn

Ever wonder how Facebook knows how an individual 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 wherein each vertex is a user profile.  The sting between two individuals is the proven fact that they’re friends amongst themselves or follow each other. 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’s an edge between page ‘u’ and one other page ‘v’ if there may be a link from page ‘v’ to page ‘u’. That’s an example of a directed graph. That’s the fundamental concept behind Google Page Rank Algorithm.

Social Network

On social networking sites, we use graphs to trace user information. Liked showing preferred post suggestions, recommendations, etc. Thus, the event of algorithms to administer graphs is of great interest in the sector of knowledge technology.

Conclusion

Because of growing the applying 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 really demanding subject for the researcher. After ending the study of graph theory, students may give you the chance to use their knowledge of graph theory in various fields of recent science.