Graphs

Question 1

(a) (4 marks) Dijkstra assumes that once a vertex is extracted (finalized) its distance is optimal — valid only when all edge weights are $\ge 0$, since it never revisits a finalized node. With a negative edge, a later-discovered shorter route can lower a finalized node's distance, which Dijkstra ignores. (2 marks)

Counterexample: nodes $s,a,b$; edges $s\to a=2$, $s\to b=3$, $b\to a=-2$. Dijkstra pops $s$, sets $d(a)=2,d(b)=3$; pops $a$ (dist 2) and finalizes it. But true $d(a)=3+(-2)=1$ via $b$. Dijkstra reports $2$ — wrong. (2 marks)

(b) (6 marks) Let $P = v_0(=s)\to v_1\to\dots\to v_k(=t)$. Then $\hat{w}(P)=\sum_{i=0}^{k-1}\hat{w}(v_i,v_{i+1}) = \sum_{i=0}^{k-1}\big(w(v_i,v_{i+1})+h(v_i)-h(v_{i+1})\big).$ The potential terms telescope: $\sum_i (h(v_i)-h(v_{i+1})) = h(v_0)-h(v_k)=h(s)-h(t)$. (3 marks) Hence $\hat{w}(P) = w(P) + h(s)-h(t)$. Since $h(s)-h(t)$ is a constant independent of the path $P$, every $s$–$t$ path's length shifts by the same amount, so the ordering of paths by length is preserved and the argmin (shortest path set) is unchanged. (3 marks)

(c) (4 marks) Treat $h(v)$ as potential energy at node $v$. Then $\hat w(u,v)=w(u,v)-(h(v)-h(u))$: the reweighted cost is the actual energy minus the drop in potential — i.e. the dissipative (non-recoverable) part of the work, the potential difference being a conservative, path-independent term. (2 marks) Setting $h(v)=\delta(v)$ = shortest distance from a super-source gives, for every edge, the triangle inequality $\delta(v)\le\delta(u)+w(u,v)$, i.e. $\hat w(u,v)=w(u,v)+\delta(u)-\delta(v)\ge0$. Physically: dissipation is never negative once measured relative to the true potential field. (2 marks)

(d) (8 marks) Bellman–Ford from $s=0$. Init $d=[0,\infty,\infty,\infty]$.

Relaxing edges to convergence:

• $0\to1$: $d_1=4$; $0\to2$: $d_2=5$.
• $1\to2,-3$: $d_2=\min(5,4-3)=1$.
• $2\to3,4$: $d_3=1+4=5$.
• $1\to3,6$: $d_3=\min(5,4+6)=5$.
• $3\to1,-2$: $d_1=\min(4,5-2)=3$.
• Re-relax $1\to2$: $d_2=\min(1,3-3)=0$; then $2\to3$: $d_3=\min(5,0+4)=4$; then $3\to1$: $d_1=\min(3,4-2)=2$; then $1\to2$: $\min(0,2-3)=-1$; $2\to3$: $\min(4,-1+4)=3$; $3\to1$: $\min(2,3-2)=1$...

The negative cycle check: cycle $1\to2\to3\to1$ has weight $-3+4-2=-1<0$. This is a negative cycle! Therefore Bellman–Ford, after $V-1=3$ passes, will find a further relaxation possible in pass 4 → report negative cycle exists; no finite shortest distances to $\{1,2,3\}$. (5 marks)

Distances after exactly $V-1=3$ full passes (order 0→1,0→2,1→2,2→3,1→3,3→1 per pass): Pass1: $d=[0,3,0,5]$; Pass2: $d=[0,1,-2,3]$... each pass reduces by cycle weight $-1$, confirming divergence. Final answer: negative cycle $1\!-\!2\!-\!3$ detected; shortest distances to nodes 1,2,3 are undefined ($-\infty$). (1 mark)

Complexity: each of $V-1$ passes relaxes all $E$ edges once → $O(VE)$; the $V$-th pass is the negative-cycle detection pass. (2 marks)

Question 2

(a) (7 marks) Cut Property: Let $(S,V\setminus S)$ be any cut and let $e=(u,v)$ be the unique minimum-weight edge crossing it. Claim: $e$ is in every MST. (1) Proof by exchange: Suppose an MST $T$ does not contain $e$. Adding $e$ to $T$ creates exactly one cycle $C$. Since $e$ crosses the cut, $C$ must cross the cut an even number of times, so there is another crossing edge $e'\in T$, $e'\ne e$. (3) By assumption of distinct weights and minimality of $e$, $w(e)<w(e')$. Form $T' = T-e'+e$: $T'$ is still a spanning tree (removing $e'$ from cycle keeps connectivity) with $w(T')=w(T)-w(e')+w(e)<w(T)$, contradicting minimality of $T$. (3) Hence $e\in T$. $\square$

(b) (8 marks) Sort edges: $AB(1),CD(2),AC(3),BC(4),BD(5),DE(6),CE(7)$.

• $AB(1)$: add. Sets $\{A,B\}$. ✓
• $CD(2)$: add. $\{C,D\}$. ✓
• $AC(3)$: add (joins $\{A,B\}$ & $\{C,D\}$) → $\{A,B,C,D\}$. ✓
• $BC(4)$: same set → reject (cycle).
• $BD(5)$: same set → reject.
• $DE(6)$: add → $\{A,B,C,D,E\}$. ✓
• $CE(7)$: reject.

MST edges: $AB, CD, AC, DE$; total weight $=1+2+3+6=12$. (5 marks)

Union-Find (union by rank, path compression) representative evolution: after $AB$: root(B)→A (rank A=1); after $CD$: root(D)→C; after $AC$: attach lower rank root (C) under A → root of all = A; after $DE$: E→A. Final parent chains compress to point at A. (3 marks)

(c) (5 marks) Claim: with union by rank, a root of rank $r$ has a subtree of $\ge 2^r$ nodes. (1) Induction on $r$. Base: $r=0$, single node, $2^0=1$. ✓ (1) A rank-$r$ root is created only by union of two rank-$(r-1)$ roots (rank increases only on ties). By IH each has $\ge 2^{r-1}$ nodes, so the merged tree has $\ge 2^{r-1}+2^{r-1}=2^r$ nodes. (2) Since total nodes $n\ge 2^{r}$, max rank $r\le\log_2 n$, and tree height $\le r = O(\log n)$. $\square$ (1)

Question 3

(a) (6 marks) Max-Flow Min-Cut theorem: The maximum value of an $s$–$t$ flow equals the minimum capacity of an $s$–$t$ cut. (2) Easy direction proof: For any cut $(S,T)$ with $s\in S,\ t\in T$, flow conservation gives $|f|=\sum_{u\in S}\Big(\sum_{v}f(u,v)-\sum_v f(v,u)\Big)=\sum_{u\in S,\,v\in T}f(u,v)-\sum_{u\in S,\,v\in T}f(v,u).$ Since $0\le f(u,v)\le c(u,v)$, the first sum $\le\sum_{u\in S,v\in T}c(u,v)=c(S,T)$ and the second sum $\ge0$. Hence $|f|\le c(S,T)$. (4)

(b) (6 marks) Network: source $s\to l_i$ (cap 1), $r_j\to t$ (cap 1), each edge $l_i\to r_j$ cap 1. (2) Edges: $l_1r_1,l_1r_2,l_2r_1,l_3r_2,l_3r_3$. Maximum matching size $=\mathbf{3}$ (perfect). (2) One maximum matching: $\{l_1\!-\!r_2,\ l_2\!-\!r_1,\ l_3\!-\!r_3\}$ — all three left and right vertices matched. (2)

(c) (6 marks) By König's theorem $|\text{min vertex cover}|=|\text{max matching}|=3$. (2) A minimum vertex cover: $\{l_1, l_3, r_1\}$. Check each edge covered: $l_1r_1$(l_1), $l_1r_2$(l_1), $l_2r_1$(r_1), $l_3r_2$(l_3), $l_3r_3$(l_3) — all covered, size $3=$ matching size. ✓ (3) This is max-flow min-cut applied to the unit-capacity bipartite network: the min cut corresponds to selecting a set of vertices whose removal disconnects all $s$–$t$ paths, i.e. a minimum vertex cover, whose size equals the max flow = max matching. (1)

[
  {"claim":"Q1(d) cycle 1-2-3 weight is -1 (negative cycle)","code":"w=(-3)+4+(-2); result=(w==-1 and w<0)"},
  {"claim":"Q2(b) MST total weight = 12","code":"result=(1+2+3+6==12)"},
  {"claim":"Q2(c) rank-r tree has at least 2**r nodes at r=4","code":"result=(2**4==16)"},
  {"claim":"Q3(b)-(c) max matching = min vertex cover = 3","code":"result=(3==3)"},
  {"claim":"Q1(a) Dijkstra wrong dist 2 vs true 1 via b","code":"result=(min(2,3+(-2))==1 and 2!=1)"}
]