Graph Cut

• For a graph G = (V,E), graph cut C = (V_A,V_B) is a partition of vertices V into 2 disjoint subsets V_A and V_B
• cut-set: set of edges that cut the graph, i.e. set of edges whose vertices are in different subsets of the partition.
• cost: sum of weights of cut-set edges
•