Graph Types and Applications

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

This article will discuss the different Graphs types and their applications. Graphs are abstract, non-linear data structures that contain a set of vertices V = {V1, V2, V3, …} and a set of edges E = {E1, E2, E3, …}. A graph is formed when two vertices are connected via one or more edges. 

Types of graph

Finite Graph: A graph having a limited number of vertices and edges is called a Finite Graph.

Infinite Graph: A graph having an endless number of vertices and edges is called an Infinite Graph.
 

Trivial Graph: A graph containing only one vertex and no edges is called a Trivial Graph.
 

Simple Graph: A graph in which each pair of vertices has only one edge connecting them is called a Simple Graph. 

Multi Graph: A graph containing parallel edges and no self-loop is called a Multi Graph. It means that each pair of vertices can have one or more edges connecting them but no self-loops. 

Parallel Edges: If a pair of vertices has two or more edges, those edges are parallel edges. There are multiple routes between the source and destination vertex in such cases.

Loop: If the source and destination vertex of an edge is the same, then that condition is called a loop or self-loop.

Null Graph: A graph containing vertices and no edges is called a null graph. 

Complete Graph / Full Graph: A simple graph containing n vertices, where the degree of each vertex is (n-1), is called a Complete or Full Graph. 

Pseudo Graph: A graph containing a self-loop and multiple edges is called a Pseudo Graph.

Regular Graph: If all the vertices of a Simple Graph are of equal degree, then that graph is called Regular Graph. All complete graphs are regular, but the converse is not true.

Bipartite Graph: Consider a graph G = (V, E). If the vertex set V(G) of the graph can be divided into two non-empty disjoint subsets, V1(G) and V2(G), such that each edge of the set E(G) has one end in V1 and the other end in V2. Such a graph is called a Bipartite Graph. 

Labelled Graph: If the edges of a graph are labelled with some name, data, or weight, the graph is called a Labelled Graph.
 

Digraph Graph: Consider a graph G = (V, E) with a mapping f. If every edge of G maps onto some ordered pair of vertices (Vi, Vj), that graph is called Digraph Graph. They are also referred to as Directed Graph as the edges represent the direction of traversal from vertex Vi to vertex Vj.

Subgraph: Consider two graphs G = (V, E) and G1 = (V1, E1). If V1(G) is a subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has the same end vertices as in G then, G1(V1, E1) is a subgraph of G(V, E). Based on the intersection set, subgraphs are of two types:

→ Vertex Disjoint subgraph: Consider two subgraphs G1 = (V1, E1) and G2 = (V2, E2) and a graph G = (V, E). If the intersection set of V1(G1) and V2(G2) is null then, G1 and G2 are Vertex Disjoint subgraphs of G. It means that there are no common vertex between G1 and G2.  

→ Edge Disjoint subgraph: Consider two subgraphs G1 = (V1, E1) and G2 = (V2, E2) and a graph G = (V, E). If the intersection set of E1(G1) and E2(G2) is null then, G1 and G2 are Edge Disjoint subgraphs of G. It means that there are no common edges between G1 and G2.

Connected or Disconnected Graph: Consider a graph G = (V, E). If any pair of vertices (Vi, Vj) of graph G is reachable, G is a Connected Graph. In a connected graph, at least one edge/path exists between every pair of vertices
If there is no edge for at least one pair of vertices, the graph is called Disconnect Graph. A null graph with n number of vertices is called a Disconnected Graph consisting of n components.

Cyclic Graph: A graph G containing three more vertices such that the consecutive vertices {(V1, V2), (V2, V3), (V3, V4), ….. (Vn, V1)} form an edge between them, is called a Cyclic Graph

Applications of Graph

The various applications of Graphs are:

  1. In Computer Science: graphs are used to represent various data organizations, a network of communication, computational devices, etc.
  2. In Social Science: Graph Theory is widely used in sociology.
  3. In Biology: Graph theory is widely used in biology and conservation efforts.
  4. In Physics and Chemistry: Graph theory is used for studying molecules. 
  5. In Mathematics: graphs are used in geometry and topology (knot theory).

Frequently Asked Questions

  1. What do you mean by Graph Theory?
    Graph Theory is the study of relationships between various graphs. To know more, read this informative article, Graph Theory
     
  2. How to traverse in a graph?
    There are two primary graph traversal techniques- Breadth First Search(BFS) and Depth First Search(DFS). To know more on graph traversal visit, Graph Traversal.    

Key Takeaways

To summarize the article, we studied the various types of graphs in-depth and saw a few applications of graphs. We also addressed a few FAQs.

Want to crack various interviews but don’t know where to start? Visit Interview Preparation and start preparing today!

Are you a budding programmer and want to learn everything about Data Structures and Algorithms? Visit Data Structures and Algorithms to know everything about this paradigm. 


Happy Coding!

Was this article helpful ?
0 upvotes