动机
最小割把无向图分成两个非空部分,并使横跨两部分的边数最少。一种随机算法可以通过反复均匀随机地选取一条边并收缩它来找到最小割。收缩某个特定最小割每一侧内部的边会保持该割不变;收缩其中一条横跨边则会破坏该割。
算法并不知道哪些边横跨最小割。它的分析转而估计:在每个阶段都避开某个固定最小割的概率。对于大图,所得的成功概率很小,但独立重复运行可以将其放大。算法的输出始终是一个合法的割;随机性只影响该割是否为最小割。
定义
定义 6.2.1
(割与最小割的大小)
设 是具有 个顶点的连通无向多重图。平行边是互不相同的边副本;自环不横跨任何割,可以丢弃。割是原图顶点集的一个划分,分成两个非空集合。割的大小是两个端点分别位于两侧的边副本的个数。设 为最小割的大小;由连通性得 。
定义 6.2.2
(收缩与随机收缩算法)
收缩一条边,是指把它的两个端点合并为一个超顶点。保留平行边作为互不相同的副本,并丢弃合并时产生的自环。每个超顶点代表原图顶点的一个非空集合。随机收缩算法反复在当前所有边副本中均匀随机地选取一条,并收缩所选的边,直到恰好剩下两个超顶点为止。算法返回这两个超顶点所代表的原图顶点划分。
在分析中,从任意数量的边副本中均匀选取被视为理想的随机选择操作。基于有限随机比特的实现必须另行说明如何做到均匀采样,以及如何处理拒绝采样。
定理
定理 6.2.3
(单次运行的成功概率)
对于每个 的连通无向多重图,一次随机收缩运行返回最小割的概率至少为 。
定理 6.2.4
(独立重复)
进行 次独立运行,返回所找到的最小的割,未能返回最小割的概率至多为
证明
证明:保护一个最小割
证明
(固定最小割的存活)
固定一个特定的最小割 ,其大小为 。只要没有横跨该割的边被收缩,就称该割存活。若该割存活,则当前每个超顶点都完全位于某一侧。在算法停止之前,两侧仍然非空,并且仍有同样的 条边副本横跨两侧:横跨该固定割的边尚未被收缩,而且只要该割存活,它就不可能变成自环。
假设当前有 个超顶点且该割已存活。每个超顶点都代表原图顶点的一个非空真子集,因此由最小割的定义,从它出发的边数至少为 。对当前无自环的多重图计算度数,总度数至少为 ,因而边副本至少有 条。平行副本在度数之和与随机选取中都分别计数。
恰有 条当前边副本横跨该固定割。在此前一直存活的条件下,下一条被均匀选取的边横跨该割的概率至多为
因此在下一次收缩中保持该割的条件概率至少为 。把 的这些条件下界相乘:
当 时,乘积为空,等于 1,唯一的割已经被返回。如果该固定割一直存活到只剩两个超顶点,则每一侧至少含有一个超顶点,所以每一侧恰由一个超顶点代表。返回的割恰好就是该固定最小割。算法也可能因返回另一个最小割而成功,因此这给出的是总成功概率的下界。
证明透视
最小割的极小性用在哪里
证明只有一步不显然:它保护的是一个固定的最小割,而不是去问最终输出是不是最小割。 的极小性恰好用一次,即把每个度数的下界定为 。离开某个超顶点的边副本构成原图的一个割,而没有任何割小于 。由于保留了平行副本,无论已形成多少副本,这个度数计算都成立。连通性给出 ,所以比值 有定义。
同一步也说明为什么被保护的割必须是最小割:对大小为 的割,横跨概率只能被界定为 ,它可能超过一。乘积随后裂项相消, 只剩下 。论证得以收束,是因为存活的割在剩下两个超顶点时,恰好就是那个固定的割。
证明:重复运行
证明
(独立重复)
每次运行都从原图的全新副本出发,使用独立的随机选择,并在原图中评估返回的划分。每次运行成功的概率至少为 。由独立性,失败概率至多为 。初等不等式 给出指数界。
如果至少有一次运行返回最小割,那么所有返回的割中最小的那个大小为 :任何合法的割都不可能小于最小值。因此,只要有任何一次运行成功,返回所观察到的最小割就会成功。要使失败概率至多为 (),只需取
并向上取整为整数。该保证针对的是错过所有最小割的概率,而不是输出非法划分的概率。
为什么边收缩能保持一个割
当前的超顶点代表合并进它的所有原图顶点之并集。收缩一条当前的边,就是把它两端所代表的集合合并。如果两个集合位于固定割的同一侧,它们的并集仍在该侧,所以当前每个超顶点仍完全落在某一侧之内。端点位于不同侧的原图边,其端点仍然属于不同的超顶点,因而仍是横跨的边副本。内部的边可能变成自环并消失,但不改变横跨边的数目。
反之,收缩一条横跨该固定割的边,会产生含有两侧顶点的超顶点。之后对整个超顶点所做的任何划分都无法再把这些原图顶点分开,所以这个特定的割就丢失了。这两个陈述解释了存活事件,而无需假设收缩能同时保持所有的割。
条件概率的乘积并不要求各阶段的收缩选择相互独立。它使用的是相继存活事件概率的链式法则,以及一个对每个存活历史都成立的下界。独立性在之后单独的重复运行保证中才需要,那时每次完整运行都使用全新的随机选择。
例题详解
例题 6.2.5
(两个顶点)
两个顶点由三条平行边副本相连,它们已经是最终的两个超顶点。算法不进行任何收缩,以概率 1 返回唯一的割,其大小为三。公式给出 。
例题 6.2.6
(三角形)
在三角形中,每个把一个顶点分离出来的割大小都是二。算法收缩一条均匀随机选取的边,留下由两条平行边相连的两个超顶点。因此每一种可能的选择都返回最小割。定理的下界只有 ,所以它不一定是紧的。
例题 6.2.7
(平行边分别被采样)
假设当前的图中边 有两个副本,边 有一个副本。在边副本中均匀选取,选中 的某个副本的概率是 ,而不是 。若把每一对不同的端点平等对待,就会定义出另一种算法,并使所述的概率计算失效。
例题 6.2.8
(选取运行次数)
当 时,一次运行的成功概率保证至少为 。要使所给出的指数失败界至多为 ,可选取 次独立运行。它们的实际成功概率可以高于该保证。
四边形圈的计算
取圈 ,每条边各有一个副本,并固定把 与其余三个顶点分开的割。它的大小为二。第一次收缩恰好在选中 或 时避开该割,每条的概率为 ,所以固定割在第一步存活的概率为 。
如果收缩的是 ,当前的图有三个超顶点:、 和 。其余的边由原来的圈决定:–、– 以及 –,其中 – 来自 ,– 来自 ;被收缩的 边变成了自环并被丢弃。于是当前的图是一个有三个边副本的三角形。恰有一条边 – 位于非 的一侧之内,所以第二步的条件存活概率为 。收缩的是 的情形是对称的。因此固定割存活的概率为 ,等于 。
这个计算只追踪一个固定的割。即使隔离 的割被破坏,四边形圈的其他最小割仍可能被返回。事实上,第一次收缩之后图就成为三角形,再收缩任何一条边,都会剩下由两条边副本连接的两个超顶点。因此这个图上的每次运行都返回最小割,固定割的存活概率 只是成功概率的下界。
常见错误
反例模式
一次收缩可能破坏某个特定的最小割
在三角形中,固定隔离顶点 的割。收缩与 关联的任一条边,都会把该固定割的两侧合并,所以它不再存活。算法仍然可以返回另一个最小割。证明追踪一个固定的割以得到下界,这并不是所有可能的成功的必要条件。
常见错误
(丢弃平行边并不安全)
丢弃自环是安全的,因为自环不横跨当前超顶点的任何划分。丢弃平行边则不安全:每个副本都计入割的大小,并且必须体现在均匀采样的概率中。带权的变体需要另行建立采样与代价模型。
常见错误
(重复运行需要全新的随机性)
单次运行的下界并不会自动使各次重复相互独立。指数形式的失败概率计算假定每次运行都使用全新的独立选择。重复使用相关的随机选择可能使失败事件相关,需要另做分析。
运行时间与概率模型
一种直接的实现可以保存当前边副本的显式列表,每次收缩之后扫描该列表来更新端点并移除自环。这是多项式时间,尽管不一定是最快的实现。把运行重复 次,代价乘以 ,而 的对数决定了所述充分界所需的重复次数。
证明把均匀选取边副本视为精确成立。如果有限比特的实现使用拒绝采样,它应当说明自己的停止与误差保证,而不是默认每个边数都是 2 的幂。理想选择下的概率定理独立于这些实现细节而保持有效。
连通性保证:当剩余超顶点多于一个时,至少有一条边连接两个超顶点,因此算法可以继续进行。对于不连通的输入,最小割为零,可取一个连通分量与其余部分构成的割得到;盲目套用连通图的收缩证明,会出现除以 的情形。
评估返回的划分
最后剩下的两个超顶点编码了原图顶点的两个非空集合。直接的实现可以统计横跨这两个集合的原图边副本个数来评估该割,即使其收缩所用的数据结构已经改变或丢弃了内部的边。输出始终是合法的划分,所以它的代价不可能低于真正的最小值。正是这一单侧性质,使得重复运行可以选取最小的结果而不引入虚假的最小值。
算法在某些运行中可能返回非最小的割。成功概率定理是对每个连通输入成立的下界,而不是某个观察到的割为最优的证明。若要不依赖概率保证而验证单次运行的最优性,需要确定性的证书或独立的精确最小割方法。
存活论证迫使最小割至多有 n(n-1)/2 个,而圈图可以达到这个数目。
自然的下一个问题
一个图最多可以有多少个最小割?
存活论证迫使最小割至多有 n(n-1)/2 个,而圈图可以达到这个数目。
存活的证明适用于每一个最小割,所以每个最小割被输出的概率都至少是 。对不同的割,“输出恰为割 ”这些事件互不相交,概率之和至多为一。因此含 个顶点的连通图至多有 个最小割。这个数目可以达到:在 个顶点的圈图中,删去任意两条边都剩下两条路径,得到 个大小为二的最小割。上面的四边形圈例子正是这种情形,而且每次运行都成功。
总结
固定的最小割有 条横跨边,而仍存活的 个超顶点的图至少有 条边。各条件存活概率的乘积至少为 。独立运行放大了这一单侧的成功保证。
练习
快速检查
(当 时,单次运行的保证成功概率是多少?)
把 代入 。
解答 · 答案
该界为 。
快速检查
(为什么收缩之后要丢弃自环?)
想一想自环能否横跨超顶点的任何划分。
解答 · 答案
自环的两个端点在同一个超顶点内,所以它不横跨超顶点的任何划分,也就不可能对返回的割有所贡献。它不应被选作收缩的边。
快速检查
(对于 ,给出 次独立运行全部失败的概率的一个上界。)
使用单次运行的下界 及独立性。
解答 · 答案
单次运行的成功概率至少为 ,所以六次全部失败的概率至多为 。指数界 是另一个有效但稍弱的上界。
快速检查
(解释:只要有任意一次运行成功,各次运行中返回的最小割就是正确的。)
分别从两个方向比较所观察到的最小大小与 。
解答 · 答案
每次运行都返回合法的割,其大小至少为 。如果有一次运行返回大小 ,则所观察到的最小大小既至多为 又至少为 ,因此它是最小割。