Discrete Structure · Unit 8
Graph Theory Fundamentals
Exam-focused notes for Graph Theory Fundamentals (Discrete Structure, BIT152): what the TU syllabus asks and how it has actually been tested, with 8 solved past questions from this unit.
What this unit covers
- Graph definition and types
- Simple graphs and pseudographs
- Graph representation using adjacency matrix
- Graph representation using incidence matrix
- Directed graphs
- Graph isomorphism
- Connectivity in graphs
- Bipartite graphs
- Planar graphs
Connectivity in graphs
What do you mean by connectivity in graph? Discuss about Bipartite and Planar graph. [1+4]
--- Connectivity refers to the property of a graph that describes whether there exists a path between every pair of vertices. - A graph G is said to be connected if there exists at least one path between every pair of vertices. - If a graph is not connected...
Full solved answer →What does connectivity in graphs mean? Differentiate between permutation and combination. Solve the recurrence relation $a_n = 7a_{n-1} - 10a_{n-2}$ with initial conditions $a_0 = 2$ and $a_1 = 3$. [4+6]
- Recurrence: $an = 7a{n-1} - 10a{n-2}$ - Initial conditions: $a0 = 2$, $a1 = 3$ - Conceptual parts: connectivity in graphs; permutation vs combination. All data present. --- Connectivity describes the extent to which vertices of a graph are reachable from ...
Full solved answer →Graph isomorphism
Define graph isomorphism with an example.Using Kruskal's algorithm generate the Minimum Spanning Tree from following graph.[5+5]
--- Part 1: Define graph isomorphism with an example. [5 marks] Part 2: Generate the MST using Kruskal's algorithm "from following graph." [5 marks] Missing data: The actual graph (vertices, edges, and edge weights) referenced by "following graph" is not pr...
Full solved answer →Differentiate between graph and tree.Describe about the necessary conditions for graphs to be isomorphic with an example.[2+8]
--- (a) Difference Between Graph and Tree Graph Tree --------------------- A graph is a collection of vertices (nodes) and edges with no restrictions on cycles. A tree is a connected, acyclic (no cycles) undirected graph. A graph may or may not be connected...
Full solved answer →Graph representation using adjacency matrix
Explain any two ways of representing the graph. [5]
An adjacency matrix is a 2D array (matrix) of size V x V, where V is the number of vertices in the graph. Definition: For a graph G = (V, E), the adjacency matrix A is defined as: Example: Consider a graph with 4 vertices (1, 2, 3, 4) and edges: (1,2), (1,3...
Full solved answer →How can we represent a graph using Adjacency Matrix? Explain. [5]
An Adjacency Matrix is a 2D array (matrix) used to represent a graph. For a graph with n vertices, the adjacency matrix is an n × n matrix where each cell indicates whether a pair of vertices is connected by an edge. --- Let A be the adjacency matrix of a g...
Full solved answer →Graph representation using incidence matrix
Explain incidence matrix representation of a graph with example. [5]
An incidence matrix is a 2D matrix used to represent a graph where: - Rows represent the vertices of the graph - Columns represent the edges of the graph For a graph G = (V, E) with n vertices and m edges, the incidence matrix is an n × m matrix B, where: $...
Full solved answer →Graph definition and types
What is graph? Explain simple graph and pseudograph with example. [5]
A graph G is a mathematical structure consisting of a non-empty set of vertices (nodes) V and a set of edges E, where each edge connects two vertices. Formally: G = (V, E) - V = {v₁, v₂, v₃, ...} → set of vertices - E = {e₁, e₂, e₃, ...} → set of edges Each...
Full solved answer →Make Unit 8 stick
Practice BIT152 with flashcards & quizzes