Exams
Test Series
Previous Year Papers
Syllabus
Books
Cut Off
Latest Updates
Eligibility
Types of Graphs in Graph Theory: Subgraphs, Properties & Examples
IMPORTANT LINKS
A graph is a way to show how things are connected using points (called vertices) and lines (called edges). It helps us understand relationships between pairs of objects. Graphs are often used in subjects like math, computer science, and networks to show how different items are linked.
What is a Graph?
A graph is a simple way to show how things are connected to each other. It is made up of two main parts: vertices (also called nodes or points) and edges (also called links or lines). Each vertex represents an object or item, and each edge shows a connection or relationship between two of these objects.
Maths Notes Free PDFs
| Topic | PDF Link |
|---|---|
| Class 12 Maths Important Topics Free Notes PDF | Download PDF |
| Class 10, 11 Mathematics Study Notes | Download PDF |
| Most Asked Maths Questions in Exams | Download PDF |
| Increasing and Decreasing Function in Maths | Download PDF |
For example, if we think of cities as vertices, then roads connecting them can be edges. In a graph, we draw the vertices as dots or circles, and the edges as straight or curved lines connecting the dots.
Graphs are useful in many areas such as computer science, networking, social media, and transportation. They help us understand relationships, plan routes, or even find the shortest path between two points.
Graphs are studied in discrete mathematics.
Edges are also called nodes or points and vertices are also called link or line.
Here the points marked with numbers 1, 2 and so on are the vertices or nodes and the line joining these nodes are the edges.
In the above graph, we can see that the edges and vertices are labeled.
What are Types of Graphs in Graph Theory?
The various types of graphs in Graph Theory are as follows:
- Directed Graph
- Undirected Graph
- Null Graph in Graph
- Trivial Graph in Graph
- Simple Graph in Graph
- Complete Graph in Graph
- Connected Graph in Graph
- Disconnected Graph in Graph
- Regular Graph in Graph
- Cyclic Graph in Graph
- Acyclic Graph in Graph
- Bipartite Graph in Graph
- Complete Bipartite Graph
- Weighted Graph in Graph
- Multi-Graph in Graph
- Planar Graph in Graph
- Non-Planar Graph in Graph
Directed Graph in Graph Theory
A graph whose all edges are directed by arrows is known as a directed graph. They are also known as digraphs.
In the above image, we can see a directed graph where all the edges are directed in a certain direction.
- 3 Live Test
- 163 Class XI Chapter Tests
- 157 Class XII Chapter Tests
Undirected Graph in Graph Theory
A graph whose edges are not directed by arrows is known as an undirected graph.
In the above image, we see an undirected graph as its edges are not marked by arrows.
Null Graph in Graph Theory
A graph in which there are no edges between its vertices is known as a null graph. It is also called an empty graph. A null graph with n number of vertices is denoted by Nn.
In the above image, three different null graphs are shown.
Trivial Graph in Graph Theory
A graph with only one vertex is known as a trivial graph.
In the above image, we see only one node and edges arising from it, thus it is a trivial graph.
Simple Graph in Graph Theory
A graph that is undirected and has no parallel edges or loops is known as a simple graph.
A simple graph with n vertices has the degree of every vertex is at most n-1.
In the above image, we can see the difference between a simple and not a simple graph.
Complete Graph in Graph Theory
A graph in which every pair of vertices is joined by only one edge is called a complete graph. It contains all the possible edges.
A complete graph with n number of vertices contains exactly
nC2edges and is represented by Kn.
In the above image we see that each vertex in the graph is connected with all the remaining vertices through exactly one edge hence both graphs are complete graphs.
Connected Graph in Graph Theory
A connected graph is a graph where we can visit from any one vertex to any other vertex. In a connected graph, there is at least one edge or path that exists between every pair of vertices.
In the above image we can traverse from any one vertex to any other vertex; it is a connected graph.
Disconnected Graph in Graph Theory
A disconnected graph is a graph in which no path exists between every pair of vertices.
In the above image we see disconnected graphs.
Regular Graph in Graph Theory
A Regular graph is a graph in which the degree of all the vertices is the same. If the degree of all the vertices is k, then it is called a k-regular graph.
In the above image all the vertices have degree 2 and thus it is a 2-regular graph.
Cyclic Graph in Graph Theory
A graph with n vertices and n edges forming a cycle of n with all its edges is known as cycle graph. Any graph containing at least one cycle in it is known as a cyclic graph.
In the above image the graph contains two cycles in it hence it is a cyclic graph.
Acyclic Graph in Graph Theory
A graph that does not contain any cycle in it is called an acyclic graph.
In the above image the graph does not contain any cycle and thus it is an acyclic graph.
Bipartite Graph in Graph Theory
A bipartite graph is a type of graph in which the vertex set can be partitioned into two sets such that the edges only go between sets and not within them.
In the above image we see a bipartite graph.
Complete Bipartite Graph in Graph Theory
A complete bipartite graph is a type of bipartite graph in which each vertex in the first set is joined to each vertex in the second set by only one edge.
We can say that a complete bipartite graph is the combination of a complete graph and a bipartite graph.
In the above image we see a complete bipartite graph.
Weighted Graph in Graph Theory
A graph whose edges have been labeled with some weights or numbers is known as a weighted graph. The length of a path in a weighted graph is the sum of the weights of all the edges labeled in the path.
In the above image we see a weighted graph where all the edges are labeled with a number.
Multi-Graph in Graph Theory
A graph in which there is more than one edge between any pair of vertices is called a multi-graph. In other words, if there is a loop in a graph then it is a multi-graph.
In the above image vertex B and C are connected with two edges and similarly vertex E and F are connected with 3 edges. Hence it is a multi-graph.
Non-Planar Graph in Graph Theory
A graph that cannot be drawn without at least one pair of its crossing edges is known as a non-planar graph.
In the above image a non-planar graph is shown.
Types of Subgraphs in Graph Theory
A subgraph G of a graph is graph G’ whose vertex set and edge set subsets of the graph G. In simple words a graph is said to be a subgraph if it is a part of another graph.
In the above image the graphs
H1,H2,andH3are different subgraphs of graph G.
There are 2 different types of subgraph:
Vertex Disjoint in Graph Theory
A subgraph with no common vertex is called a vertex disjoint subgraph of the parent graph G. Since the vertices in a vertex disjoint graph cannot have a common edge, a vertex disjoint subgraph will always be an edge-disjoint subgraph.
In the above image the vertex disjoint subgraphs have no vertices in common between them.
Edge Disjoint in Graph Theory
A subgraph with no common edge is called an edge-disjoint subgraph of graph G.
On considering the above example we see that the edge-disjoint subgraphs have no edges in common between them but they may have common vertices.
Properties of Graphs in Graph Theory
The properties related to a graph are listed below.
- Distance between two vertices is basically the number of edges in the shortest path between vertex X and vertex Y. The distance between two vertices is denoted by d(X, Y).
- Eccentricity of a vertex is the maximum distance between one vertex to all other vertices. It is represented as e(V).
- Radius of a connected graph is the minimum eccentricity from all the vertices. It is represented as r(G).
- Diameter of a graph is the maximum eccentricity from all the vertices of the graph. It is represented as d(G).
- If the eccentricity of the graph is equal to its radius then it is known as the central point of the graph.
- The set of all the central point of a graph is known as the center of the graph
- The total number of edges in the longest cycle of graph G is known as the circumference of the graph G.
- The total number of edges in the shortest cycle of graph G is known as girth. It is represented as g(G).
Trees, Degree, and Cycle in Graphs
In graph theory, some common terms like Trees, Degree, and Cycle help us describe and understand graphs better. Let’s go through them one by one:
Trees:
A tree is a type of graph that connects different points (called vertices) in such a way that there is only one path between any two points. It doesn’t have any loops or cycles. Trees were first introduced by a British mathematician named Arthur Cayley in 1857. In simple words, it’s a connected graph without any round paths or circles.
Degree:
The degree of a vertex means how many edges (lines) are connected to that point. It shows how many direct connections a point has. It is written as deg(v), where v is the vertex.
Cycle:
A cycle is a path in a graph that starts and ends at the same point and forms a loop. If no point (vertex) is repeated in that loop, except the first and last one, then it is called a simple cycle. A cycle graph is shown as Cn, where n is the number of points.
- A cycle with an even number of edges or vertices is called an Even Cycle.
- A cycle with an odd number of edges or vertices is called an Odd Cycle.
Graph Theory Algorithm
- An algorithm is a set of clearly defined steps that we follow to find the answer to a problem. In simple terms, they are a group of instructions used to solve a problem using graphical techniques. There are many types of algorithms, some of which are listed below.
Bellman-Ford algorithm
Borůvka’s algorithm
Ford–Fulkerson algorithm
Edmonds–Karp algorithm and many more.
Advantages of Graphs
- Show Complex Relationships: Graphs help us understand and study complicated systems and how different parts are connected.
- Easy to Visualize Data: They make it easier to see patterns, trends, and connections in information.
- Useful in Many Fields: Graphs are used in computer science, social media analysis, transport systems, and more.
- Flexible Usage: You can use graphs to represent different kinds of data, like roads, friendships, or websites.
Disadvantages of Graphs
- Hard to Read When Big: Very large graphs can be messy and hard to understand.
- Takes Time to Analyze: Some graph-related calculations take a lot of computer power and time.
- Needs Expert Understanding: You may need specific knowledge of the subject to understand the results.
- Sensitive to Errors: If the data has mistakes or unusual values (outliers), the graph might give the wrong idea.
Solved Examples of Types of Graphs in Graph Theory
Example 1: Identify which one of the following is a directed graph and which one is an undirected graph and why.
Solution:
- The graph shown here does not contain any arrows and so its edges are not pointing in any direction. Thus it is an undirected graph.
- The graph shown here contains arrows and thus all of its edges are pointing in a particular direction. Thus it is a directed graph.
Example 2: Write the number of edges and vertices in the present in the following graph. Also, state where its is directed or undirected graph.
Solution: We have been given a graph where there are 5 vertices and 5 edges. Also we see that none of the edges are marked with arrows, hence it is an undirected graph.
If you want to score well in your maths exam then you are at the right place. Here you will get weekly test preparation, live classes, and exam series. Download the Testbook App now to prepare a smart and high-ranking strategy for the exam.
|
If you are checking Types of Graphs article, also check the related maths articles: |
|
FAQs For Types of Graphs in Graph Theory
How many types of graphs are there in graph theory?
There are a total of 18 types of graphs available under graph theory.
What are commonly used ways to represent graphs?
A graph can be represented using 3 data structures- adjacency matrix, adjacency list and adjacency set.
Why are graphs used everyday?
Studying graphs through a framework provides answers to many arrangements, networking, optimization, matching and operational problems. Graphs can be used to model many types of relations and processes in physical, biological, social and information systems, and has a wide range of useful applications
If the degree of the vertex is 2, then what vertex it is?
If the degree of the vertex is 2 then it is an even vertex.
What is graph theory?
Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
What is the difference between a directed and undirected graph?
In a directed graph, edges have direction (like one-way streets). In an undirected graph, edges do not have direction (like two-way streets).
What is the use of graph theory?
Graph theory is used in computer networks, social networks, maps, scheduling, and many more real-life problems where connections matter.