图的最小割集随机化算法

The randomized algorithms of the minimum cut set of diagram

一个有n个顶点的图G=(V,E),其割集C是一个边的集合,当去掉这些边时将图分成两个或多个连通部分,称C为两路割集或r(r≥3)路割集。最小割问题就是在图G中寻找一个基数最小的割集。

A graph G =(V,E)with n vertex,the cut set C is a set of edges,when these edges will figure into two or more connected components,called C is two cut set or r(r ≥ 3) cut set.The problem of minimum cut is to look for a minimal cut set of cardinality in fig G.