下载文档原格式
一般图上的推广的最小k——cut问题的求解算法摘要原始割集问题是图论几大经典问题之一，在实际中应用广泛。
割集问题有很多较为复杂的推广问题，如最小multicut问题和最小multiwaycut问题等。
本文主要讨论的是割集问题的另一推广问题最小k--cut问题，并且给出了一个时间复杂度为的近似算法求得该问题的可行解。
关键词推广；最小k--cut问题；近似算法0 引言割集问题在图论和组合优化中占有举足轻重的地位，几十年来一直受到广泛的重视。
原始的割集问题是指给定一个连通赋权图以及在中指定两个点，，问题是找的一个最小权重的边子集，使得与在中不连通。
1 推广的最小k--cut问题定义：给定连通赋权图及正整数和，其中，求的一个边子集，使得中恰有个连通分支，且每个连通分支，的顶点数满足条件，目标是：达到最小。
当且时，即连通分支数为2而每个连通分支的顶点数不受限制时，此问题就为图的原始cut问题它是多项式可解的，调用求最大流的MPM算法再根据最大流最小割集定理就可以求得图的原始cut问题的最优解且时间复杂度。
当时通过最大流算法不一定会找到最优解。
因为最大流算法只保证有两个连通分支，但是每个连通分支的顶点数不一定会小于。
当时此问题是难的，方法是将最小边multiwaycut问题归约到此问题。
任给连通赋权图的最小multiway cut问题的一个实例：，和的顶点子集，其中，称为终端点，最小multiway cut问题就是要求使得中的点在中不连通且达到最小。
构造限制性最小k--cut问题的一个实例，构造的方法：在中的每一个终端点处加入个点，，边的权重为无穷大，这样构造了新图求图的一个权重最小的边子集。
，使得有连通分支且每个连通分支的顶点数都小于。
这样就得到了限制性最小k--cut问题的一个实例。
若有一个多项式时间算法能够解决那么它也能解决实例。
因为通过算法求得的最优解，使得有连通分支且每个连通分支的顶点数都小于，因此中的任意两点是不可能在同一个连通分支的，若与在的同一连通分支，那么此连通分支的顶点数至少为与已知条件矛盾。
最小权路径集问题【解题报告】关键词：斯坦纳树、DP 套DP、最短路优化DP将这些路径分为若干个部分，使得每个部分都相交，不同部分不相交。
那么每个部分的所有路径的端点都连通。
记(,)f i S 表示使点i 与集合S 中每一个点都连通的最小代价。
其中{1,2,...,}S n ⊆。
那么有状态转移：（1）(,)(,)(,)f i S f i T f i S T ←+-，其中T S ⊂。
这一转移表示：将S 划分为若干个不相交子集，如果x 和(,)y x y k ≤不属于同一个子集，那么i 到x 、i 到y 的路径就不重合。
我们考虑像背包问题或者树形DP 一样，一个个地加入集合，就能够推出上述转移。
（2）(,)(,)(,)f i S f j S w i j ←+这一转移表示：一切从i 出发到集合S 中任一点的路径都两两重合。
首先，任意两点间最多有一条路径是被计算了答案的，不然一定不优。
所以，我们的第一步一定是重合的，也就得到上述转移。
这个转移由于可以相互转移，要使用SPFA（当然也可以用其他最短路算法）来转移。
这只是一部分的答案，最后再做一次DP 将这些合并起来就好了。
铃铛计数问题【解题报告】题面分析：在一棵有根树上进行单点修改，区间查询。
算法分析：首先应该想到暴力的解法，就是预处理父节点，每次修改把会影响到的点都改了，求和就直接区间求和。
期望得分：0pts优化１：区间求和很麻烦，我们可以想到用分块来维护s，查询的时候整块就直接加上去，不满的块暴力查询。
但是问题来了：如何实现修改？考虑到题目意思是单点修改，而修改时会对祖先产生影响，因故我们可以预处理出对应关系。
记：,i j f 表示点i 对第j 块产生影响的权值和。
记：i sum 表示第i 块的和，那么在修改的时候就可以直接用i tag 来记录对块i 的影响。
于是乎，区间查询的时候就可以用i i sum tag 计算出答案了。
对于整块的做法是如此的，但是问题又来了：不满的块要怎么暴力？不满的块单点暴力固然好算，不过因为考虑到s i 的实际意义，在进行单点修改的时候会很麻烦。
计算最小函数依赖集示例一、求最小依赖集的算法①根据推理规则的分解性，右部最小化②消除左边的冗余属性③消除冗余的FD（依赖）重点：操作步骤的顺序不能颠倒，颠倒了可能消除不了FD中左边冗余的属性，或冗余的依赖。
二、具体操作详解（以下两种意思相同，表述略有区别罢了）（1）右部最小化：右切，使每个函数依赖的右部仅有一个属性（2）规则最小化：除本求包（对每个函数依赖的左部做除本求包，求包的结果如果不包含本函数依赖的右部，本函数依赖保留；求包的结果如果包含了本函数依赖的右部，删除本函数依赖）（3）左部最小化注意，解题一定要先（3）后（2）三、例题，反例等反例，假如将②③步骤颠倒例：求**F＝{ABD→AC，C→BE，AD→BF，B→E}**的最小函数依赖集FmF_mFm注意：当在函数依赖已经改变的地方开始一个新步骤时，重写函数依赖集很重要，这样可以在下一步中方便引用。
第一步对F中的函数依赖运用分解原则来创建一个等价函数依赖集H，该集合中每一个函数依赖的右部是单个属性：H＝｛①ABD→A，②ABD→C，③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝第二步考察每一个函数依赖是否是必须的，去除非必要的函数依赖（1）ABD→A是平凡的函数依赖（就是A是ABD的子集，所以他是平凡的依赖），所以显然是非必要的函数依赖，因此去除。
保留在H中的函数依赖是H＝｛②ABD→C，③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝（2）考察ABD→C，去掉此函数依赖将会得到新的函数依赖集J ＝｛③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝。
如果ABD→C 是非必要的，则(ABD)J+(ABD)_J^+(ABD)J+=ABDFE，不包含C，因此ABD→C是必要的函数依赖，不能去掉。
H＝｛②ABD→C，③C→B，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝（3）考察C→B，J＝｛②ABD→C，④C→E，⑤AD→B，⑥AD→F，⑦B→E｝，则**CJ+C_J^+CJ+=CE**，不包含B，因此C→B 是必要的函数依赖，保留在H中。
最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）普⾥姆算法（Prim算法)思路：以点为⽬标构建最⼩⽣成树1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。
循环n-1次如下操作：（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标(2)打印此边，并将vk加⼊U中。
（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中以下图为例#include<bits/stdc++.h>using namespace std;#define MAXVEX 100#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;void CreateMGraph(MGraph *G) {int m, n, w; //vm-vn的权重wscanf("%d %d", &G->numVertexes, &G->numEdges);for(int i = 0; i < G->numVertexes; i++) {getchar();scanf("%c", &G->vexs[i]);}for(int i = 0; i < G->numVertexes; i++) {for(int j = 0; j < G->numVertexes; j++) {if(i == j) G->arc[i][j] = 0;else G->arc[i][j] = INF;}}for(int k = 0; k < G->numEdges; k++) {scanf("%d %d %d", &m, &n, &w);G->arc[m][n] = w;G->arc[n][m] = G->arc[m][n];}}void MiniSpanTree_Prim(MGraph G) {int min, j, k;int arjvex[MAXVEX]; //最⼩边在 U集合中的那个顶点的下标int lowcost[MAXVEX]; // 最⼩边上的权值//初始化,从点 V0开始找最⼩⽣成树Tarjvex[0] = 0; //arjvex[i] = j表⽰ V-U中集合中的 Vi点的最⼩边在U集合中的点为 Vjlowcost[0] = 0; //lowcost[i] = 0表⽰将点Vi纳⼊集合 U ，lowcost[i] = w表⽰ V-U中 Vi点到 U的最⼩权值for(int i = 1; i < G.numVertexes; i++) {lowcost[i] = G.arc[0][i];arjvex[i] = 0;}//根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩for(int i = 1; i < G.numVertexes; i++) {min = INF, j = 1, k = 0;//寻找 V-U到 U的最⼩权值minfor(j; j < G.numVertexes; j++) {// lowcost[j] != 0保证顶点在 V-U中，⽤k记录此时的最⼩权值边在 V-U中顶点的下标if(lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}}}printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);lowcost[k] = 0; //表⽰将Vk纳⼊ U//查找邻接矩阵Vk⾏的各个权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中for(int i = 1; i < G.numVertexes; i++) {if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {lowcost[i] = G.arc[k][i];arjvex[i] = k;}}}int main() {MGraph *G = (MGraph *)malloc(sizeof(MGraph));CreateMGraph(G);MiniSpanTree_Prim(*G);}/*input:4 5abcd0 1 20 2 20 3 71 2 42 3 8output:V[0]-V[1] weight = 2V[0]-V[2] weight = 2V[0]-V[3] weight = 7最⼩总权值: 11*/时间复杂度O(n^2)克鲁斯卡尔算法（Kruskal算法）思路：以边为⽬标进⾏构建最⼩⽣成树在边集中依次寻找最⼩权值边，若构建是不形成环路（利⽤parent数组记录各点的连通分量），则将其添加到最⼩⽣成树中。
求最小割（径）集的MOCUS＋程序
王占森; 牛希敏
【期刊名称】《《工业安全与防尘》》
【年(卷),期】1989(000)003
【摘要】随着企业安全管理水平的迅速提高,事故树分析法越来越广泛地被应用。
在事故树分析法中,求最小割(径)集是定性及定量分析事故的基础。
求事故树的最小割(径)集有多种方法,但计算量比较大,人工难以完成。
一些书籍中介绍的求最小割(径)集的Fussell算法,以及据此算法编制的部分原程序(称MOCUS),只给出了直接使用Fussell算法,求出最小割(径)集的方法叙述不多,而且存在问题。
为此,编制了一个适用于微型机的实用求解事故树最小割(径)集的程序。
主要从3个方面提高微型机的处理速度。
【总页数】2页(P4-5)
【作者】王占森; 牛希敏
【作者单位】不详
【正文语种】中文
【中图分类】F243.6
【相关文献】
1.应用Petri网的关联矩阵求最小割集的新方法 [J], 武滢;谢里阳;李进冬
2.求极大独立集的程序实现研究 [J], 李云;傅秀芬;何杰光;林茜卡
3.用最短径集算法求模式的最简编码 [J], 曹鲁寅
4.求取故障树最小割(径)集的状态向量合成法 [J], 王平;陈志业;高曙
5.用最小割径集编制安全检查表初探 [J], 周邦才
因版权原因，仅展示原文概要，查看原文内容请购买。
最小生成树的模型数学公式
最小生成树（Minimum Spanning Tree，简称MST）是一个连通图的生成树，它的权重之和最小。
对于一个图G=(V,E)，其中V为图中的顶点集合，E为边的集合。
假设G是一个连通无向图，权重函数w:E->R是一个从边集E到实数域R的映射。
上述问题的模型数学公式为：
最小生成树问题的数学模型为：在连通图G=(V,E)中，找出一个边子集T，使得该子集包含图中所有顶点，且图T是一个树（也即没有环），并且T的边的权重之和最小。
可以用如下的公式来表示MST问题：
min ∑w(u,v)
(u,v)∈E
s.t.
T⊆E
T是一棵树
V(T)=V(G)
其中，∑w(u,v)表示权重的和，(u,v)∈E表示(u,v)是图G中的边，T表示生成树的边子集，T⊆E表示T是边集E的子集，
V(T)=V(G)表示生成树包括图中所有的顶点。
最小生成树问题可通过贪心算法（如Prim算法、Kruskal算法等）来求解。
普里姆算法和克鲁斯卡尔算法在计算机科学中，图是一种常见的数据结构，它由顶点和边组成。
在图中，顶点代表对象，边代表对象间的关系。
因此，图的算法是计算机科学中的一个重要分支。
其中，普里姆算法和克鲁斯卡尔算法是两种常用的最小生成树算法。
一、普里姆算法普里姆算法是一种基于贪心策略的算法，用于查找连接给定图中所有顶点的最小生成树。
该算法的基本思想是从一个起始顶点开始，逐步地添加新的顶点，直到所有顶点都被覆盖。
具体步骤如下：1. 选择一个起始顶点，并将其标记为已访问。
2. 查找与已访问顶点相邻的未访问顶点中，权值最小的边。
3. 将该边与对应的顶点标记为已访问，并将边加入最小生成树中。
4. 重复步骤2和步骤3，直到所有顶点都被访问。
二、克鲁斯卡尔算法克鲁斯卡尔算法也是一种基于贪心策略的算法，用于查找连接给定图中所有顶点的最小生成树。
该算法的基本思想是将边按照权值从小到大排序，逐步地将边加入最小生成树中，直到所有顶点都被覆盖。
具体步骤如下：1. 将图中所有边按照权值从小到大排序。
2. 逐步地将边加入最小生成树中，直到所有顶点都被覆盖。
3. 在加入新边的过程中，如果新边连接的两个顶点已经在最小生成树中，那么不加入该边。
三、普里姆算法和克鲁斯卡尔算法的比较虽然普里姆算法和克鲁斯卡尔算法都可以用于查找连接给定图中所有顶点的最小生成树，但它们的实现方式有所不同。
普里姆算法的实现方式比较简单，适用于边稠密的图。
该算法的时间复杂度为O(n^2)，其中n为顶点数。
克鲁斯卡尔算法的实现方式较为复杂，适用于边稀疏的图。
该算法的时间复杂度为O(elog2e)，其中e为边数。
四、总结普里姆算法和克鲁斯卡尔算法都是常用的最小生成树算法。
它们的实现方式有所不同，适用于不同类型的图。
在实际应用中，需要根据图的特点选择合适的算法。
最小点覆盖算法
最小点覆盖算法是一种图论算法，用于在给定的无向图中找到一个最小的点集，使得这个点集中的每条边都至少有一个端点在其中。
这个点集被称为图的最小点覆盖。
最小点覆盖算法可以用于多种实际问题，例如在一个社交网络中找到最少的人数来覆盖所有的社交关系，或者在一个生物网络中找到最少的基因来覆盖所有的调控关系。
最小点覆盖算法可以通过将原图转化为一个二分图来求解。
具体来说，对于原图中的每个点，都将其分为两个节点，分别在二分图的左右两部分中。
对于原图中的每条边 (u, v)，都从左部的节点 u 向右部的节点 v 连接一条边。
这样构建出的二分图就保证了最小点覆盖的点集一定是二分图中的一个最小点覆盖。
最小点覆盖算法可以通过二分图匹配来求解。
具体来说，找到二分图的最大匹配，然后将匹配中的左部节点和右部节点的并集作为最小点覆盖。
这是因为对于任意一条边 (u, v)，它要么在最大匹配中被覆盖了，要么它的两个节点中至少有一个在最大匹配中。
因此，最大匹配中的节点集合一定是一个最小点覆盖。
- 1 -。
最小割集Stoer-Wagner算法初探
首先抄一些网上关于该算法裸的解释:
1.min=MAXINT，固定一个顶点P
2.从点P用“类似”prim的s算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边
3.计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min
4.合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并，这个好理解吧？）
5.转到2，合并N-1次后结束
6.min即为所求，输出min
第一眼看到这么"精辟"的解释感到很蛋疼，画了很多图研究了好一会儿，突然发现解释地有点可爱。
当然我并不是藐视这种解释，或许换个人看看会感觉解释地很自然，很清晰。
当然下面我就要解释一下它的可爱之处，和我对于该算法的理解。
(这里我将采用混着论述的方法)
如果你对该算法要干什么不是很清楚请先看一下poj的2914 Minimum Cut ，题目连接：/problem?id=2914
目的：将图划分成S 和T两部分
算法主线：每次搜索完后便找到了当前的最小割，这时更新最小割的值，同时将该点扔进集合。
Step1: 算法开始，随便找一点P，然后从P开始累加和P点相连的边的连通度，并将它存储在wage[i]数组中，算法演示：
这里的wage初始值都为0
Step2: 这一步是keypoint ，而且也是我觉得网上的解释比较可爱的地方，在step1之后，就得到了相应的wage值，如果我们找到当前wage值最大的那个点(如果有多个这样的点那么任选其一)，那么这时候这个点也就是在已选了P点之后能获得的最大的连通度的点，按照这个思路我们依次进行这个步骤: 在未访问过的点中找wage值最大的点，那么当算法进行到结束的时候，这时我们获得了这样的两个点S 和T ，其中T是最后找到的那个点，S是T刚刚前一个找到的点。
那么这时候就可以得到一条十分有用的性质:
wage[T] = 将T这个点分离这幅图的连通度之和，也就是说sum(T的连通度)
这条结论很容易证明：因为每次找到一个点u的时候都对和这个点相连的点v加上了一个从u到v的连通度g[u][v]（表示u,v之间点的连通度，即u，v有几条边连接），那么当当前的节点为T的时候，和T相连的所有的边的连通度必然都已经累加并存储在了wage[T]中。
这时我可以不假思索地说wage[T]为S和T中较小的点的割集，要理解这一点可以看下面的两种情况(且只会出现这两种情况):
Condition 1 :
Condition 2 :
你可以自己先模拟一下上文提到过的步骤。
这里必须明确一点，那就在step2 中我们并不关心选出来的wage[T]是否是全局的最小割，
我们只关心wage[T]是S或者T中的最小割。
以上面的两幅图来说就是，对于condition 1 由于S的选取早于T的选取也就是说在选择S或者T作为扩展的节点时，由于wage[S] >= wage[T] ，我们必须选S，接下来，如果当前节点是S那么无论是wage[S]还是wage[T]，都只剩下(2,3)这条边的连通度没有更新。
那么到底是应该更新S还是T，很明显我们应该更新T，因为在更新(2,3)边之前wage[S] >= wage[T] , 如果我们更新wage[T]那么获得的割集肯定是两者中较小的。
Condition 2 的情况分析于此类似（这里我就不再赘述了）。
这里提及一下，前面说我感到网上的算法描述很可爱，主要是首先step2和最大生成树更本一点关系也没有，只是模仿了最大生成树构造方法而已(形似而神不似)。
Step3：由于step2我们已经获得了S和T中的最小割，并且更新了最小割的值那么不妨将T扔到集合in_set 中，表示对T求割值已经ok了。
接下来提出一个绝妙的想法(当然不是我自己想出来的)，如果将S和T合并成一个点，并且更新S的相应元素的值，那么T便可以丢弃了。
如果这条想法可行的话那么点的规模便会减小。
只要扫描n - 1次便可以得到最终的解。
下面证明一下其可行性。
再次回到上面的两幅图，对于condition 1 ，只需将T移向S和S重合，那么原来和T相连的边，现在和S也相连了，这时候T和S在同一个连通块中，那么及时删去T也不会对后面的操作产生影响，原因：既然wage[T]表示S和T中的最小割，那么最小割必然不会是wage[S] + (S->T的连通度) , 而且我已经更新了最小割的值，那么现在即使将S和T合并也不会影响全局最小割的求解。
而对于condition 2 的解释更加简单。
Condition 2 中当当前扫描到的节点是T，那么wage[S] , wage[T]中已经保存了S和T 两个单节点的累计连通度之和。
所以当将S和T合并之时，已经将T独立了，而S和T中的最小割又不是wage[T] 那么，将S和T合并，并不会影响后面的计算。
好了就三步可以得出最小割了，时间复杂度为O(n^3) 或者O(n^2logn).
总结：keypoint: 处理的时候始终是对单点求最小割，多点的最小割通过合并可以转化成单点的最小割。
Code (Stoer-WagnerO(n^3)) :
typedef long long Type;
bool in_set[cy] , vis[cy];
Type wage[cy];
Type Search ( int n , int &S , int &T ){
memset ( vis , false , n * sizeof ( vis[0] ) );
memset ( wage , 0 , n * sizeof ( wage[0] ) );
S = T = -1;
Type min_cut ;
int u = 0;
for ( int i = 0 ; i < n ; i++ ){
Type mx = -INF;
for ( int j = 0 ; j < n ; j++ ){
if ( !in_set[j] && !vis[j] && mx < wage[j] ){
mx = wage[u = j];
}
}
if ( u == T ) return min_cut;
S = T ; T = u;
min_cut = mx;
vis[u] = true;
for ( int v = 0 ; v < n ; v++ ){
if ( !in_set[v] && !vis[v] ){
wage[v] += g[u][v];
}
}
}
return min_cut;
}
//n >= 2
//n个点m条边
Type Stoer_Wagner ( int n , int m ){
int S , T;
Type ans = INF , min_cut;
memset ( in_set , false , n * sizeof ( in_set[0] ) );
for ( int i = 1 ; i < n ; i++ ){
min_cut = Search ( n , S , T );
ans = min ( ans , min_cut );
if ( ans == 0 ) return ans;
in_set[T] = true;
for ( int j = 0 ; j < n ; j++ ){
if ( !in_set[j] && j != S ){
g[S][j] += g[T][j];
g[j][S] += g[j][T];
}
}
}
return ans;
}。
