动机
稳健路线需要不会一同失效的备选路径,但边与顶点是不同资源。两条路径可无公共边,却共用关键的中间顶点。因此,同一端点对的删边问题和删点问题可以有不同答案。
Menger 定理把最多的不交路径与阻断所有路线的最小分隔集联系起来。路径族给出可行性下界,分隔集给出最优性上界。本章从已证明的整数最大流最小割定理推导两种等式,逐项解释化归模型,而不略过建模步骤。
定义
定义 9.2.1
(不交路径与分隔集)
设 为有限简单无向图, 为两个不同的顶点。本章中的路径均为简单路径。若若干条路径没有公共边,则称它们是边不交的,它们可以共享顶点。若它们仅有的公共顶点是端点 ,则称它们是内部顶点不交的。边分隔集是这样一个边的集合:删去它之后不再存在 – 路径。内部顶点分隔集是 的一个子集:删去它之后不再存在这样的路径。
如果两个端点本来就不连通,则允许取空分隔集,同时需要选取的路线数为零。内部顶点形式的定理将假设端点不相邻。如果有一条边直接连接两个端点,那么删除内部顶点永远无法摧毁这条边,因此所述的分隔集问题没有有限解。
对于包含 但不包含 的顶点集 ,令 为恰有一个端点在 内、另一个端点在 外的无向边的集合。这样的边界是一个边分隔集。反过来,删去任意一个边分隔集之后,取从 可达的顶点集,则它的边界上的每条边都必然已被删去。因此,最小分隔集的大小等于最小边界的大小。
定理/命题
定理 9.2.2
(有限无向图 Menger 定理的边形式)
两两边不交的 – 路径的最大条数等于边分隔集的最小大小。等价地,它等于 。无论 是否相邻,该命题都成立。
定理 9.2.3
(有限无向图 Menger 定理的内部顶点形式)
若 是两个不同且不相邻的顶点,则内部顶点不交的 – 路径的最大条数等于内部顶点分隔集的最小大小。端点永远不会被删除,也不计入内部顶点。
任何分隔集都必须与每一条所选路径相交。对于不交路径,分隔集中被删除的各个资源必须互不相同。这就给出了两个定理中容易的那个不等式。实质性的部分是反方向:最小大小的阻断集总能与同样数量的相容路线相匹配。
证明思路或证明
我们使用下面已经建立的流的结果。具有非负整数容量的有限有向网络存在整数最大流,其值等于最小割的容量。允许有弧进入源点或离开汇点;流的值指源点处的净流出量。当用方向相反的两条弧替换无向边时,这一精确表述是有用的。
以下引理把流转化为路线。
引理 9.2.4
(整数流可分解为路径)
设 是有限有向网络中从源点 到汇点 的非负整数流,其值为 。则存在简单有向 – 路径 (允许重复),使每条弧 至多位于其中 条上。
证明
(逐条移去正流路径的证明)
若流值为正,则存在一条从源点到汇点的、流为正的有向路径。否则,设 为从源点出发经由正流弧可达的顶点集。没有正流离开 ,所以其净流出量非正。但由守恒性及汇点不在 内,这个净流出量应等于正的源点流值,矛盾。取一条简单的正流路径,并从中减去其最小的正弧流量。这保持了守恒性,并使流值减少一个正整数。重复这一过程即可提取出承载全部流值的路径;剩下的值为零的环流可以丢弃。承载多个单位流的路径按相应重数列出。由于每次相减后流仍为非负,所列路径使用每条弧 至多 次。
证明
(边形式的证明)
把每条无向边 替换为弧 与 ,每条弧容量为一。一个有向割对每条无向边界边恰有一条向外的弧,所以最小割容量等于最小边分隔集的大小。取一个整数最大流。
方向相反的两条弧可能各承载一个单位的流。把两者流量中较小者从两条弧上同时减去。在每个端点处,流入与流出被减去相同的量,所以守恒性与净值都不变。全部抵消之后,每条原始边至多有一个方向的流为正。把这个流分解为路径。由于弧的容量为一,提取出的路径使用互不相同的弧;又因为相反方向的正流已被消除,它们也使用互不相同的无向边。反过来,把任意一族边不交路径沿从 到 的方向定向,就得到一个同样值的可行流。最大流最小割定理即证明了等式。
证明
(内部顶点形式的证明)
记 ,并使用有向的拆点网络。保持 不拆。把其余每个顶点 替换为 ,二者之间由一条容量为一的有向弧相连。对每条无向边,添加两个方向的对应弧,即从一个端点的输出副本指向另一个端点的输入副本,每条容量为 。对于未拆分的端点,其输入副本与输出副本都表示原来的端点。
整数流可分解为路径,而每次经过内部的原始顶点都必须穿过其容量为一的拆点弧。因此提取出的路线是内部顶点不交的。反过来,这样的一族路径给出一个整数流;当端点不相邻时,每条路线至少使用一个内部顶点,所以其大小至多为 。容量 对每条邻接弧都足够大。
删去全部 条拆点弧会使源点与汇点不连通。在此删除之后取可达集割,得到一个容量至多为 的割。因此,最小割不可能包含容量为 的向外邻接弧。所以它向外的弧只能是拆点弧。设 为这些弧所对应的原始顶点。割的容量是 ,而任何避开 的原始路径都会提升为网络中一条不穿过任何割弧的路径,这是不可能的。因此 是一个内部顶点分隔集。最大整数流提供了同样数量的不交路线,证明完毕。
证明透视
把容量限制与证书提取分开
顶点证明有三个运作部分。第一,每条拆点弧 上的单位容量是唯一强制不交的地方。
第二,关键一步是邻接弧上的容量 。它只在解码最小割时用到:仅由拆点弧已可得到容量至多为 的割,所以任何最小割都承担不起一条邻接弧。最小割的向外弧都是拆点弧,它们确定一个顶点集 ,其大小就是割的容量。
第三,不相邻假设正在此处用到。若 ,删去全部拆点弧后弧 仍然存在,上界 不再可用,每个割都要为这条弧付出容量。整数最大流最小割等式经由两个转换(流到路线、割到分隔集)完成证明。
例题详解
例题 9.2.5
(两条边路线共享一个脆弱顶点)
取路径 与 ,图中恰好只有这八条边。它们没有公共边,所以存在两条边不交路线。与 关联的两条边构成一个边分隔集,由此证明边的最优值为二。然而每条路线都经过 ,所以 是一个内部顶点分隔集。又因为存在路线,所以顶点的最优值恰为一。边的独立性并不蕴含顶点的独立性。
例题 9.2.6
(三个独立的中间选择)
把 中的每一个都与 和 相连,且没有边 。经由三个不同中间顶点的三条路径是内部顶点不交的。删去全部三个中间顶点就能分隔端点,而只删去两个则仍留下一条路线。在拆点网络中,有三条容量为一的内部弧,邻接容量为 。最大流与最小割的值都是三。三条路径共享源点与汇点,这正是定理所允许的。
例题 9.2.7
(路径长度不是选取问题的目标)
取五圈 。它提供了路线 与 ,长度分别为三和二。它们既是内部顶点不交的,也是边不交的。 处的边界有两条边,而删去内部邻点 会使 孤立。因此两个局部分隔集的最优值都是二。一个最大的路径族不必由同样短的路径组成,该定理也不会最小化它们的总长度。
为什么抵消要先于边分解
有向流把有向弧视为相互独立的资源。在无向模型中,沿一个方向走过一条边与沿相反方向走过这条边,使用的仍是同一条底层边。如果在处理这一区别之前就进行分解,就可能得到作为有向弧列表不交、却违反所需无向要求的路径。
抵消在不改变目标的情况下修正了模型。它去掉的是一个由两条弧构成的环流,而不是有用的净运输。一旦只剩下一个正方向,随后的分解只做减法,永远不会产生新的相反方向。因此提取出的路径在原图中仍然边不交。这是一个正确性步骤,而不仅仅是为了让路线显示得更整齐。
内部不交意味着端点可以重复使用
如果对每个顶点(包括源点)都以单位容量拆点,整个答案就会被限制为一。端点被有意地豁免,因为每条所选路线都必须使用它们。同样,内部分隔集排除端点:否则删去源点就会使每个连通的实例变得平凡。
不相邻假设使得最小分隔集的陈述在这一约定下有意义。它还为归约中大容量的选取提供了有限的上界:全体内部顶点合起来是一个有效的分隔集。如果端点之间有直接的边,这个集合就不能分隔它们,证明中关于小割的论证恰好在相应之处失效。
反例模式
相邻的一对端点没有内部顶点分隔集
在顶点为 的三角形中,路径 与 是内部顶点不交的。它们的最大条数是有限的,即二。但是,在唯一的内部顶点集 的任何子集中,都没有能摧毁直接边 的。因此所述的分隔集最小值不存在。修正后的顶点定理假设端点不相邻;边定理则不需要这样的限制。
局部证书与全局边连通度的陈述
如果每一对顶点之间都至少有 条边不交路径,那么删去少于 条边后,每一对顶点仍然连通。每条被删去的边至多破坏某个特定不交族中的一条路线,所以至少有一条路线幸存。反过来,如果删去少于 条边总是使图保持连通,那么每个局部边分隔集的大小都至少为 。于是 Menger 定理对每一对顶点都给出 条边不交路线。
当图至少有两个顶点时,这就给出了有限 -边连通性的精确解释。该陈述针对所有顶点对。单独一对高度连通的顶点并不能证明整个图是高度连通的:另一个顶点可以只通过一座桥接入,而第一对顶点仍然保有许多备选路线。
一个简单的必要局部界是各端点的度。边不交路线需要不同的第一条边,所以它们的数量至多等于任一端点的度。对于不相邻的端点,内部不交路线还需要不同的第一个内部顶点。这些界是快速的阻碍,但它们并不能证明相应的下界;图内部更远处的瓶颈可能更小。
贪心地删除路径可能丢失最优解
找到一条路线并永久删去它的全部内部顶点,并不能自动构造出最大的路径族。在边为 的图中,选取 会删去两个内部顶点,从而不再留下路线。然而 与 构成一个大小为二的族。因此,极大族可以比最大族更小。
残量算法可以修正先前的决定。当不再有残量改进时发现的分隔集是一个数学证书;而在不可逆的贪心删除之后找不到另一条路线则不是。这一区别类似于极大匹配与最大匹配的区别,每当某个选取问题诱使人采用局部选择规则时,它都是一个有用的警示。
常见错误
常见错误
(通行容量太小会隐藏分隔集)
拆点网络中邻接弧的容量必须严格大于已知的分隔集上界,例如 。容量取一时,最小割可能全由通行弧组成而不指出任何顶点,路径 即为一例。
大小相等的路径族与分隔集可以独立于其寻找方式来证明最优性。只展示若干条路线而没有上界,只证明了可行性;只展示一个小分隔集而没有路线,只证明了一个阻碍。
总结
整数流经过相反方向的抵消与路径分解后,成为边不交的路线。拆点用来保证内部不交,而很大的通行容量使最小割可以解码为顶点分隔集。这些假设把真正的连通度等式与端点相邻时的例外情形以及贪心失败区分开来。
练习
快速检查
(取边为 的图。求两种局部不交路径选取的最优值以及相应的分隔集。)
源点的度为二,但通向汇点的最后一条边只有一条。
解答 · 答案
每条 – 路线都使用 ,所以边装入至多为一; 达到一。单独一条边 是最小边分隔集。每条路线也都使用内部顶点 ,所以内部顶点装入与分隔集的大小都是一,由同一条路线与顶点集 证明。仅凭端点的度为二,并不能推出存在两条路线。
快速检查
(证明下面两个条件的全局等价:删去少于 条边的任何操作后图仍然连通;每一对顶点之间都有 条边不交路径。)
假设图是至少有两个顶点的有限图,且 为整数。
解答 · 答案
如果每一对顶点都有 条边不交路线,那么少于 条边的被删集合不可能与任何一对顶点的全部路线都相交,所以剩下的图是连通的。反过来,如果所有这样的删除都保持连通性,那么没有任何一对顶点的边分隔集的大小小于 。因此边定理对每一对顶点给出至少 条不交路线。结论是逐对地同时具备可用性,而不是要求所有顶点对所选取的路径族彼此互不相交。
快速检查
(为什么每条通行弧的容量都取一,可能无法把最小割解码为内部顶点分隔集?请使用路径 。)
有效的流值与正确解释的割是两个独立的要求。
解答 · 答案
在单位通行容量下,对应 的拆点网络有一个源点侧恰为 的割。它穿过指向 的通行弧,容量为一,且是最小割。它不穿过任何内部拆点弧,因此所提出的被提取的顶点集将是空集,而空集并不能分隔原来的路径。把通行容量取得大于已知的内部分隔集上界,就能避免这样的割成为最小割。