图论杂项问题课件.ppt

《图论杂项问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论杂项问题何亮roba269gmail最大闭合子图闭合子图(closure)是指，若X在该集合中，则X的后继结点也必须在该集合中给定任意有向图，点上有权值（可正可负），求出权值总和最大的闭合子图。最大闭合子图解法：添加源S和汇T，S到所有正权值的点连边，容量为该点权值。所有负权值的点到T连边，容量为该点权值绝对值。原图中的边保留，容量为正无穷。求此图最小割C，则(正权值总和-C)即为所求。与S同侧的割集即为选出的闭合子图中的点（除去S点）。最大闭合子图解释：割的容量由两部分组成：(1)未被选入闭合子图的正权值点(2)被选入闭合子图的负权值点“闭合”的限制对应“割”的定义：若某点属于S集而它的

2、后继属于T集，则割容量为无穷大，不可能出现最大密度子图给定一个无向图，要求它的一个子图（点集和边集都是原图的子集），使得子图中边数与点数的比值最大。最大密度子图涉及比值的问题常见思路——二分答案所谓0-1分数规划问题E.g.最优比率生成树，最小平均环路模型：给定N对数(ai,bi)，要求从中选出一部分来，使得∑a/∑b最小分数规划由每对(ai,bi)，我们求得一系列新值ai–k*bi。现在的问题中，从中找出若干个新值，使得其总和∑(ai-k*bi)最小（这是一个很简单的问题），也就是∑ai-k∑bi最小。∑ai-k∑bi<0∑ai/∑bi

3、小了。于是可以缩小二分的范围，直至找到恰好等于0的解。[注意精度]分数规划最优比率生成树每边有两权值(a,b)，求∑a/∑b最小的生成树边权变为a-k*b后求MST，看是否<0最小平均环路每边有两权值(a,b)，在图中找一个环，使得环上所有的∑a/∑b最小边权变成a-k*b后，Bellman-ford(SPFA)找负环最大密度子图回到原题，密度定义

4、E

5、/

6、V

7、=k假设答案为k，则要求解的问题是：选出一个合适的点集V和边集E，令(

8、E

9、-k*

10、V

11、)取得最大值所谓“合适”是指满足如下限制：若选择某条边，则必选择其两端点最大密度子图以原图的边作为左侧顶点，则原图的点作为右侧顶点。左侧点有正权值+

12、1，右侧点有负权值-k若原图中存在边(u,v)，则新图中添加两条边([uv]u),([uv]v)最大权闭合子图!最大密度子图新图中点数为m+n，不太理想。能否只用原图中的点建立网络？最大密度子图如上图，要统计的边为点集关联的所有边除去红色的边可发现红色的边恰为一个割Max{

13、E

14、-k*

15、V

16、}-Min{k*

17、V

18、-

19、E

20、}

21、E

22、=(

23、V

24、中点度数之和–(

25、V

26、与

27、V

28、的补之割))/2最大密度子图

29、E

30、=V中点度数之和–(V与V的补之割))/2=(∑v∈Vdv–c[V,V’])/2为便于计算，扩大2倍，化简得最大密度子图选出一个点集V，里面每选一个点v的花费是2k-dv，这部分花费再加上V

31、和它的补集之前的割，要求总和最小能否把这个总和计入一个割里？最大密度子图把原图的无向边变成双向的有向边（注：此处没有必要拆点），容量为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-

32、x)例如y=x^2(x>0)凸费用流问题是指，费用与流量成凸函数关系（而不是经典的线性关系）凸费用流问题因为流量常限定为整数，故费用函数可看作“分段”为凸。类似下图所示：凸费用流问题一个实用解法：拆边根据费用函数的“折点”把边拆成费用不同的若干条边。例如：某边容量上限为3，费用为f(x)=x^2则可把该边拆成3条边，容量均为1，费用依次为1^2-0^2=1,2^2–1^2=3,3^2–2^2=5凸费用流问题由费用流的“贪心”性质可知，若某两点之间有多条边，必然会先填满费用较小的边。故当此边流过1个流量时，费用为1，流量为2时，费用为1+3=4，依次类推思考：为什么要限定“凸”？平面图最大流与普

33、通流网络的唯一不同：图是由平面图构建而来即平面图中的一块区域作为一个点，相邻区域之间连边所得到的图有何特殊性质？平面图最大流ACMBeijing2019如下图所示，边上有权值，要阻断从左上角到右下角的的全部路，最小花费多少1000*1000矩阵平面图最大流ST平面图最大流把每个面当作一个点，原问题转变为求S到T的最短路问题无向图最小割与普通最小割不同之处：不限定源与汇，随便割成两部分即可枚举？