《图论杂项问题.ppt》由会员分享，可在线阅读，更多相关《图论杂项问题.ppt（48页珍藏版）》请在三一办公上搜索。
1、图论杂项问题,何亮,最大闭合子图,闭合子图(closure)是指，若X在该集合中，则X的后继结点也必须在该集合中给定任意有向图，点上有权值（可正可负），求出权值总和最大的闭合子图。,最大闭合子图,解法：添加源S和汇T，S到所有正权值的点连边，容量为该点权值。所有负权值的点到T连边，容量为该点权值绝对值。原图中的边保留，容量为正无穷。求此图最小割C，则(正权值总和-C)即为所求。与S同侧的割集即为选出的闭合子图中的点（除去S点）。,最大闭合子图,解释：割的容量由两部分组成：(1)未被选入闭合子图的正权值点(2)被选入闭合子图的负权值点“闭合”的限制对应“割”的定义：若某点属于S集而它的后继属于T
2、集，则割容量为无穷大，不可能出现,最大密度子图,给定一个无向图，要求它的一个子图（点集和边集都是原图的子集），使得子图中边数与点数的比值最大。,最大密度子图,涉及比值的问题常见思路二分答案所谓0-1分数规划问题E.g.最优比率生成树，最小平均环路模型：给定N对数(ai,bi)，要求从中选出一部分来，使得a/b最小,分数规划,由每对(ai,bi)，我们求得一系列新值 ai k*bi。现在的问题中，从中找出若干个新值，使得其总和(ai-k*bi)最小（这是一个很简单的问题），也就是ai-kbi最小。ai-kbi 0 ai/bi k若这个最小总和0，说明k值假定得大了。反之说明k小了。于是可以缩小二
3、分的范围，直至找到恰好等于0的解。注意精度,分数规划,最优比率生成树每边有两权值(a,b)，求a/b最小的生成树边权变为a-k*b后求MST，看是否0最小平均环路每边有两权值(a,b)，在图中找一个环，使得环上所有的a/b最小边权变成a-k*b后，Bellman-ford(SPFA)找负环,最大密度子图,回到原题，密度定义|E|/|V|=k假设答案为k，则要求解的问题是：选出一个合适的点集V和边集E，令(|E|-k*|V|)取得最大值所谓“合适”是指满足如下限制：若选择某条边，则必选择其两端点,最大密度子图,以原图的边作为左侧顶点，则原图的点作为右侧顶点。左侧点有正权值+1，右侧点有负权值-k
4、若原图中存在边(u,v)，则新图中添加两条边(uvu),(uvv),最大权闭合子图!,最大密度子图,新图中点数为m+n，不太理想。能否只用原图中的点建立网络？,最大密度子图,如上图，要统计的边为点集关联的所有边除去红色的边可发现红色的边恰为一个割Max|E|-k*|V|-Mink*|V|-|E|E|=(|V|中点度数之和(|V|与|V|的补之割)/2,最大密度子图,|E|=V中点度数之和(V与V的补之割)/2=(vVdv cV,V)/2为便于计算，扩大2倍，化简得,最大密度子图,选出一个点集V，里面每选一个点v的花费是2k-dv，这部分花费再加上V和它的补集之前的割，要求总和最小能否把这个总和
5、计入一个割里？,最大密度子图,把原图的无向边变成双向的有向边（注：此处没有必要拆点），容量为1。添加S,T。添加从S到每个点的边，容量为0(why?)。对每个点添加指向T的边，容量为2k-dv,求此网络的最小割。注意：边权为负怎么办？,最大密度子图,对于此题，处理方法很简单，对每条从S发出和指向T的边，都增加一个足够大的值U，使得所有边权非负。此时总的最大流值增加U*n。设上述最大流（最小割）为C，则判断C-U*n的正负情况，即可决定开始猜测的k是偏大还是偏小。,最大密度子图,凸费用流问题,凸函数：函数的曲线始终在其切线上方f(y)=f(x)+f(x)(y-x)例如 y=x2(x0)凸费用流问
6、题是指，费用与流量成凸函数关系（而不是经典的线性关系）,凸费用流问题,因为流量常限定为整数，故费用函数可看作“分段”为凸。类似下图所示：,凸费用流问题,一个实用解法：拆边根据费用函数的“折点”把边拆成费用不同的若干条边。例如：某边容量上限为3，费用为f(x)=x2则可把该边拆成3条边，容量均为1，费用依次为12-02=1,22 12=3,32 22=5,凸费用流问题,由费用流的“贪心”性质可知，若某两点之间有多条边，必然会先填满费用较小的边。故当此边流过1个流量时，费用为1，流量为2时，费用为1+3=4，依次类推思考：为什么要限定“凸”？,平面图最大流,与普通流网络的唯一不同：图是由平面图构建
7、而来即平面图中的一块区域作为一个点，相邻区域之间连边所得到的图有何特殊性质？,平面图最大流,ACM Beijing 2006如下图所示，边上有权值，要阻断从左上角到右下角的的全部路，最小花费多少1000*1000矩阵,平面图最大流,S,T,平面图最大流,把每个面当作一个点，原问题转变为求S到T的最短路问题,无向图最小割,与普通最小割不同之处：不限定源与汇，随便割成两部分即可枚举？可以比O(n2)次最大流更快么？,无向图最小割,只需O(n)次最大流，但我们可以更快Stoer-Wagner算法O(n3),无向图最小割,Maximum Adjacency Search 1.建立一个空的A集合。2.首
8、先随便在图上找一点，加入到A集合中。3.令w(A,x)是目前的A集合的每个点与x点之间所有的边的权重总和。逐次加入一个不在A中且w(A,x)最大的x点到A中。4.所有点都加入到A集合之后，各点加入的順序即为所求。,无向图最小割,intmap99;/adjacencymatrix intw9;/紀錄各個點到目前的A集合的距離 boolvisit9;/紀錄各個點是不是已找過 voidmaximum_adjacency_search()for(inti=0;imax)max=wi,s=i;visits=true;/加入s點到A集合 cout這次讀到第s點endl;/加入s點到A集合後，更新w(A,x
9、)的值。for(intt=0;tV;+t)if(!visitt)wt+=mapst;,无向图最小割,设得到的顺序是x1,x2xn，则x1,x2,xn-1与xn的割，必定是使得xn-1和xn不在同一集合里的所有割中最小的即上面程序里最后一次得到的max证明略,无向图最小割,“合并”点的操作：若把t点并到s点，则对所有x点，有mapsx=mapxs=mapsx+maptx若s,t在割的同一侧，合并以后不影响割值,无向图最小割,于是，我们求完此值以后，把xn-1和xn“合并”成一个点，继续下一次MAS，求得的就是使得xn-2与xn-1,xn不是同一集合中的最小割重复此过程直到缩为1个点，比较每次求得
10、的割的最小值即可MAS:O(n2)共做n次,正则二分图,正则二分图是指，所有点的度都为同一个值的二分图Hall定理：二分图G有完美匹配，当且仅当G满足Hall条件：对X集的任意子集S都有|S|=|N(S)|，N(S)表示S中的点在Y集中的相邻点组成的集合。,正则二分图,推论1：正则二分图必有完美匹配证明：设正则二分图所有点的度为k，则任意一个左侧点集的子集X关联|X|*k条边，这|X|*k条边至少关联右侧|X|个点（由鸽笼原理），故满足Hall定理的条件,正则二分图,推论2：k-正则二分图有k个边不重叠的完美匹配证明：由推论1，k-正则二分图必有完美匹配，把这个完美匹配去掉以后，变成k-1度的
11、正则二分图，仍存在完美匹配。依此类推。,正则二分图的匹配,求一个d=2k-度正则二分图的完美匹配通常的匹配算法复杂是O(VE)，此处可以更快么？,正则二分图的匹配,因为d为偶数，我们一定可以用O(E)时间在d-正则二分图中找出一个欧拉回路。然后，我们把这条欧拉回路中的边隔一条删掉一条，因为对每个点来说每一对入边和出边都恰好留下一条，你会发现得到了一个(d/2)-正则二分图。重复上面算法直到d=1，则完美匹配显然可得。而我们会惊奇地发现E+E/2+E/4+=2E，所以总的复杂度还是O(E)。,Havel定理,给定一个非负整数序列d1,d2,.dn，若存在一个无向图使得图中各点的度与此序列一一对应
12、，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。可图化的判定比较简单：d1+d2+.dn=0(mod2)。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。,Havel定理,Havel定理：我们把序列排成不增序，即d1=d2=.=dn，则d可简单图化当且仅当d=(d2-1,d3-1,.d(d1+1)-1,d(d1+2),d(d1+3),.dn)可简单图化。实际上也就是，我们把d排序以后，找出度最大的点(设度为d1)，把它和度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。,随机欧拉图,随机欧拉
13、图是指，从某个指定点V0开始，任意地走不重复的边，不论如何走都会走出一条欧拉回路。如何判断一个图是否随机欧拉图？,随机欧拉图,首先，如果图不满足欧拉回路存在的性质则肯定不是，下面讨论原图已经是欧拉图的情况。如果随机走的时候失败，说明一定是走到了某一点v，由此点出发的所有边都已经被走过了。容易发现，如果失败的话，最后停的点一定是出发的原点V0。因为如果是停在其它点，那么此点的入度一定比出度大一，但这与前提“图中存在欧拉回路”矛盾。,随机欧拉图,如果找欧拉路失败，那么是走了一个包含V0的回路，且除去这个回路上的所有边后，图中仍有边存在。由欧拉回路的性质易得，剩下的补图中，每个强连通分量都各自包含一
14、个自己的欧拉回路。整体算法：首先判断该图是否为欧拉图。如果不是，直接否定。然后我们试图找一个不包含V0的回路，如果能找到，那么该图就不是“随机欧拉图”，因为这时候就存在一种乱走的方案不包含这个回路。如果找不到，就可以确信原图是随机欧拉图。,最长路,能否把最短路算法稍做改进，变成求最长路？比如把dijkstra里的松弛操作的符号变一下方向可不可以？什么特殊情况下可以求？,最长路,无环的情况下可以求若不要求一定是简单路，则若图中存在正环（且正环与起止点连通），则最长路为无穷大若要求是简单路，此问题为NP难一个简单的解释：如果此问题有多项式解法，则Hamilton路有多项式解法,图论中的NPC/NP-Hard问题,Hamilton回路旅行售货员问题最大团最小点覆盖集最大独立集在二分图中上两个问题都可解,图论中的NPC/NP-Hard问题,子图同构问题最大割着色数最小支配集即使在二分图中仍然难解,
