1. What is the time complexity of Kruskal’s algorithm with an adjacency list
representation?
A. O(ElogV)O(E \log V)O(ElogV)
B. O(V2)O(V^2)O(V2)
C. O(E2)O(E^2)O(E2)
D. O(V+E)O(V + E)O(V+E)
Answer: A) O(ElogV)O(E \log V)O(ElogV)
Rationale: Kruskal's algorithm requires sorting the edges, which takes O(ElogE)O(E
\log E)O(ElogE), and the union-find operations take O(logV)O(\log V)O(logV).
Therefore, the overall time complexity is O(ElogV)O(E \log V)O(ElogV).
2. Which of the following best describes a bipartite graph?
A. It contains no cycles.
B. It can be colored using two colors.
C. It has exactly one vertex.
D. It is a tree with two branches.
Answer: B) It can be colored using two colors.
Rationale: A bipartite graph is one where the vertex set can be divided into two disjoint
sets such that every edge connects a vertex from one set to a vertex from the other
set.
3. Which of the following is NOT a property of a minimum spanning tree (MST)?
A. It contains all the vertices of the graph.
B. It contains the minimum number of edges to connect all vertices.
C. It may contain cycles.
D. The sum of its edge weights is minimized.
Answer: C) It may contain cycles.
Rationale: A minimum spanning tree (MST) cannot contain cycles by definition, as it is a
connected acyclic graph.
4. What is the degree of a vertex in a graph?
A. The number of edges connected to the vertex.
B. The sum of the weights of the edges connected to the vertex.
C. The number of vertices connected to the vertex.
D. The number of loops at the vertex.
Answer: A) The number of edges connected to the vertex.
Rationale: The degree of a vertex is simply the number of edges that are incident to it.
5. In a directed graph, if there is an edge from vertex A to vertex B, this is represented
by:
A. A bidirectional edge.
B. An arrow from A to B.
C. An undirected edge.
D. A cycle.
Answer: B) An arrow from A to B.
Rationale: Directed edges in a graph are represented by arrows, indicating the direction
from one vertex to another.
, 6. What is the key difference between a tree and a general graph?
A. A tree is always connected, and it contains no cycles.
B. A tree contains cycles, while a graph does not.
C. A tree is disconnected, while a graph is connected.
D. A tree contains no edges.
Answer: A) A tree is always connected, and it contains no cycles.
Rationale: A tree is a special type of graph that is connected and contains no cycles.
7. What is the chromatic number of a graph?
A. The minimum number of edges that cover all vertices.
B. The minimum number of colors needed to color the graph such that no two adjacent
vertices share the same color.
C. The number of vertices in the graph.
D. The maximum degree of a vertex.
Answer: B) The minimum number of colors needed to color the graph such that no two
adjacent vertices share the same color.
Rationale: The chromatic number is the smallest number of colors needed to color a
graph such that no two adjacent vertices have the same color.
8. What is the degree of vertex A in the graph shown below (considering undirected
edges)?
(Graph with edges: A-B, A-C, A-D, B-C, D-E)
A. 1
B. 2
C. 3
D. 4
Answer: D) 4
Rationale: Vertex A is connected by edges to vertices B, C, and D, which gives it a
degree of 4.
9. What is the main purpose of a directed edge in a graph?
A. To represent a relationship that has no direction.
B. To show the direction of a relationship between two vertices.
C. To connect two vertices without any relationship.
D. To form a loop between two vertices.
Answer: B) To show the direction of a relationship between two vertices.
Rationale: A directed edge indicates that there is a one-way relationship between two
vertices, with a specified direction.
10. Which of the following algorithms is used to find the maximum flow in a network?
A. Ford-Fulkerson Algorithm.
B. Dijkstra’s Algorithm.
C. Kruskal’s Algorithm.
D. Bellman-Ford Algorithm.
Answer: A) Ford-Fulkerson Algorithm.
Rationale: The Ford-Fulkerson algorithm is used to find the maximum flow in a flow
network by augmenting paths from the source to the sink.
11. Which of the following is true about a directed graph?
A. It consists of only vertices.
representation?
A. O(ElogV)O(E \log V)O(ElogV)
B. O(V2)O(V^2)O(V2)
C. O(E2)O(E^2)O(E2)
D. O(V+E)O(V + E)O(V+E)
Answer: A) O(ElogV)O(E \log V)O(ElogV)
Rationale: Kruskal's algorithm requires sorting the edges, which takes O(ElogE)O(E
\log E)O(ElogE), and the union-find operations take O(logV)O(\log V)O(logV).
Therefore, the overall time complexity is O(ElogV)O(E \log V)O(ElogV).
2. Which of the following best describes a bipartite graph?
A. It contains no cycles.
B. It can be colored using two colors.
C. It has exactly one vertex.
D. It is a tree with two branches.
Answer: B) It can be colored using two colors.
Rationale: A bipartite graph is one where the vertex set can be divided into two disjoint
sets such that every edge connects a vertex from one set to a vertex from the other
set.
3. Which of the following is NOT a property of a minimum spanning tree (MST)?
A. It contains all the vertices of the graph.
B. It contains the minimum number of edges to connect all vertices.
C. It may contain cycles.
D. The sum of its edge weights is minimized.
Answer: C) It may contain cycles.
Rationale: A minimum spanning tree (MST) cannot contain cycles by definition, as it is a
connected acyclic graph.
4. What is the degree of a vertex in a graph?
A. The number of edges connected to the vertex.
B. The sum of the weights of the edges connected to the vertex.
C. The number of vertices connected to the vertex.
D. The number of loops at the vertex.
Answer: A) The number of edges connected to the vertex.
Rationale: The degree of a vertex is simply the number of edges that are incident to it.
5. In a directed graph, if there is an edge from vertex A to vertex B, this is represented
by:
A. A bidirectional edge.
B. An arrow from A to B.
C. An undirected edge.
D. A cycle.
Answer: B) An arrow from A to B.
Rationale: Directed edges in a graph are represented by arrows, indicating the direction
from one vertex to another.
, 6. What is the key difference between a tree and a general graph?
A. A tree is always connected, and it contains no cycles.
B. A tree contains cycles, while a graph does not.
C. A tree is disconnected, while a graph is connected.
D. A tree contains no edges.
Answer: A) A tree is always connected, and it contains no cycles.
Rationale: A tree is a special type of graph that is connected and contains no cycles.
7. What is the chromatic number of a graph?
A. The minimum number of edges that cover all vertices.
B. The minimum number of colors needed to color the graph such that no two adjacent
vertices share the same color.
C. The number of vertices in the graph.
D. The maximum degree of a vertex.
Answer: B) The minimum number of colors needed to color the graph such that no two
adjacent vertices share the same color.
Rationale: The chromatic number is the smallest number of colors needed to color a
graph such that no two adjacent vertices have the same color.
8. What is the degree of vertex A in the graph shown below (considering undirected
edges)?
(Graph with edges: A-B, A-C, A-D, B-C, D-E)
A. 1
B. 2
C. 3
D. 4
Answer: D) 4
Rationale: Vertex A is connected by edges to vertices B, C, and D, which gives it a
degree of 4.
9. What is the main purpose of a directed edge in a graph?
A. To represent a relationship that has no direction.
B. To show the direction of a relationship between two vertices.
C. To connect two vertices without any relationship.
D. To form a loop between two vertices.
Answer: B) To show the direction of a relationship between two vertices.
Rationale: A directed edge indicates that there is a one-way relationship between two
vertices, with a specified direction.
10. Which of the following algorithms is used to find the maximum flow in a network?
A. Ford-Fulkerson Algorithm.
B. Dijkstra’s Algorithm.
C. Kruskal’s Algorithm.
D. Bellman-Ford Algorithm.
Answer: A) Ford-Fulkerson Algorithm.
Rationale: The Ford-Fulkerson algorithm is used to find the maximum flow in a flow
network by augmenting paths from the source to the sink.
11. Which of the following is true about a directed graph?
A. It consists of only vertices.
