Graph Theory

Graph Theory is the study of the graph. A graph is determined as a mathematical structure that represents a particular function by connecting a set of points. It is used to create a  pairwise relationship between objects. The graph is made up of vertices (nodes) that are connected by the edges (lines). The applications of the graph are used not only in Maths but also in other fields such as Computer Science, Physics and Chemistry, Linguistics, Biology, etc. In real-life also the best example of graph structure is GPS, where you can track the path or know the direction of the road.

History of Graph Theory

The history of graph theory states it was introduced by the famous Swiss mathematician named Leonhard Euler, to solve many mathematical problems by constructing graphs based on given data or a set of points. The graphical representation shows different types of data in the form of bar graphs, frequency tables, line graphs, circle graphs, line plots, etc.

Graph Theory Definition

Graph Theory is the study of points and lines. In Mathematics, it is a sub-field that deals with the study of graphs. It is a pictorial representation that represents the Mathematical truth. Graph theory is the study of relationship between the vertices (nodes) and edges (lines). Formally, a graph is defined as a pair (V, E).

Where V represents the finite set vertices and E represents the finite set edges.

Directed and Undirected Graph

The graphs are basically of two types, directed and undirected. It is best understood by the figure given below. The arrow in the figure indicates the direction.

Graph Theory

Directed Graph

In graph theory, a directed graph is a graph made up of a set of vertices connected by edges, in which the edges have a direction associated with them.

Undirected Graph

The undirected graph is defined as a graph where the set of nodes are connected together, in which all the edges are bidirectional. Sometimes, this type of graph is known as the undirected network.

Graph Theory Terms

There are certain terms that are used in graph representation such as Degree, Trees, Cycle, etc. Let us learn them in brief.

Trees

A tree in a graph is the connection between undirected networks which are having only one path between any two vertices. It was introduced by British mathematician Arthur Cayley in 1857. The graph trees have only straight lines between the nodes in any specific direction but do not have any cycles or loops. Therefore trees are the directed graph.

Degree

A degree in a graph is mentioned to be the number of edges connected to a vertex. It is denoted deg(v), where v is a vertex of the graph. So basically it the measure of the vertex.

Cycle

A cycle is a closed path in a graph that forms a loop. When the starting and ending point is the same in a graph that contains a set of vertices, then the cycle of the graph is formed. When there is no repetition of the vertex in a closed circuit, then the cycle is a simple cycle. The cycle graph is denoted by Cn.

  • A cycle that has an even number of edges or vertices is called Even Cycle.
  • A cycle that has an odd number of edges or vertices is called Odd Cycle.

Properties of Graph

  • The starting point of the network is known as root.
  • When the same types of nodes are connected to one another, then the graph is known as an assortative graph, else it is called a disassortative graph.
  • A cycle graph is said to be a graph that has a single cycle.
  • When all the pairs of nodes are connected by a single edge it forms a complete graph.
  • A graph is said to be in symmetry when each pair of vertices or nodes are connected in the same direction or in the reverse direction.
  • When a graph has a single graph, it is a path graph.

What is the Algorithm of Graph?

The procedure to draw a graph for any given function or to calculate any function is the algorithm of the graph. Basically, there are predefined steps or sets of instructions that have to be followed to solve a problem using graphical methods. There are different types of algorithms which the graph theory follows, such as;

  • Bellman-Ford algorithm
  • Borůvka’s algorithm
  • Ford–Fulkerson algorithm
  • Edmonds–Karp algorithm and many more.

Related Links

Download BYJU’S The learning App and learn to represent the mathematical equations in a graph.