Graph Theory

Graph Theory is the study of graphs in discrete mathematics. A graph is referred to as a mathematical structure that connects a group of points to express a specific function. It’s used to link objects together in a paired relationship.

The graph is made up of vertices (nodes) and edges (connections) (lines). The linear graph has applications not only in mathematics, but also in computer science, physics and chemistry, linguistics, biology, and other sciences. The best illustration of graph structure in real life is GPS, which allows you to track a path or determine the direction of travel.

The Graph

A graph is a visual representation of any data in an organized fashion in mathematics. The graph portrays the relationship between two variables. In graph theory, a graph is a collection of objects that are connected in some way. The objects are essentially mathematical notions that are represented by vertices or nodes, with edges expressing the relationship between the nodes.

History of Graph theory

According to the history of graph theory, it was invented by Leonhard Euler, a great Swiss mathematician, to answer numerous mathematical problems by generating graphs from provided data or a set of points. Bar graphs, frequency tables, line graphs, circle graphs, line plots, and other graphical representations are used to display various sorts of data.

Definition

The study of points and lines is known as graph theory. It is a branch of mathematics concerned with the study of graphs. It is a visual depiction of mathematical truth. The study of the relationships between vertices (nodes) and edges is known as graph theory (lines). A graph is officially referred to as a pair G. (V, E). The finite set vertices are represented by V, and the finite set edges are represented by E.As a result, a graph has a non-empty set of vertices V and a set of edges E.

Types

There are two sorts of graphs: directed and undirected. The diagram below will help you understand it better. The direction is shown by the arrow in the figure.

• Directed Graphs

A directed graph is a graph made up of a set of vertices connected by edges, each of which has a direction associated with it in graph theory.

• Undirected Graphs

The undirected graph is a graph in which all of the edges are bidirectional and all of the nodes are connected together. This form of a graph is also referred to as an undirected network.

Graphs of other kinds:

1. A graph with no edges is known as a null graph.
2. An undirected graph with no loops or numerous edges is referred to as a simple graph.
3. A graph containing several edges connecting the same set of vertices is known as a multigraph. It’s made up of loops.
4. A graph with any two vertices connected by a path is known as a connected graph.
5. A network in which any two vertices or nodes are connected by a path is known as an unconnected graph.
6. A graph that completes a cycle is known as a cycle graph.
7. Complete Graph: A complete graph is one in which each pair of vertices is connected by an edge.
8. Planar graph: A planar graph is one in which no two edges of a graph overlap and all of the vertices and edges are represented in a single plane.

Properties of Graphs:

1. Root refers to the network’s starting point.
2. When nodes of the same kind are connected to one another, the graph is referred to as an assortative graph; otherwise, it is referred to as a disassortative graph.
3. A single-cycle graph is referred to as a cycle graph.
4. A full graph is formed when all pairs of nodes are connected by a single edge.
5. When each pair of vertices or nodes in a graph is connected in the same or opposite direction, it is said to be in symmetry.
6. It’s a path graph when a graph only contains one graph.

Cycle, Trees, and Degrees of Graphs

Certain words in graph representation are utilized, such as Degree, Trees, Cycle, and so on. Let’s have a quick look at them.

• A cycle in a graph is a closed path that forms a loop. When the starting and ending points of a graph with a set of vertices are the same, the graph’s cycle is established. When the vertex in a closed circuit does not repeat, the cycle is called a simple cycle. Cn is the symbol for the cycle graph.

1. Even Cycle is a cycle with an even number of edges or vertices.
2. Odd Cycle refers to a cycle with an odd number of edges or vertices.

• Trees: In a graph, a tree is a connection between undirected networks with only one path connecting any two vertices. There are no cycles or loops in the graph trees; only straight lines connect the nodes in any direction. As a result, trees are directed graphs.
• The number of edges linked to a vertex is referred to as a degree in a graph. It’s written as deg(v), where v is a graph vertex. In a nutshell, it’s the vertex’s measurement. 

Algorithm of Graph Theory:

The algorithm of the graph is the technique for drawing a graph for any given function or calculating any function. To solve an issue using graphical approaches, there are preset steps or sets of instructions that must be followed. The graph theory employs a variety of algorithms, including the following:

• The Bellman-Ford algorithm was developed by Bellman and Ford.
• Borvka’s algorithm, Ford–algorithm, Fulkerson’s Edmonds–algorithm, Karp’s, and many others are among them.

Conclusion

This article has sufficiently provided information regarding the graph theory and its properties. There are various algorithms for graph theory of which the Bellman-Ford algorithm is the most crucial. There is a long mathematical history associated with the graph theory which has been enlightened in this article proficiently.