Graph Theory

Graph Theory is the study of the graph. A graph is determined as a mathematical structure which represents a particular function by connecting a set of points. 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. The graphs are basically of two types, directed and undirected. It is best understood by the figure given below.

Graph Theory

The arrow in the figure indicates the direction.

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 table, line graph, circle graph, line plot, etc.

Terms Used in Graph Theory

There are certain terms which 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 which 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 which has an even number of edges or vertices is called Even Cycle.
  • A cycle which 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 as a disassortative graph.
  • A cycle graph is said to be a graph which has a single cycle.
  • When all the pair 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 which 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.