Data Structures Algorithms 简明教程
Karger’s Minimum Cut Algorithm
考虑到像图像分割这样的实际应用，其中需要从图像中移除摄像头聚焦的对象。在这里，每个像素被视为一个节点，这些像素之间的容量被减小。遵循的算法是最小割算法。
Considering the real-world applications like image segmentation where objects that are focused by the camera need to be removed from the image. Here, each pixel is considered as a node and the capacity between these pixels is reduced. The algorithm that is followed is the minimum cut algorithm.
Minimum Cut 是在图（有向或无向）中移除最少数量的边，从而将图划分为多个独立的图或不相交的顶点集。
Minimum Cut is the removal of minimum number of edges in a graph (directed or undirected) such that the graph is divided into multiple separate graphs or disjoint set of vertices.
让我们看一个示例，以更清晰地理解达到的不相交集
Let us look at an example for a clearer understanding of disjoint sets achieved
边 {A, E} 和 {F, G} 是唯一松散粘合，可以轻松地从图中移除的边。因此，图的最小割为 2。
Edges {A, E} and {F, G} are the only ones loosely bonded to be removed easily from the graph. Hence, the minimum cut for the graph would be 2.
在移除边 A → E 和 F → G 之后，生成的图是 {A, B, C, D, G} 和 {E, F}。
The resultant graphs after removing the edges A → E and F → G are {A, B, C, D, G} and {E, F}.
Karger’s Minimum Cut 算法是一个随机算法，用于找到图的最小割。它使用蒙特卡罗方法，因此预期在时间限制内运行，并在获得输出时将误差最小化。但是，如果执行该算法多次，则误差的可能性会降低。karger 最小割算法中使用的图是没有权重的无向图。
Karger’s Minimum Cut algorithm is a randomized algorithm to find the minimum cut of a graph. It uses the monte carlo approach so it is expected to run within a time constraint and have a minimal error in achieving output. However, if the algorithm is executed multiple times the probability of the error is reduced. The graph used in karger’s minimum cut algorithm is undirected graph with no weights.
Karger’s Minimum Cut Algorithm
karger 的算法将图中的任意两个节点合并成一个节点，称为超级节点。两个节点之间的边收缩，并且连接其他相邻顶点的其他边可以连接到超级节点。
The karger’s algorithm merges any two nodes in the graph into one node which is known as a supernode. The edge between the two nodes is contracted and the other edges connecting other adjacent vertices can be attached to the supernode.
Algorithm
Step 1 − 从图 G 中选择任意一条随机边 [u, v] 进行收缩。
Step 1 − Choose any random edge [u, v] from the graph G to be contracted.
Step 2 − 合并这些顶点以形成一个超级节点，并将这些顶点的其他相邻节点的边连接到已形成的超级节点。如果存在，则删除自结点。
Step 2 − Merge the vertices to form a supernode and connect the edges of the other adjacent nodes of the vertices to the supernode formed. Remove the self nodes, if any.
Step 3 − 重复此过程，直到收缩的图中仅剩两个节点。
Step 3 − Repeat the process until there’s only two nodes left in the contracted graph.
Step 4 − 连接这两个节点的边是最小割边。
Step 4 − The edges connecting these two nodes are the minimum cut edges.
该算法并不总能给出最优输出，因此重复此过程多次以降低错误概率。
The algorithm does not always the give the optimal output so the process is repeated multiple times to decrease the probability of error.
Pseudocode
Kargers_MinCut(edge, V, E):
v = V
while(v > 2):
i=Random integer in the range [0, E-1]
s1=find(edge[i].u)
s2=find(edge[i].v)
if(s1 != s2):
v = v-1
union(u, v)
mincut=0
for(i in the range 0 to E-1):
s1=find(edge[i].u)
s2=find(edge[i].v)
if(s1 != s2):
mincut = mincut + 1
return mincutExample
对无向未加权图 G {V, E} 应用算法，其中 V 和 E 是图中存在的顶点和边的集合，让我们找到最小割 −
Applying the algorithm on an undirected unweighted graph G {V, E} where V and E are sets of vertices and edges present in the graph, let us find the minimum cut −
Step 1
Step 1
选择任意一条边，比如 A → B，并通过将两个顶点合并为一个超级节点来收缩该边。将相邻顶点边连接到超级节点。如果存在，则删除自环。
Choose any edge, say A → B, and contract the edge by merging the two vertices into one supernode. Connect the adjacent vertex edges to the supernode. Remove the self loops, if any.
Step 2
Step 2
收缩另一条边 (A, B) → C，因此超级节点变为 (A, B, C)，并且将相邻边连接到新形成的更大超级节点。
Contract another edge (A, B) → C, so the supernode will become (A, B, C) and the adjacent edges are connected to the newly formed bigger supernode.
Step 3
Step 3
节点 D 仅有一条边连接到超级节点和一条相邻边，因此更容易收缩并连接相邻边到形成的新超节点。
The node D only has one edge connected to the supernode and one adjacent edge so it will be easier to contract and connect the adjacent edge to the new supernode formed.
Step 4
Step 4
在 F 和 E 顶点中，F 与超级节点的结合更紧密，因此收缩连接 F 和 (A, B, C, D) 的边。
Among F and E vertices, F is more strongly bonded to the supernode, so the edges connecting F and (A, B, C, D) are contracted.
Step 5
Step 5
由于图中仅存在两个节点，因此边的数量是图的最终最小割。在这种情况下，给定图的最小割是 2 。
Since there are only two nodes present in the graph, the number of edges are the final minimum cut of the graph. In this case, the minimum cut of given graph is 2.
原始图的最小割是 2（E → D 和 E → F）。
The minimum cut of the original graph is 2 (E → D and E → F).