图论杂项问题.pptVIP

图论杂项问题 何亮 roba269@ 最大闭合子图 闭合子图(closure)是指，若X在该集合中，则X的后继结点也必须在该集合中 给定任意有向图，点上有权值（可正可负），求出权值总和最大的闭合子图。 最大闭合子图 解法：添加源S和汇T，S到所有正权值的点连边，容量为该点权值。所有负权值的点到T连边，容量为该点权值绝对值。原图中的边保留，容量为正无穷。 求此图最小割C，则(正权值总和-C)即为所求。与S同侧的割集即为选出的闭合子图中的点（除去S点）。 最大闭合子图 解释： 割的容量由两部分组成： (1)未被选入闭合子图的正权值点 (2)被选入闭合子图的负权值点 “闭合”的限制对应“割”的定义： 若某点属于S集而它的后继属于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 k 若这个最小总和0，说明k值假定得大了。反之说明k小了。于是可以缩小二分的范围，直至找到恰好等于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 若原图中存在边(u,v)，则新图中添加两条边([uv]?u), ([uv]?v) 最大密度子图 新图中点数为m+n，不太理想。能否只用原图中的点建立网络？ 最大密度子图 如上图，要统计的边为点集关联的所有边除去红色的边 可发现红色的边恰为一个割 Max{|E| - k*|V|} ? - Min{k*|V| - |E|} |E| = (|V|中点度数之和 – (|V|与|V|的补之割)) / 2 最大密度子图 |E| = V中点度数之和 – (V与V的补之割)) / 2 = (∑v∈Vdv – c[V, V’]) / 2 为便于计算，扩大2倍，化简得 最大密度子图 选出一个点集V，里面每选一个点v的花费是2k-dv，这部分花费再加上V和它的补集之前的割，要求总和最小 能否把这个总和计入一个割里？ 最大密度子图 把原图的无向边变成双向的有向边（注：此处没有必要拆点），容量为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 = x^2 (x0) 凸费用流问题是指，费用与流量成凸函数关系（而不是经典的线性关系） 凸费用流问题 因为流量常限定为整数，故费用函数可看作“分段”为凸。类似下图所示： 凸费用流问题 一个实用解法：拆边 根据费用函数的“折点”把边拆成费用不同的若干条边。 例如：某边容量上限为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，依次类推 思考：为什么要限定“凸”？ 平面图最大流 与普通流网络的唯一不同：图是由平面图构建而来 即平面图中的一块