Min-Cut E(S,T)={uw∈E|u∈S,v∈T} Undirected graph G(V,E) ·Too many cuts: there are 29()bi-partitions ·(will see later）only at most O(n)min-cuts Generate a random cut that is a min-cut with large enough probability?Min-Cut • Undirected graph • Too many cuts: • there are bi-partitions • (will see later) only at most min-cuts • Generate a random cut that is a min-cut with large enough probability? G(V, E) 2Ω(n) O(n2 ) T S E(S, T) = {uv ∈ E ∣ u ∈ S, v ∈ T}