时间：2022-05-08 11:22:50
摘 要 原始割集问题是图论几大经典问题之一，在实际中应用广泛。割集问题有很多较为复杂的推广问题，如最小multicut问题和最小multiwaycut问题等。本文主要讨论的是割集问题的另一推广问题最小k--cut问题，并且给出了一个时间复杂度为的近似算法求得该问题的可行解。
关键词 推广；最小k--cut问题；近似算法
中图分类号O29 文献标识码A 文章编号 1674-6708（2014）119-0140-02
0 引言
割集问题在图论和组合优化中占有举足轻重的地位，几十年来一直受到广泛的重视。 原始的割集问题是指给定一个连通赋权图以及在中指定两个点，，问题是找的一个最小权重的边子集，使得与在中不连通。
1 推广的最小k--cut问题
定义：给定连通赋权图及正整数和，其中，求的一个边子集，使得中恰有个连通分支，且每个连通分支，的顶点数满足条件，目标是：达到最小。
当且时，即连通分支数为2而每个连通分支的顶点数不受限制时，此问题就为图的原始cut问题它是多项式可解的，调用求最大流的MPM算法再根据最大流最小割集定理就可以求得图的原始cut问题的最优解且时间复杂度 。
当时通过最大流算法不一定会找到最优解。因为最大流算法只保证有两个连通分支，但是每个连通分支的顶点数不一定会小于。
当时此问题是难的，方法是将最小边multiwaycut问题归约到此问题。任给连通赋权图的最小multiway cut问题的一个实例：，和的顶点子集，其中 ，称为终端点，最小multiway cut问题就是要求使得中的点在中不连通且达到最小。构造限制性最小k--cut问题的一个实例，构造的方法：在中的每一个终端点处加入个点，，边的权重为无穷大，这样构造了新图求图的一个权重最小的边子集。
，使得有连通分支且每个连通分支的顶点数都小于。这样就得到了限制性最小k--cut问题的一个实例。若有一个多项式时间算法能够解决那么它也能解决实例。因为通过算法求得的最优解，使得有连通分支且每个连通分支的顶点数都小于，因此中的任意两点是不可能在同一个连通分支的，若与在的同一连通分支，那么此连通分支的顶点数至少为与已知条件矛盾。因此也是实例的最优解而最小multiway cut问题是难的。当时，Calinesca，karloff和Rabani[1]设计了的近似算法。
2 算法设计
Input： 连通赋权图，及正整数和
Output：无解或可行解
第1步：计算，If ，则输出“无解”，Else ，转第2步；
第2步：去掉 的所有边放入集合中，此时中恰有个连通分支，若，输出最优解，若，转第3步；
第3步：对中的所有边按权重进行从大到小的顺序排列：
第4步：从中权重最大的边开始试着加入，此时恰有个连通分支，且每一个连通分支的顶点数小于等于2，若，令，输出最优解。若，则继续从中权重最大的边开始试着加入，此时中恰有个连通分支，且每个连通分支的顶点数都小于等于3，若，令输出最优解，若，则继续考虑中权重最大的边，若加入中连通分支数大于，且每个连通分支的顶点数小于等于，令则继续依此考虑重复进行下去。若加入中，连通分支数大于，且存在连通分支的顶点数大于，此时考虑中下一条权重大的边，一直重复上述过程直到中的所有边都考虑完为止，此时得到
第5步：输出。
算法正确性分析：算法第4步首先从中权重最大的边开始试着加入中，每一次加入都要保证连通分支数减小且每个连通分支的顶点数都小于等于。直到连通分支数等于且每一个连通分支的顶点数都小于等于。因此整个算法结束就得到了限制性k--cut问题的解。
算法的时间复杂度分析：算法时间复杂度主要是第3步和第4步，第3步是对的所有边进行降序排列，采用二分法，其时间复杂度为，第4步是检验中的每一条边时间复杂度为，所以整个算法的时间复杂度为。
3实例
应用上述算法求解如下：
第一步：，计算，，问题有解。
第二步：去掉的所有边放入中，则，第三步：对中边按权重进行降序排列。
令。
第四步：在中试着加入权重最大的边，当在中加入时，连通分支数5且每个连通分支的顶点数都小于等于2，令。
因为的连通分支数大于3，因此继续实施算法，在中试着加入权重最大的边，当在中加入时，连通分支数4且每个连通分支的顶点数都小于等于3，令。
因为的连通分支数大于3，因此继续实施算法，在中试着加入权重最大的边，当在中加入时，连通分支数3且每个连通分支的顶点数都小于等于3，令。
4 结论
本文主要讨论的是k--cut问题的一类推广问题制性的最小k--cut，文中首先说明了此问题是难的，其次设计了一个时间复杂度为的算法求得问题的可行解，易于实现计算机求解。需要指出的是，该算法只能找到一个可行解。故如何进一步改进算法，找到近似度高的算法是下一步将要研究的方向。