1. 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.
2. 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.
3. In a weighted graph, if the edge weights are all equal, what does this imply?
A. The graph is a tree.
B. The graph is bipartite.
C. Any algorithm for finding the shortest path will have the same result.
D. The graph is not connected.
Answer: C) Any algorithm for finding the shortest path will have the same result.
Rationale: If the edge weights are equal, the shortest path will simply depend on the
number of edges in the path, not their weight.
4. 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.
5. Which of the following is a feature of the Bellman-Ford Algorithm?
A. It is used to find the minimum spanning tree.
B. It can handle graphs with negative edge weights.
C. It requires a priority queue.
D. It is faster than Dijkstra’s algorithm.
Answer: B) It can handle graphs with negative edge weights.
Rationale: The Bellman-Ford algorithm can find the shortest paths in a graph even if
some of the edge weights are negative, unlike Dijkstra’s algorithm.
6. 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).
7. Which of the following is NOT a valid operation on graphs?
A. Addition of an edge.
B. Deletion of a vertex.
C. Removal of a vertex's edges.
D. Change of the number of edges in a graph.
Answer: D) Change of the number of edges in a graph.
Rationale: The number of edges in a graph is determined by its structure, but the other
options involve operations on the graph that preserve or modify the structure without
fundamentally changing edge count.
8. Which of the following algorithms is based on a greedy strategy?
A. Dijkstra’s Algorithm.
B. Bellman-Ford Algorithm.
C. Floyd-Warshall Algorithm.
D. Ford-Fulkerson Algorithm.
Answer: A) Dijkstra’s Algorithm.
Rationale: Dijkstra’s algorithm is a greedy algorithm because it always selects the
nearest unvisited vertex with the smallest tentative distance.
9. 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.
10. In the context of graph theory, what does "planar" mean?
A. The graph is weighted.
B. The graph can be drawn on a plane without any edges crossing.
C. The graph is directed.
D. The graph contains a Hamiltonian cycle.
Answer: B) The graph can be drawn on a plane without any edges crossing.
Rationale: A planar graph is one that can be embedded in the plane without any edges
crossing each other.
11. Which algorithm is used to find the shortest path from a single source to all other
vertices in a graph with negative edge weights?
A. Dijkstra’s Algorithm.
B. Bellman-Ford Algorithm.
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.
2. 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.
3. In a weighted graph, if the edge weights are all equal, what does this imply?
A. The graph is a tree.
B. The graph is bipartite.
C. Any algorithm for finding the shortest path will have the same result.
D. The graph is not connected.
Answer: C) Any algorithm for finding the shortest path will have the same result.
Rationale: If the edge weights are equal, the shortest path will simply depend on the
number of edges in the path, not their weight.
4. 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.
5. Which of the following is a feature of the Bellman-Ford Algorithm?
A. It is used to find the minimum spanning tree.
B. It can handle graphs with negative edge weights.
C. It requires a priority queue.
D. It is faster than Dijkstra’s algorithm.
Answer: B) It can handle graphs with negative edge weights.
Rationale: The Bellman-Ford algorithm can find the shortest paths in a graph even if
some of the edge weights are negative, unlike Dijkstra’s algorithm.
6. 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).
7. Which of the following is NOT a valid operation on graphs?
A. Addition of an edge.
B. Deletion of a vertex.
C. Removal of a vertex's edges.
D. Change of the number of edges in a graph.
Answer: D) Change of the number of edges in a graph.
Rationale: The number of edges in a graph is determined by its structure, but the other
options involve operations on the graph that preserve or modify the structure without
fundamentally changing edge count.
8. Which of the following algorithms is based on a greedy strategy?
A. Dijkstra’s Algorithm.
B. Bellman-Ford Algorithm.
C. Floyd-Warshall Algorithm.
D. Ford-Fulkerson Algorithm.
Answer: A) Dijkstra’s Algorithm.
Rationale: Dijkstra’s algorithm is a greedy algorithm because it always selects the
nearest unvisited vertex with the smallest tentative distance.
9. 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.
10. In the context of graph theory, what does "planar" mean?
A. The graph is weighted.
B. The graph can be drawn on a plane without any edges crossing.
C. The graph is directed.
D. The graph contains a Hamiltonian cycle.
Answer: B) The graph can be drawn on a plane without any edges crossing.
Rationale: A planar graph is one that can be embedded in the plane without any edges
crossing each other.
11. Which algorithm is used to find the shortest path from a single source to all other
vertices in a graph with negative edge weights?
A. Dijkstra’s Algorithm.
B. Bellman-Ford Algorithm.
