Graphs

Q1. (4 marks) — 1 mark each

• (a) Simple graph: no self-loops and no multiple (parallel) edges between the same pair of vertices.
• (b) Multigraph: allows multiple parallel edges between the same pair of vertices (and possibly self-loops).
• (c) Weighted graph: each edge carries a numeric weight/cost.
• (d) Directed graph: edges have direction (ordered pairs); edge $u\to v \ne v\to u$.

Q2. (4 marks)

• (a) Adjacency matrix: $O(V^2)$. (1)
• (b) Adjacency list: $O(V+E)$. (1)
• For $V=1000$: matrix $\approx V^2 = 10^6$ entries; list $\approx V+2E = 1000+6000 = 7000$. (1) List uses far less space because the graph is sparse ($E \ll V^2$). (1)

Q3. (4 marks)

• BFS: $O(V+E)$. (1) DFS: $O(V+E)$. (1) (each vertex and edge examined once)
• BFS explores vertices in non-decreasing order of distance (level by level), so the first time a vertex is reached is via a minimum number of edges. (2)

Q4. (4 marks)

• BFS order from $A$: $A, B, C, D, E$. (2) (A → neighbours B,C → their unvisited neighbour D → then E)
• Distance $A\to E$: path $A\text{-}B\text{-}D\text{-}E$ (or $A\text{-}C\text{-}D\text{-}E$) = 3 edges. (2)

Q5. (4 marks) — 1 mark each

• (a) False — Dijkstra's greedy choice fails with negative edges.
• (b) True — a further (V-th) relaxation succeeding indicates a negative cycle.
• (c) False — only for DAGs (acyclic); a cycle prevents topological ordering.
• (d) True — Kruskal uses Union-Find to detect whether adding an edge forms a cycle.

Q6. (5 marks)

• $d(A) = 2$ (direct $S\to A$). (1)
• $d(B) = \min(5,\; 2+1) = 3$ (via $A$). (2)
• $d(C) = \min(2+7,\; 3+3) = \min(9,6) = 6$ (via $B$). (2)

Final: $d(A)=2,\ d(B)=3,\ d(C)=6$.

Q7. (4 marks) — 1 mark each

• (a) Dijkstra (binary heap): $O((V+E)\log V)$.
• (b) Bellman-Ford: $O(VE)$.
• (c) Floyd-Warshall: $O(V^3)$.
• (d) Kruskal: $O(E \log E)$ (dominated by sorting; $=O(E\log V)$).

Q8. (3 marks)

• (a) The maximum flow from source to sink equals the capacity of the minimum $s$-$t$ cut. (2)
• (b) Edmonds-Karp: $O(VE^2)$. (1)

Q9. (4 marks)

• Bipartite graph: vertices can be split into two disjoint sets $U,V$ such that every edge connects a vertex in $U$ to one in $V$ (no edge within a set). (2)
• Test: 2-coloring via BFS/DFS — attempt to color adjacent vertices with alternating colors; bipartite iff no conflict. (1) Complexity $O(V+E)$. (1)

Q10. (4 marks)

• Amortized time per operation: $O(\alpha(n))$ (inverse Ackermann, effectively constant). (1)
• Path compression: flattens the tree by pointing nodes directly to the root during find. (1.5)
• Union by rank: attaches the smaller/shorter tree under the taller one to keep trees shallow. (1.5)

[
  {"claim": "Adjacency list count 7000 < matrix 10^6 for V=1000,E=3000", "code": "V=1000; E=3000; matrix=V*V; lst=V+2*E; result = (lst==7000) and (matrix==1000000) and (lst<matrix)"},
  {"claim": "Dijkstra Q6 distances S->A=2,B=3,C=6", "code": "dA=2; dB=min(5,dA+1); dC=min(dA+7,dB+3); result = (dA==2) and (dB==3) and (dC==6)"},
  {"claim": "BFS shortest distance A to E is 3 edges", "code": "import collections; adj={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C','E'],'E':['D']}; dist={'A':0}; q=collections.deque(['A'])\nwhile q:\n    u=q.popleft()\n    for w in adj[u]:\n        if w not in dist:\n            dist[w]=dist[u]+1; q.append(w)\nresult = dist['E']==3"},
  {"claim": "Kruskal complexity E log E equals E log V asymptotically for E<=V^2", "code": "import sympy; V=sympy.Symbol('V',positive=True); result = sympy.simplify(sympy.log(V*V)-2*sympy.log(V))==0"}
]