→ History
Graph Theory 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.
→ Introduction to Graph:
Graph is a discrete structure consisting of vertices and edges connecting the vertices.
• It is used to create a pairwise relationship between objects.
→ Definition of Graph Theory:
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.
• It is the study of relationship between the vertices (nodes) and edges (lines).
» Formally, a graph is denoted as a pair G(V, E).
Where V represents the finite set vertices and E represents the finite set edges.
• Therefore, we can say a graph includes non-empty set of vertices V and set of edges E.
Example
‣ Suppose, a Graph G=(V,E),
where Vertices, V={a,b,c,d}
Edges, E={{a,b},{a,c},{b,c},{c,d}}
Simple Graph:
A graph G(V,E) is said to be simple if G has no loops and no parallel edges.
Multigraph:
A graph will be known as a multi-graph if the same sets of vertices contain multiple edges. In this type of graph, we can form a minimum of one loop or more than one edge.
Directed Graph:
A directed graph, or digraph, is a graph in which the edges have a direction. This means that each edge points from one vertex to another vertex.
Undirected Graph:
An undirected graph, on the other hand, is a graph in which the edges do not have a direction. This means that each edge connects two vertices, but it does not matter which vertex the edge is pointing from.
