Graphs

Question 1

(a) Dijkstra from $S$ (original weights).

• Init: $d(S)=0$, others $\infty$.
• Extract $S(0)$: relax $A\to4$, $B\to2$.
• Extract $B(2)$: relax $A: \min(4, 2+1)=3$; $C: 2+8=10$; $D: 2+7=9$.
• Extract $A(3)$: relax $C: \min(10, 3+5)=8$.
• Extract $C(8)$: relax $T: 8+3=11$.
• Extract $D(9)$: relax $C: \min(8, 9+2)=11$ (no change); $T:\min(11,9+6)=11$? $9+6=15$, no change.
• Extract $T(11)$.

Final distances: $S=0,\ B=2,\ A=3,\ C=8,\ D=9,\ T=11$. Finalize order: $S, B, A, C, D, T$. (6: distances 4, order 2)

(b) Dijkstra minimises total weight, not edge count. Transforming $w'=10-w$ makes long original edges cheap, so the algorithm favours paths with many short-original edges — but there is no monotone relationship between $w'$-cost and number of edges. Concretely: path $S\to B\to A\to C\to T$ has 4 edges; $w'$-cost $=8+9+5+7=29$. Path $S\to B\to C\to T$ has 3 edges; $w'$-cost $=8+2+7=17$. Under $w'$ the 3-edge path wins here, but that's coincidental — one can construct a graph where the $w'$-minimal path uses more edges than an alternative. The point: minimising $\sum(10-w)$ = minimising $(10k-\sum w)$ for a $k$-edge path, which mixes edge count $k$ and total weight, so it is not equivalent to minimising $k$. To get fewest edges, use BFS (unit weights). (4: correct reasoning 2, concrete numbers 2)

(c) Bottleneck (minimax edge) $S\to T$:

• Path $S\to B\to A\to C\to T$: max edge $=\max(2,1,5,3)=5$.
• Path $S\to B\to C\to T$: max $=\max(2,8,3)=8$.
• Path $S\to B\to D\to C\to T$: max $=\max(2,7,2,3)=7$. Minimum bottleneck $=\mathbf{5}$, achieved by $S\to B\to A\to C\to T$. Adaptation: replace the "distance = sum" relaxation with $\text{bottleneck}(v)=\min\big(\text{bottleneck}(v),\ \max(\text{bottleneck}(u),w(u,v))\big)$ and extract the vertex of minimum current bottleneck. (4: value 2, path 1, adaptation 1)

Question 2

(a) Bellman–Ford from $1$. Order: $(1\!\to\!2:3),(2\!\to\!3:-2),(3\!\to\!4:2),(4\!\to\!2:-2),(1\!\to\!3:5)$. Init: $[0,\infty,\infty,\infty]$ for $(1,2,3,4)$.

Pass 1:

• $1\to2$: $d_2=3$
• $2\to3$: $d_3=1$
• $3\to4$: $d_4=3$
• $4\to2$: $d_2=\min(3,3-2)=1$
• $1\to3$: $d_3=\min(1,5)=1$ Result: $[0,1,1,3]$.

Pass 2:

• $1\to2$: $\min(1,3)=1$
• $2\to3$: $\min(1,1-2)=-1$
• $3\to4$: $\min(3,-1+2)=1$
• $4\to2$: $\min(1,1-2)=-1$
• $1\to3$: $\min(-1,5)=-1$ Result: $[0,-1,-1,1]$.

Pass 3:

• $1\to2$: $\min(-1,3)=-1$
• $2\to3$: $\min(-1,-1-2)=-3$
• $3\to4$: $\min(1,-3+2)=-1$
• $4\to2$: $\min(-1,-1-2)=-3$
• $1\to3$: $\min(-3,5)=-3$ Result: $[0,-3,-3,-1]$.

Pass 4 (|V|-th, the extra check pass):

• $1\to2$: $-3$ (no)
• $2\to3$: $\min(-3,-3-2)=-5$ ← still decreasing
• ... distances keep dropping. Result shows further relaxation, e.g. $d_3=-5$. (7: passes 2 each ≈ rounded to 7)

(b) Yes, a negative cycle reachable from $1$ exists. Distances continue to decrease on pass 4 (the $|V|$-th pass), which is the standard Bellman–Ford negative-cycle certificate. The cycle is $2\to3\to4\to2$ with weight $-2+2-2=-2<0$. (3)

(c) Floyd–Warshall gives all-pairs shortest paths in $O(V^3)$ and handles negative edges (no negative cycle). Running Bellman–Ford from every source costs $O(V\cdot VE)=O(V^2E)$; with $E\approx V^2/4$ that is $O(V^4/4)$, worse than $O(V^3)$. So Floyd–Warshall is preferable on dense graphs when all-pairs distances are needed. (2)

Question 3

(a) Edges: $a\to b\to c\to a$ (cycle) and $c\to d$, $d\to e\to f\to d$ (cycle). Kosaraju pass 1 (DFS, record finish times) from $a$: visits $a,b,c,d,e,f$; a valid finish order (last-finished first) is $a,b,c,d,e,f$ i.e. stack top $a$. Pass 2 on transpose ($b\to a, c\to b, a\to c, d\to c, e\to d, f\to e, d\to f$):

• Start $a$: in $G^T$ reach $c$ (via $a\to c$? transpose of $c\to a$ gives $a\to c$), $b$, back — collects $\{a,b,c\}$.
• Next unvisited by finish order: $d$: in $G^T$ reaches $f,e$ (transposes of $d\to e\to f\to d$) — collects $\{d,e,f\}$.

SCCs: $\{a,b,c\}$ and $\{d,e,f\}$. (7)

(b) Condensation: two super-nodes $X=\{a,b,c\}$, $Y=\{d,e,f\}$ with single edge $X\to Y$ (from $c\to d$). Topological order: $X, Y$. (3)

(c) If the condensation had a cycle, two distinct SCCs would be mutually reachable and hence form one larger SCC — contradiction; so it is acyclic. Number of topological orderings of a 2-node chain $X\to Y$ = 1. (3)

Question 4

(a) Max flow. Edmonds–Karp (shortest augmenting paths):

• Path $s\to u\to t$ (length 2), bottleneck $\min(10,5)=5$. Flow $=5$. Residual: $s\to u=5$, $u\to t=0$.
• Path $s\to v\to t$ (length 2), bottleneck $\min(5,10)=5$. Flow $=10$. Residual: $s\to v=0$, $v\to t=5$.
• Path $s\to u\to v\to t$ (length 3), bottleneck $\min(5,15,5)=5$. Flow $=15$. Residual: $s\to u=0$, $u\to v=10$, $v\to t=0$.
• No more augmenting paths ($s$'s out-edges saturated). Max flow $=15$. (6)

(b) Min cut: $S=\{s\}$, $T=\{u,v,t\}$. Cut edges $s\to u(10)$, $s\to v(5)$, capacity $=15$. Equals max flow ✓. (3)

(c) Bipartite matching: $x_1\!-\!y_1,\ x_3\!-\!y_2$ (or $x_3\!-\!y_3$), $x_2$ has only $y_1$ (taken). Better: $x_1\!-\!y_2,\ x_2\!-\!y_1,\ x_3\!-\!y_3$ — size 3 (perfect). Min vertex cover (König): must cover all edges; since matching size $=3$, min cover size $=3$, e.g. $\{y_1, y_2, x_3\}$ covers every edge ($x_1$'s edges to $y_1,y_2$ ✓; $x_2$'s $y_1$ ✓; $x_3$'s edges via $x_3$ ✓). Cover size $=$ matching size $=3$, so matching is maximum. (4)

Question 5

(a) Kruskal, sorted edges:

MST edges: P–Q, Q–R, S–U, Q–S. Total weight $=1+2+2+4=9$. (5)

(b) Union-by-rank + path compression trace (ranks start 0). Making first-named the root on ties:

• P–Q: root P (rank 1), Q→P.
• Q–R: find(Q)=P; R→P (P rank stays 1 since R rank 0).
• S–U: root S (rank 1), U→S.
• Q–S: find(Q)=P(rank1), find(S)=S(rank1) — equal ranks: P becomes root, S→P, P rank→2.

Final parent array: $P\to P$, $Q\to P$, $R\to P$, $S\to P$, $U\to S$ (or $U\to P$ after path compression on any later find(U)). Single tree rooted at P. (3)

[
  {"claim":"Dijkstra Q1 final distances S,A,B,C,D,T",
   "code":"import heapq\nadj={'S':[('A',4),('B',2)],'A':[('C',5)],'B':[('A',1),('C',8),('D',7)],'C':[('T',3)],'D':[('C',2),('T',6)],'T':[]}\ndist={k:float('inf') for k in adj}\ndist['S']=0\npq=[(0,'S')]\nwhile pq:\n d,u=heapq.heappop(pq)\n if d>dist[u]:continue\n for v,w in adj[u]:\n  if d+w<dist[v]:dist[v]=d+w;heapq.heappush(pq,(dist[v],v))\nresult = dist=={'S':0,'A':3,'B':2,'C':8,'D':9,'T':11}"},
  {"claim":"Bellman-Ford Q2 has reachable negative cycle from 1",
   "code":"edges=[(1,2,3),(2,3,-2),(3,4,2),(4,2,-2),(1,3,5)]\nV=[1,2,3,4]\nINF=float('inf')\nd={v:INF for v in V};d[1]=0\nfor _ in range(len(V)-1):\n for u,v,w in edges:\n  if d[u]!=INF and d[u]+w<d[v]:d[v]=d[u]+w\nneg=False\nfor u,v,w in edges:\n if d[u]!=INF and d[u]+w