Min-cut for undirected graphs Given an undirected graph,a global min-cut is a cut (S,V-S) minimizing the number of crossing edges. Recall:a crossing edge is an edge (u,v)s.t.uES andv∈V-S. V-S S 14Min-cut for undirected graphs ◼ Given an undirected graph, a global min-cut is a cut (𝑆, 𝑉 − 𝑆) minimizing the number of crossing edges. ❑ Recall: a crossing edge is an edge (𝑢, 𝑣) s.t. 𝑢 ∈ 𝑆 and 𝑣 ∈ 𝑉 − 𝑆. V - S S 14