图论杂项问题.ppt

《图论杂项问题.ppt》由会员分享，可在线阅读，更多相关《图论杂项问题.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论杂项问题 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望最大闭合子图o闭合子图(closure)是指，若X在该集合中，则X的后继结点也必须在该集合中o给定任意有向图，点上有权值（可正可负），求出权值总和最大的闭合子图。最大闭合子图o解法：添加源S和汇T，S到所有正权值的点连边，容量为该点权值。所有负权值的点到T连边，容量为该点权值绝对值。原图中的边保留，容量为正无穷。o求此图最小割C，则(正权值总和-C)即为所求。与S同侧的割集即为选出的闭合子图中的点（除去S

2、点）。最大闭合子图o解释：n割的容量由两部分组成：n(1)未被选入闭合子图的正权值点n(2)被选入闭合子图的负权值点n“闭合”的限制对应“割”的定义：n若某点属于S集而它的后继属于T集，则割容量为无穷大，不可能出现最大密度子图o给定一个无向图，要求它的一个子图（点集和边集都是原图的子集），使得子图中边数与点数的比值最大。最大密度子图o涉及比值的问题常见思路二分答案o所谓0-1分数规划问题nE.g.最优比率生成树，最小平均环路o模型：给定N对数(ai,bi)，要求从中选出一部分来，使得a/b最小分数规划o由每对(ai,bi)，我们求得一系列新值aik*bi。现在的问题中，从中找出若干个新值，使得

3、其总和(ai-k*bi)最小（这是一个很简单的问题），也就是ai-kbi最小。oai-kbi0ai/biko若这个最小总和0，说明k值假定得大了。反之说明k小了。于是可以缩小二分的范围，直至找到恰好等于0的解。注意精度分数规划o最优比率生成树n每边有两权值(a,b)，求a/b最小的生成树n边权变为a-k*b后求MST，看是否=f(x)+f(x)(y-x)o例如y=x2(x0)o凸费用流问题是指，费用与流量成凸函数关系（而不是经典的线性关系）凸费用流问题o因为流量常限定为整数，故费用函数可看作“分段”为凸。类似下图所示：凸费用流问题o一个实用解法：拆边o根据费用函数的“折点”把边拆成费用不同的若

4、干条边。o例如：某边容量上限为3，费用为f(x)=x2o则可把该边拆成3条边，容量均为1，费用依次为12-02=1,2212=3,3222=5凸费用流问题o由费用流的“贪心”性质可知，若某两点之间有多条边，必然会先填满费用较小的边。故当此边流过1个流量时，费用为1，流量为2时，费用为1+3=4，依次类推o思考：为什么要限定“凸”？平面图最大流o与普通流网络的唯一不同：图是由平面图构建而来n即平面图中的一块区域作为一个点，相邻区域之间连边所得到的图o有何特殊性质？平面图最大流oACMBeijing2006o如下图所示，边上有权值，要阻断从左上角到右下角的的全部路，最小花费多少o1000*1000

5、矩阵平面图最大流ST平面图最大流o把每个面当作一个点，原问题转变为求S到T的最短路问题无向图最小割o与普通最小割不同之处：不限定源与汇，随便割成两部分即可o枚举？n可以比O(n2)次最大流更快么？无向图最小割o只需O(n)次最大流，但我们可以更快oStoer-Wagner算法oO(n3)无向图最小割oMaximumAdjacencySearchn1.建立一个空的A集合。n2.首先随便在图上找一点，加入到A集合中。n3.令w(A,x)是目前的A集合的每个点与x点之间所有的边的权重总和总和。逐次加入一个不在A中且w(A,x)最大的x点到A中。n4.所有点都加入到A集合之后，各点加入的順序即为所求。

6、无向图最小割intmap99;/adjacencymatrixintw9;/紀錄各個點到目前的A集合的距離boolvisit9;/紀錄各個點是不是已找過voidmaximum_adjacency_search()for(inti=0;i9;i+)visiti=false;/initializefor(inti=0;i9;i+)wi=0;for(inti=0;iV;+i)/找出一個尚未加入A當中、且w(A,x)最大的x點。ints=0,max=-1e9;for(intj=0;jmax)max=wi,s=i;visits=true;/加入s點到A集合cout這次讀到第s點endl;/加入s點到A集

7、合後，更新w(A,x)的值。for(intt=0;tV;+t)if(!visitt)wt+=mapst;无向图最小割o设得到的顺序是x1,x2xn，则x1,x2,xn-1与xn的割，必定是使得xn-1和xn不在同一集合里的所有割中最小的n即上面程序里最后一次得到的maxn证明略无向图最小割o“合并”点的操作：n若把t点并到s点，则对所有x点，有nmapsx=mapxs=mapsx+maptxo若s,t在割的同一侧，合并以后不影响割值无向图最小割o于是，我们求完此值以后，把xn-1和xn“合并”成一个点，继续下一次MAS，求得的就是使得xn-2与xn-1,xn不是同一集合中的最小割o重复此过程直

8、到缩为1个点，比较每次求得的割的最小值即可oMAS:O(n2)共做n次正则二分图o正则二分图是指，所有点的度都为同一个值的二分图oHall定理：二分图G有完美匹配，当且仅当G满足Hall条件：对X集的任意子集S都有|S|=d2=.=dn，则d可简单图化当且仅当d=(d2-1,d3-1,.d(d1+1)-1,d(d1+2),d(d1+3),.dn)可简单图化。o实际上也就是，我们把d排序以后，找出度最大的点(设度为d1)，把它和度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。随机欧拉图o随机欧拉图是指，从某个指定点V0开始，任意

9、地走不重复的边，不论如何走都会走出一条欧拉回路。o如何判断一个图是否随机欧拉图？随机欧拉图o首先，如果图不满足欧拉回路存在的性质则肯定不是，下面讨论原图已经是欧拉图的情况。o如果随机走的时候失败，说明一定是走到了某一点v，由此点出发的所有边都已经被走过了。容易发现，如果失败的话，最后停的点一定是出发的原点V0。因为如果是停在其它点，那么此点的入度一定比出度大一，但这与前提“图中存在欧拉回路”矛盾。随机欧拉图o如果找欧拉路失败，那么是走了一个包含V0的回路，且除去这个回路上的所有边后，图中仍有边存在。由欧拉回路的性质易得，剩下的补图中，每个强连通分量都各自包含一个自己的欧拉回路。o整体算法：首先

10、判断该图是否为欧拉图。如果不是，直接否定。然后我们试图找一个不包含V0的回路，如果能找到，那么该图就不是“随机欧拉图”，因为这时候就存在一种乱走的方案不包含这个回路。如果找不到，就可以确信原图是随机欧拉图。最长路o能否把最短路算法稍做改进，变成求最长路？o比如把dijkstra里的松弛操作的符号变一下方向可不可以？o什么特殊情况下可以求？最长路o无环的情况下可以求o若不要求一定是简单路，则n若图中存在正环（且正环与起止点连通），则最长路为无穷大o若要求是简单路，此问题为NP难n一个简单的解释：如果此问题有多项式解法，则Hamilton路有多项式解法图论中的NPC/NP-Hard问题oHamilton回路o旅行售货员问题o最大团o最小点覆盖集o最大独立集n在二分图中上两个问题都可解图论中的NPC/NP-Hard问题o子图同构问题o最大割o着色数o最小支配集n即使在二分图中仍然难解