割与最小割

contract(G):
   Input graph G=(V,E) with |V|>=2 vertices
   Output cut of G

   while |V|>2 do
      randomly select e∈E
      contract edge e in G
   end while 
   return the only cut in G

MinCut(G):
   Input graph G with V>=2 vertices
   Output smallest cut found

   min_weight=∞, d=0
   repeat 
      cut=contact(G) // 获取当前的割
      if weight(cut)<min_weight then // 如果当前割的权重小于最小割
         min_cut=cut, min_weight=weight(cut) // 就把当前割赋值为最小割，并且将最小权重记录为当前割的权重
      end if
      d=d+1
      until d>binomial(V,2).lnV // 等于说对图中的边两两组合的枚举
      return min_cut