Graph Theory: Types of Graph
Mathematical representations of interactions between objects are called graphs, and the study of the features and uses of these representations is known as graph theory. Graphs consist of vertices or nodes, which represent objects, and edges or arcs, which represent relationships between those objects. Graphs are used in various fields such as computer science, social sciences, biology, and transportation, to model and analyze complex systems.
Graph: A graph is an ordered pair G=<V,E> of two sets V(vertices) and E(edges) satisfying the following conditions:
I) V is a finite non-empty set
II) Each edge e belongs E corresponds to unordered pair v1,v2 of elements of V
There are several types of graphs in graph theory, each with its unique characteristics and applications. Let’s explore some of the commonly used types of graphs:
Null Graph:
A graph with no edges is called a null graph.
Simple Graph:
A graph with no loops and multiple edges is called a simple graph.
Loop- If an edge starts and ends in same vertex, it is called loop or self loop
Multiple edges- If two edges have same starting vertex and same end vertex, they are called as multiple edges
Undirected Graphs:
An undirected graph is a graph in which the edges have no direction, and the relationship between vertices is symmetric. This means that if there is an edge between vertices A and B, there is also an edge between vertices B and A. Undirected graphs are used to represent relationships that are bidirectional, such as social networks, where friendships or connections between people are mutual.
Directed Graphs:
A directed graph, also known as a digraph, is a graph in which the edges have a direction, indicating a one-way relationship between vertices. This means that if there is an edge from vertex A to vertex B, there is no necessary edge from vertex B to vertex A. Directed graphs are used to represent relationships that are not necessarily symmetric, such as internet webpages with hyperlinks or transportation networks with one-way streets.
Weighted Graphs:
A weighted graph is a graph in which the edges have weights or values assigned to them, representing the strength or cost of the relationship between vertices. These weights can represent various quantities, such as distances, costs, or probabilities.
Cyclic Graphs:
A cyclic graph is a graph that contains at least one cycle, which is a closed path of edges that starts and ends at the same vertex. In other words, it is possible to follow a sequence of edges in the graph and return to the starting vertex without retracing any edge.
Acyclic Graphs:
An acyclic graph is a graph that does not contain any cycles.
Complete Graphs:
A complete graph is a graph in which there is an edge between every pair of distinct vertices. In other words, every vertex is directly connected to every other vertex. Here the degree of each node is one less than the number of nodes in the graph.
Regular Graphs:
A graph whose all the vertices have the same degree. It is a simple graph.
Bipartite Graphs:
A bipartite graph is a graph in which the vertices can be partitioned into two disjoint sets, such that every edge connects a vertex from one set to a vertex from the other set.
Complete Bipartite Graph:
It is a bipartite graph where every vertex of the first set is connected to every vertex of the second set.
Let’s check your understanding
Question 1: If a graph has 5 nodes, then in a complete graph, degree of each node is?
a) 2
b) 3
c) 4
d) 5
Answer: c (Since number of nodes is 5 then degree of each node is 1 liss than the number of nodes)
Question 2: A simple graph can be defined as
a) A graph with no loop and no multiple edges
b) A graph with loop and no multiple edges
c) A graph with no loop and multiple edges
d) A graph with loop and multiple edges
Answer: a
Question 3: A graph in which the edges have weights or values assigned to them is
a) Bipartite Graph
b) Weighted Graph
c) Planar Graph
d) Simple Graph
Answer: b
Question 4: Number of edges in a null graph is
a) 0
b) 1
c) 2
d) 3
Answer: a
Question 5: Number of edges required to make the below Bipartite graph into complete Bipartite graph is
a) 4
b) 3
c) 2
d) 0
Answer: b
Acknowledgement:
Thank you Dr. Rekha Sharma, Associate Professor Department of computer engineering, Thakur College of Engineering and Technology for your valuable support and guidance in helping me create a blog on Types of Graph. Your expertise and knowledge in the field have been instrumental in shaping my understanding of this topic. Your feedback and suggestions were instrumental in shaping the structure and content of the blog.
References:
https://www.javatpoint.com/graph-theory-types-of-graphs
https://www.geeksforgeeks.org/graph-types-and-applications/
https://hyperskill.org/learn/step/5645
https://en.wikipedia.org/wiki/Directed_graph
Hashtags:
#GraphTheory #Typesofgraph #dataStructures #computationcomplexity #Graphs