Graphs play a pivotal role in the field of computer science, especially within data structures and algorithms. As part of B.Tech Data Structures Notes 2025 and Unit 2 Notes Data Structures, understanding the terminology of graphs is fundamental for solving a wide range of real-world problems such as social networking, routing, scheduling, and mapping systems. This chapter explores the foundational concepts, definitions, and terminologies of graph theory tailored for Engineering Study Material and students looking for a Free Download PDF resource.
A graph is a mathematical structure used to model pairwise relations between objects. A graph is denoted by G = (V, E) where V is the set of vertices (also called nodes) and E is the set of edges (also called arcs) that connect pairs of vertices. Graphs are widely used in representing networks, whether it be computer networks, social networks, transportation systems, or dependency graphs in compilers.
Vertex (Node): A vertex is a fundamental unit in a graph representing an entity. It is denoted as v ∈ V. Each vertex may store data or be identified by a unique label.
Edge (Arc): An edge represents a relationship or connection between two vertices. It is denoted as e = (u, v) where u, v ∈ V. Edges may be directed or undirected depending on the nature of the relationship they model.
Directed Graph (Digraph): A graph where each edge has a direction from one vertex to another is called a directed graph. In such graphs, e = (u, v) is not the same as e = (v, u). These are commonly used in scenarios where directionality matters such as one-way roads or hierarchical structures.
Undirected Graph: In an undirected graph, edges do not have a direction. This implies that the edge e = (u, v) is identical to e = (v, u). These are used in cases like mutual friendships in social networks.
Weighted Graph: A graph is said to be weighted if a real number (weight) is associated with each edge. These weights can represent costs, distances, or time, and are crucial in optimization problems like shortest path finding.
Unweighted Graph: In contrast, an unweighted graph treats all edges as equal, without any numerical values assigned to them.
Adjacency: Two vertices u and v are said to be adjacent if there exists an edge (u, v) between them.
Degree of Vertex: The degree of a vertex is the number of edges incident to it. For directed graphs, we define two types:
- In-degree: Number of edges coming into the vertex.
- Out-degree: Number of edges going out from the vertex.
Path: A path is a sequence of vertices connected by edges. For example, a path from v1 to v4 might be: v1 → v2 → v3 → v4.
Cycle: A cycle is a path that starts and ends at the same vertex, with all edges and vertices (except the start/end) being distinct.
Simple Path: A path in which no vertex is repeated.
Simple Cycle: A cycle in which only the first and last vertices are the same, with no repetition of edges or vertices in between.
Connected Graph: An undirected graph is said to be connected if there is a path between every pair of vertices.
Disconnected Graph: If there exists at least one pair of vertices in an undirected graph that does not have a path between them, the graph is disconnected.
Strongly Connected Graph: A directed graph is strongly connected if there is a path from every vertex to every other vertex in the graph.
Weakly Connected Graph: A directed graph is weakly connected if replacing all directed edges with undirected ones results in a connected graph.
Subgraph: A subgraph is a portion of a graph containing a subset of the vertices and edges of the original graph.
Spanning Subgraph: A subgraph that includes all the vertices of the original graph is known as a spanning subgraph.
Complete Graph: A graph in which every pair of distinct vertices is connected by a unique edge. A complete graph with n vertices has n(n – 1)/2 edges.
Null Graph: A graph with n vertices and 0 edges.
Graph Representations: Graphs can be represented in various formats:
- Adjacency Matrix: A two-dimensional array where A[i][j] = 1 indicates an edge from vertex i to j.
- Adjacency List: An array of lists where each list corresponds to a vertex and contains all adjacent vertices.
- Incidence Matrix: A matrix with rows representing vertices and columns representing edges.
📌 Insert Diagram: Adjacency Matrix vs Adjacency List
Graph Traversals: Traversing a graph means visiting all the vertices and edges in a structured way. Two primary methods are:
- Breadth-First Search (BFS): Explores the graph layer by layer starting from a source vertex.
- Depth-First Search (DFS): Explores as far as possible along one branch before backtracking.
📌 Insert Diagram: BFS vs DFS Traversal Example
Directed Acyclic Graph (DAG): A directed graph with no cycles. DAGs are widely used in scheduling, representing tasks and their dependencies.
Tree: A tree is a special type of graph that is connected and acyclic. A tree with n vertices has n-1 edges.
Forest: A disjoint set of trees. It is a collection of acyclic graphs.
Isomorphic Graphs: Two graphs G1 and G2 are isomorphic if there is a one-to-one mapping between their vertices and edges that preserves adjacency.
Multigraph: A graph that is allowed to have multiple edges (also called parallel edges) between the same pair of vertices.
Pseudograph: A graph that can have both multiple edges and self-loops.
Self-loop: An edge that connects a vertex to itself.
Bridge: An edge in a graph whose removal increases the number of connected components.
Cut Vertex (Articulation Point): A vertex whose removal increases the number of connected components in the graph.
Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to the other.
📌 Insert Diagram: Bipartite Graph Example
Planar Graph: A graph that can be drawn on a plane without any edges crossing.
Chromatic Number: The smallest number of colors needed to color the vertices of a graph such that no two adjacent vertices share the same color.
Euler Path and Circuit: An Euler Path is a path that visits every edge exactly once. An Euler Circuit is an Euler Path that starts and ends at the same vertex.
Hamiltonian Path and Circuit: A Hamiltonian Path visits every vertex exactly once. A Hamiltonian Circuit is a Hamiltonian Path that starts and ends at the same vertex.
🔹 Short Answer Questions (2-3 Marks)
- What is a directed graph? — A graph in which edges have a specific direction from one vertex to another.
- Define a weighted graph. — A graph where each edge has an associated numerical value or weight.
- What is a simple path? — A path that does not repeat any vertices.
- Explain the term ‘degree of a vertex’. — The number of edges connected to the vertex. In directed graphs, this includes in-degree and out-degree.
- Define a subgraph. — A graph formed from a subset of the vertices and edges of another graph.
- What is a null graph? — A graph with n vertices and zero edges.
- What is a self-loop? — An edge that connects a vertex to itself.
🔸 Long Answer Questions (5-10 Marks)
- Explain different types of graph representations with examples. — Students should describe adjacency matrix, adjacency list, and incidence matrix with suitable examples.
- Distinguish between Euler and Hamiltonian circuits with examples. — Students should explain each concept, their conditions, and provide illustrations or examples.
- What is the difference between a connected graph and a strongly connected graph? — This answer should define each type, use diagrams if possible, and highlight the role of direction in edges.
- Describe graph traversal techniques. Compare BFS and DFS. — Students should explain both methods, include their working principles, use cases, and suitable examples.
- Define and explain different types of graphs like complete graph, null graph, and multigraph. — Definitions, features, and differences must be detailed clearly.
📝 Chapter Summary A graph is defined as G = (V, E) where V is a set of vertices and E is a set of edgesGraphs can be directed or undirectedGraphs can be weighted or unweightedThe degree of a vertex is the number of edges connected to itGraph representations include adjacency matrix, adjacency list, and incidence matrixTraversals in graphs include BFS and DFSA tree is a connected acyclic graphA forest is a collection of treesA DAG is a directed graph with no cyclesBipartite graphs can be divided into two vertex sets with no internal connectionsEuler and Hamiltonian paths and circuits deal with visiting edges and vertices without repetition
📘 Model Paper / Sample Internal Exam Questions
- Define and differentiate between a simple path and a simple cycle with examples.
- Write short notes on BFS and DFS traversal techniques.
- Explain the concept of a directed acyclic graph and its applications.
- What is the chromatic number of a graph? Explain with an example.
- Describe the adjacency matrix representation of a graph with an example.
