动机
局部路径定理比较的是一对选定的顶点。全局顶点连通度则问:当少量顶点失效时,整个图是否仍然连通。两种观点相互关联,但局部分离集定理中“端点相邻”的例外情形不能简单忽略:删除内部顶点永远无法去掉连接两个端点本身的那条边。
我们将显式处理这一例外,从而对全局连通图中的每一对顶点都得到互不相交的路径。第二个构造把单个目的地换成一个可能目的地的集合,得到一个扇:其中各条路径只在公共起点相交,且终点是目标集中互不相同的顶点。证明将说明,为什么图的阶数和不同目标的个数都必须写入假设。
下文唯一引用的结果,是上一篇笔记中已证明的、有限图且端点不相邻的顶点版 Menger 定理;我们并不假设任何更强的全对顶点命题。
定义
定义 9.3.1
(全局顶点连通度)
设 为有限简单无向图, 为整数。若 ,且删除任意少于 个顶点后所得的图仍连通,则称 是 -顶点连通的,此处简称 -连通。删除操作指去掉所选顶点及其所有关联边。
路径均指简单路径。若从 到 的一族路径中任意两条仅共享端点,则称它们内部顶点互不相交。这些路径必须互不相同;直接相连的那条边在这样的路径族中至多只能作为一条路径出现。
阶数条件排除了这样的情形:在删除所有有意义的顶点之后,图变为空图或单点图,从而使判断失去意义。按通常约定, 个顶点的完全图的顶点连通度为 。如果只检验不相邻的顶点对,则对完全图什么也说明不了,所以它不能单独取代全局定义。
定义 9.3.2
(到目标集的扇)
对顶点 与目标集 ,从 到 的 -扇是由 条路径组成的族:这些路径都从 出发,终点是 中互不相同的顶点,且除 外两两不相交。我们另外要求每条扇路径的内部顶点都不属于 ;在第一个目标处截断即可保证这一约定。
前面的局部定理指出:对于互不相同且不相邻的两个端点,内部顶点互不相交的路径的最大条数,等于分离这两个端点的、不含端点的顶点集的最小规模。下文应用该结果的所有图都是有限简单图,且满足所需的不相邻条件。
定理/命题
定理 9.3.3
(全局连通性等价于每一对顶点都有不相交的路径)
设 。图 是 -连通的,当且仅当任意两个不同顶点之间都至少有 条内部顶点互不相交的路径。该命题包括相邻的顶点对。因此,-连通图中每个顶点的度至少为 。
引理 9.3.4
(扇引理及其逆判据)
在 -连通图中,对每个顶点 以及每个不含 且 的目标集 ,都存在从 到 的 -扇。
反之,若一个图至少有 个顶点,且对每个顶点 与每个不含 的 元目标集都存在这样的扇,则该图是 -连通的。逆命题用到的是对所有目标集的全称选取,而不只是某个特别有利的目标集。
概念视角结构
局部证书度量全局的删除承诺
连通性对每一个小的失效集作量化。Menger 定理把这一承诺转化为每对顶点之间许多独立的路线。在下面的证明中,加入一个辅助目的地,把目标集转化为单个顶点对的问题,再通过截断恢复原来互不相同的目的地。辅助顶点只是证明的工具,并不是留在原图中的额外资源。
度的结论是必要条件而非充分条件。同样,某一对选定顶点之间有许多不相交的路径,并不能推出全对性质。扇给出的是互不相同的目标终点;若允许所有路径终止于同一个目标,则表达的是另一个弱得多的要求。
证明
证明
(每一对顶点都有不相交路径,包括相邻端点)
先设每一对顶点之间都有 条内部不相交的路径。删除满足 的集合 ,并在 之外任取两个顶点。每个被删除的顶点至多出现在其中一条路径的内部,所以被破坏的路径少于 条,至少有一条幸存。因此其余每一对顶点仍然连通,这就证明了全局删除性质。
再设 是 -连通的。不相邻的两个端点不可能被其他少于 个顶点分离,所以由局部定理立即得到 条路径。相邻的端点则需要额外的论证。当 时,它们之间的边就提供了所需的一条路径。设 , 为一条边,令 ,保留所有顶点。
我们断言:不存在至多含 个其他顶点的集合 在 中分离 与 。假设存在这样的 ,则 连通,而把单条边 加到 上就会连接它的各个连通分支。于是 恰有两个连通分支,各含一个端点。剩下的顶点至少有三个,因为 。因此至少有一个分支在其端点之外还含有别的顶点。
若含 的分支有这样一个额外顶点,则从 中删除 。该额外顶点仍与含 的非空分支分离:两个分支之间唯一的边已经消失。由于 ,这与 -连通矛盾。若含 的分支有额外顶点,则删除 ,同理得到对称的矛盾。所以所设的分离集不存在。
在 中端点 不相邻,于是局部 Menger 定理给出其中至少 条内部不相交的路径。再加上原来的单边路径 ,就得到 中 条互不相同、内部不相交的路径。这就证明了包含相邻情形的全对等价性。
对于度的下界,假设某顶点的邻点少于 个。删除它的所有邻点会使它成为孤立点,而阶数条件保证还剩至少一个其他顶点。于是删除少于 个顶点后图就不连通,矛盾。
证明透视
删去一条边使局部定理得以适用
由路径推出连通性的方向纯属计数:每个被删除的顶点至多位于路径族中一条路径的内部,所以少于 次删除不能破坏全部 条路线。另一方向包含唯一不显然的一步。局部 Menger 定理要求端点不相邻,而任何内部分离集都不能去掉边 ,所以证明先删去 ,并只要求在 中找到 条路线。
假设正是在 中分离集的下界处发挥作用。 的连通性用了两次: 时它使 连通,所以 恰有两个分支; 时它禁止删除 或 。阶数条件 只用了一次,保证 至少剩三个顶点,使某一侧含有端点以外的顶点。若只剩两个端点,删去其中一个只留下单个顶点,得不到矛盾。最后把 恢复为第 条路径;它的内部为空,所以与其余 条路径内部不相交,论证至此完成。
证明
(辅助目标顶点,再加上被迫的内部相遇)
对于扇引理,加入一个新顶点 ,使其恰与 的所有顶点相邻。端点 不相邻。设 是此扩充图中不含 且少于 个顶点的任意集合。因为至少有 个目标,可取 。原图 连通且含 ,所以存在从 到 的路线,再接上新边到达 。因此 不能分离 。
在扩充图中应用局部 Menger 定理,得到 条内部不相交的 到 的路径。去掉它们通向 的最后一条边,并在每条剩余路径第一次进入 时截断。它们的终点互不相同,因为若有共同的目标,该目标就会是原路径的内部交点。截断保证它们的内部不含 中的顶点,且去掉后缀不会产生新的交点。这就是所求的扇。
对于逆命题,设删除某个满足 的 使图不连通。在剩余的一个连通分支中取 ,在另一个分支中取 。选一个包含 且不含 的 元目标集;图的阶数保证有足够多的其他顶点来补足。任何到这个集合的 -扇都必须用到它的全部目标,包括 。但每条从 到 的路径都必须经过 ,而 属于目标集。路径在到达 之前就会在内部遇到某个目标,违反扇的定义。这一矛盾排除了每个大小小于 的分离集,证明图是 -连通的。
顶点失效不同于边失效
删除一个顶点可以同时破坏许多关联边。因此,一个图可能没有任何脆弱的单条边,却有某个顶点,使两个区域之间的所有路线都必须经过它。反过来,度的下界把局部的可用性与全局的韧性作了比较:内部不相交的路线必须从不同的邻点出发,但邻点足够多并不能排除远处的瓶颈。
这些定理在两个方向上都给出了证书。一族路径证明少于该数目的内部顶点删除不能分离其端点。一个小的分离集证明全局连通性失败。扇记录的是到若干个分别指定的目标的更强的路由安排。这些对象应当作为实际的顶点序列来检查,而不是凭图中看起来分开的线条来推断。
例题详解
例题 9.3.5
(完全图达到阶数上限)
在 中,删除少于 个顶点后至少剩下两个顶点以及它们之间的所有边,所以图是 -连通的。对端点 ,取它们的直接边,并对其余 个顶点 各取两边路径 。这恰好是 条内部不相交的路径。每个端点的度为 ,所以不可能有更大的互异路径族。直接边虽然内部顶点集为空,但只计一次。
例题 9.3.6
(圈有两条路线,但没有任意的韧性)
对至少有三个顶点的圈,删除一个顶点后得到一条连通的路径,所以它是 2-连通的。在任意两个端点之间,绕圈的两个方向给出内部不相交的路径。圈的度为二,所以当阶数允许 3-连通图的度条件时,它仍然不满足;三角形也不满足 3-连通所需的阶数。长圈并不会仅因为顶点更多就具有更高的顶点连通度。
例题 9.3.7
(轮图提供三个独立的连接)
取一个至少有三个顶点的轮缘圈,以及一个与每个轮缘顶点都相邻的轮心。若被删除的至多两个顶点不含轮心,则每个幸存的轮缘顶点仍与轮心相连。若轮心被删除,则至多还有一个轮缘顶点被删除,剩下连通的轮缘圈或轮缘路径。因此轮图是 3-连通的。
对于四个顶点的轮缘 与轮心 ,从 到 的 3-扇为:;;以及 。它们的目标终点互不相同,且唯一的公共顶点是 。这是对扇的显式检验,而不只是观察到有三条路径从源点出发。
常见错误
反例模式
最小度为二并不蕴含 2-连通
把两个三角形在一个公共顶点 处连接起来,不再有其他重叠或边。每个顶点的度至少为二,且删除任意一条边后图仍然连通。然而删除 会把一个三角形的另外两个顶点与第二个三角形的另外两个顶点分开。该图连通,但不是 2-顶点连通的。无论选取哪些边,位于两个三角形相对两侧的顶点之间的所有路线都必须经过同一个割点。
常见错误
(把直接边计算不止一次)
内部不相交的路径族是一组互不相同的路径。单边路径 的内部为空,所以它与其他每条路径都不相交,但它仍然只是一条路径:把它列出两次并不会增加条数。在 中条数恰为 :一条直接边加上 条两边路径。
常见错误
(让扇路径共用目标)
到 的 -扇终止于 中 个互不相同的顶点。从 到同一目标 的多条内部不相交路径表达的是顶点对 的局部 Menger 性质,那是另一个命题。在证明中,正是单个辅助顶点 (经最后一条边由 到达)迫使截断后的路径终止于不同的目标。
常见错误
(只用一个目标集检验逆判据)
逆判据要求对每个起点和每个 元目标集都存在扇。在共享 的两个三角形中,中心 到其中一个三角形另外两个顶点有 -扇 与 ,但该图并非 -连通。若起点的目标全是它的邻点,就不能说明远处的瓶颈。
总结
只要通过删去并恢复端点之间的边来处理相邻端点,全局删除定义就等价于每一对顶点之间都有不相交的路径。辅助目标顶点证明了扇引理,而精心选取的目标集证明了它的逆命题。度、顶点韧性与边韧性仍是不同的量,各有不同的证书。
练习
快速检查
(证明:当 时,从 -连通图中删除一个顶点,所得的图是 -连通的。)
检查剩余的阶数,然后对进一步的删除作量化。
解答 · 答案
删除 之后至少还剩 个顶点,满足 -连通对阶数的要求。若 是剩余顶点中少于 个顶点的任意集合,则 。原图的保证使 连通。这恰好就是对 的删除检验。该命题给出的是下界,而不是断言连通度总是恰好减少一。
快速检查
(在约定 个顶点的图的连通度至多为 的前提下,证明具有至少三个轮缘顶点的轮图的顶点连通度恰为 。)
把三角形轮缘与更大的轮缘分开讨论。
解答 · 答案
例题中的证明对每个允许的轮图都给出了 3-连通性。轮缘为三角形时,轮图就是 ,其阶数把连通度限制为三。轮缘至少有四个顶点时,每个轮缘顶点的度为三。删除它的三个邻点会使它成为孤立点,而且还剩至少一个其他顶点,所以连通度至多为三。结合已经建立的下界,两种情形下连通度都恰为三。
快速检查
(对共享顶点 的两个三角形,求其顶点连通度与边连通度。给出删除证书,并证明所需的下界。)
这里的边连通度指使该连通图不连通所需删除的最少边数。
解答
该图连通且至少有两个顶点,所以它的顶点连通度至少为一。删除 会使图不连通,由此证明该值恰为一。
删除任意一条边至多把一个三角形变为一条路径;这条路径仍通过 与另一个三角形相连,所以图保持连通。因此边连通度至少为二。删除任一非中心顶点关联的两条边会使该顶点孤立,而其他顶点仍然存在,由此得到规模为二的边割。所以边连通度恰为二。这一比较说明,即使没有任何一条边是桥,也存在真正的顶点瓶颈。