Level 1 — RecognitionGraphs

Graphs

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Chapter: 3.5 Graphs Level: 1 — Recognition (MCQ / Matching / True-False with justification) Time limit: 20 minutes Total marks: 30

Section A — Multiple Choice (1 mark each)

Choose the single best answer.

Q1. The space complexity of an adjacency matrix representation for a graph with $V$ vertices is: (a) $O(V+E)$ (b) $O(V^2)$ (c) $O(E)$ (d) $O(\log V)$

Q2. Which traversal naturally finds the shortest path (fewest edges) in an unweighted graph? (a) DFS (b) BFS (c) Dijkstra (d) Floyd–Warshall

Q3. Dijkstra's algorithm fails on graphs that contain: (a) cycles (b) negative-weight edges (c) more than $V^2$ edges (d) self-loops only

Q4. The time complexity of the Floyd–Warshall all-pairs shortest path algorithm is: (a) $O(V^2)$ (b) $O(VE)$ (c) $O(V^3)$ (d) $O((V+E)\log V)$

Q5. Which algorithm can detect a negative-weight cycle? (a) Dijkstra (b) Prim (c) Bellman–Ford (d) BFS

Q6. Kahn's algorithm is a BFS-based method used to perform: (a) cycle counting (b) topological sort (c) minimum spanning tree (d) max-flow

Q7. With union by rank and path compression, the amortized cost per Disjoint-Set-Union operation is: (a) $O(\log n)$ (b) $O(1)$ exactly (c) $O(\alpha(n))$ (d) $O(n)$

Q8. A graph is bipartite if and only if it contains: (a) no cycles (b) no odd-length cycles (c) no even-length cycles (d) exactly one cycle

Q9. For an admissible A* heuristic $h$ , which condition must hold for every node $n$ ? (a) $h(n) \ge h^*(n)$ (b) $h(n) \le h^*(n)$ (c) $h(n)=0$ (d) $h(n)=h^*(n)$

Q10. The Edmonds–Karp algorithm improves Ford–Fulkerson by finding augmenting paths using: (a) DFS (b) BFS (shortest augmenting path) (c) Dijkstra (d) random selection

Section B — Matching (1 mark each, 5 marks)

Q11–Q15. Match each algorithm (left) with its correct purpose/complexity (right). Write the letter.

#	Algorithm	Letter	Purpose / Complexity
11	Kruskal's	A	SCC via two DFS passes (Kosaraju)
12	Prim's	B	MST using Union-Find, $O(E\log E)$
13	Kosaraju's	C	Articulation points/bridges via low-link
14	Tarjan's low-link	D	MST using priority queue
15	Dijkstra's	E	Single-source shortest path, $O((V+E)\log V)$

Section C — True / False with one-line justification (2 marks each: 1 for T/F, 1 for justification)

Q16. In an undirected simple graph, DFS classifies a back edge as evidence of a cycle. (True/False + justify)

Q17. An adjacency list uses $O(V^2)$ space regardless of the number of edges. (True/False + justify)

Q18. The max-flow of a network equals the capacity of the minimum cut. (True/False + justify)

Q19. A directed graph that has a valid topological ordering may still contain a cycle. (True/False + justify)

Q20. A consistent (monotone) heuristic in A* is always admissible. (True/False + justify)

Answer keyMark scheme & solutions

Section A (10 marks)

Q1 — (b) $O(V^2)$ . The matrix stores an entry for every ordered pair of vertices → $V \times V$ . (1)

Q2 — (b) BFS. BFS explores in layers of increasing distance, so the first time a node is dequeued its distance in edges is minimal. (1)

Q3 — (b) negative-weight edges. Dijkstra's greedy "finalize the min" assumption breaks because a later negative edge can reduce an already-settled distance. (1)

Q4 — (c) $O(V^3)$ . Triple nested loop over intermediate vertex $k$ and pairs $(i,j)$ . (1)

Q5 — (c) Bellman–Ford. After $V-1$ relaxation rounds, a further relaxable edge signals a negative cycle. (1)

Q6 — (b) topological sort. Kahn repeatedly removes in-degree-0 vertices via a queue. (1)

Q7 — (c) $O(\alpha(n))$ . Combined path compression + union by rank gives inverse-Ackermann amortized cost. (1)

Q8 — (b) no odd-length cycles. Odd cycles cannot be 2-colored; their absence guarantees bipartiteness. (1)

Q9 — (b) $h(n)\le h^*(n)$ . Admissibility = never overestimate the true remaining cost $h^*$ . (1)

Q10 — (b) BFS. Edmonds–Karp picks the shortest augmenting path by edge count, bounding iterations to $O(VE)$ and total time $O(VE^2)$ . (1)

Section B (5 marks)

Q	Answer
11	B — Kruskal's: MST with Union-Find, $O(E\log E)$
12	D — Prim's: MST with priority queue
13	A — Kosaraju's: SCC via two DFS passes
14	C — Tarjan's low-link: articulation points/bridges
15	E — Dijkstra's: SSSP, $O((V+E)\log V)$

(1 mark each)

Section C (10 marks)

Q16 — TRUE. (1) In undirected DFS, an edge to an already-visited vertex that is not the parent is a back edge, closing a cycle. (justify 1)

Q17 — FALSE. (1) An adjacency list uses $O(V+E)$ space; it only stores edges that exist, not all pairs. (justify 1)

Q18 — TRUE. (1) This is the max-flow min-cut theorem: any flow ≤ any cut, and equality is achieved at the maximum flow. (justify 1)

Q19 — FALSE. (1) A topological ordering exists iff the graph is a DAG (acyclic); a cycle makes ordering impossible. (justify 1)

Q20 — TRUE. (1) Consistency ( $h(u)\le c(u,v)+h(v)$ with $h(\text{goal})=0$ ) implies admissibility by telescoping along any path to the goal. (justify 1)

[
  {"claim":"Adjacency matrix space is V^2 for V=6 -> 36","code":"V=6; result=(V*V==36)"},
  {"claim":"Floyd-Warshall is V^3; for V=10 that is 1000 vs VE(=10*20=200) larger","code":"V=10;E=20; result=(V**3==1000 and V**3 > V*E)"},
  {"claim":"Bellman-Ford needs V-1 relaxation rounds for V=7 -> 6","code":"V=7; result=(V-1==6)"},
  {"claim":"Consistency implies admissibility: telescoping h(u)<=c+h(v) with h(goal)=0 keeps h<=h_star. Check numeric chain c1=3,c2=4 -> h_start<=7","code":"c1=3;c2=4; h_goal=0; hv=c2+h_goal; hu=c1+hv; result=(hu<=7 and hu==7)"},
  {"claim":"Edmonds-Karp bound O(V*E^2): for V=4,E=5 the magnitude 4*25=100","code":"V=4;E=5; result=(V*E**2==100)"}
]