使用Karger算法解决最小割问题

一、问题介绍

把图 G=(V, E) 的节点 V 分割成两个部分 S 和 S-V 的边的集合称为割，而最小割问题就是输⼊是⽆向图 G，求解把图 G 分割成两个部分的边数最⼩的割。而随机算法是指该算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。我们将使用随机算法中的Karger算法来解决最小割问题。

二、算法

Karger算法的基本思路是每次随机选择一条边，把边的两个端点合二为一。原来与这两个点邻接的点，现在把边连到合并后的节点去，把原来的点和边删除。当合并至只剩两个点时，相当于将原图的点划分成两个集合。这两个点之间的连边数就是形成的割的边数。Karger 算法属于蒙特卡洛随机算法，假设输⼊图有 n个节点，该算法能保证其得到正确解的概率为Pr(\frac{2}{n^{2}})。

三、代码实现

我使用python实现了使用Karger算法解决最小割问题。我使用字典G存储了图的邻接列表作为输入，输出的是割的边数以及边的信息，在karger算法中，会不断合并图中的顶点，当最后只剩下两个顶点的时候，只需查看邻接列表中顶点的邻接节点数就可以得到割的边数。同时我定义了一个字典V用来记录和最后得到分割的两个图，每当顶点合并时，我就会更新这个字典。最后通过这个字典中存储的两个图的顶点来得到割的边。

同时由于Karger算法不能保证得到最小割，我在实际实现中运行100次Karger算法来求最小割，在我的试验中，得到了最小割。

代码：

import sys
import copy
import random

def choose_random_key(G):
    v1 = random.choice(list(G.keys()))
    v2 = random.choice(list(G[v1]))
    return v1, v2

def karger(graph):
    G=copy.deepcopy(graph)
    keys=list(graph.keys())
    V={}
    for key in keys:
        V[key]=[]
        V[key].append(key)
    length = []
    while len(G) > 2:
        v1, v2 = choose_random_key(G) # 随机选择两个节点
        G[v1].extend(G[v2]) # 合并 v1 和 v2
        # 根据合并调整边的连接
        for x in G[v2]:
            G[x].remove(v2)
            G[x].append(v1)
        while v1 in G[v1]:#去环
            G[v1].remove(v1)
        del G[v2]
        V[v1].extend(V[v2])
        del V[v2]
    for key in G.keys(): # 得到最小割边的数量
        length.append(len(G[key]))
    return length[0],V

graph={1:[2,3,4],
      2:[1,3,4],
      3:[1,2,4,5,6],
      4:[1,2,3],
      5:[3,6,7,8],
      6:[3,5,7,8],
      7:[5,6,8],
      8:[5,6,7]}

currentLen=0
currentV={}
shortestLen=sys.maxsize
shortestV={}
for i in range(100):
   currentLen,currentV = karger(graph)
   if currentLen<shortestLen:
        shortestLen=currentLen
        shortestV=copy.deepcopy(currentV)

cut_edge=[]
keys=list(shortestV.keys())
for i in shortestV[keys[0]]:
    for j in shortestV[keys[1]]:
        if j in graph[i]:
            cut_edge.append([i,j])
print("the shortest length of cut is {}".format(shortestLen))
print("the cut edge is {}".format(cut_edge))

结果：

1 2	the shortest length of cut is 2 the cut edge is [[3, 6], [3, 5]]

四、结论

在本文中我成功地使用Karger算法解决了图的最小割问题，得到了一个图的最小割的边数，并通过一个字典来记录分割后的两个图的顶点信息，以此来得到割的边。同时由于Karger算法是一个随机算法，不能保证单次运行得到最小割，因此我循环多次Karger算法来尽可能地求得最小割。