从找出割点到理解全图
两个三角形若恰好共用一个顶点,就没有桥,但删除公共顶点会使它们分开。因此桥森林不能描述所有单顶点故障。仅有一张割点清单也不够:它告诉我们哪些顶点脆弱,却没有说明这些顶点把哪些部分连在一起。
这里需要的部分可以重叠。在上述例子中,每个三角形都应保留为一个部分,所以公共割点必须同时属于两者。下面精确定义这些部分,证明它们的连接方式是一片森林,再用森林回答:除了指定的两个端点之外,哪些顶点能在单独删除时将它们分开?
本节 是有限简单无向图,允许不连通图和空图。用 表示连通分支数。删除顶点时也删除其所有关联边。
定义 9.1.1
(割点)
若 ,就称顶点 为图 的割点。
空图有零个分支;单顶点图没有割点。
可以共用顶点的部分
定义 9.1.2
(块)
的一个块是没有割点的连通子图,且在具有这两个性质的子图中按包含关系极大:它不是 中另一个没有割点的连通子图的真子图。
常见错误
(极大不等于最大)
“极大”表示子图无法再扩大而保持两个性质,并不表示它在所有候选中顶点最多。在三角形 加上悬挂边 的图中,单条边 连同两端点是一个块,虽然它的顶点比三角形少:任何真包含它的连通子图都含有 以及 在 中的某个邻点,此时 是割点,把 与该邻点分开。
定义包括两种小情形。一条边连同其两个端点没有割点,因为删除任一端点后仍留下连通的单顶点图。孤立顶点自身也构成一个块。
定义 9.1.3
(2-连通图)
若一个图至少有三个顶点、连通,且删除任一顶点后仍连通,就称它为 2-连通图。
因此,至少有三个顶点的块是2-连通图;小块则需要另外说明约定。
每个块都是其顶点集上的诱导子图。在同一顶点集内补上一条缺失边,不会破坏原来的连通性,也不会破坏删除任一顶点后的连通性。若候选不是诱导子图,就还可以扩大,违反极大性。有限性还保证:任何没有割点的连通子图都可扩充成一个块,只需在还能扩大时继续扩大,过程必定停止。特别地,每条边至少属于一个块。
反例模式
块并不划分顶点集
设两个三角形的边集分别为 和 。并图有割点 ,所以并图不是一个块。两个三角形正是它的块,都包含 。若强行把每个顶点只分配给一个部分,就会抹去其中一个连接关系。相比之下,稍后将证明每条边恰好属于一个块。
在一个割点处分开问题
关键证明使用较小的图,而不预先假定块应如何连接。
定理 9.1.4
(割点把块问题分成较小问题)
设 连通, 是割点。令 为 的各连通分支的顶点集,其中 ,并令
每个 连通,顶点数小于 ,且至少有两个顶点。 的块恰好就是这些 的块,没有重复。
证明
(块在割点处分开的证明)
每个 内都有 的邻点,否则 不连通。因此 连通。各部分只共用 ,不同 之间没有边。
取任意没有割点的连通子图 。若 同时包含不同 中的顶点,其连通性迫使它包含 ;但 在这两个分支中仍有顶点,彼此没有路径。因此 成了 的割点,矛盾。所以 必须包含在某个 中。单顶点子图 虽包含在每一部分内,却在任何一部分中都不极大,因为每个 都有一条与 关联的边。
于是, 的每个块包含在某一部分中,且在该部分内也必须极大。反过来,取 的块 。由于 连通且至少有两个顶点, 必有一条边。若 中有更大的无割点连通子图包含 ,前面的论证说明它仍须包含在某个部分中; 的那条边迫使该部分就是 ,违反 在其中的极大性。不同部分的块也不能相同,因为各块有边,而各部分的边集互不相交。
证明透视
为什么分割后仍能保留极大性?
证明由两步支撑。第一步是分离:与 的两个不同分支都相交的连通子图必须经过 ,而此时 是该子图的割点。这里用到 正是 的连通分支,所以 中没有边连接其中两个。因此 的每个没有割点的连通子图都落在单一部分 内。
第二步是识别。各部分的顶点集在 处重叠,所以顶点无法说明一个块属于哪一部分;但各部分的边集互不相交。由于每个 连通且至少有两个顶点,其每个块都有一条边,这条边把任何可能的扩大固定在同一部分内。于是 中的极大性与 中的极大性在同一个固定部分内比较,两个方向都由此完成。唯一落在每一部分内的子图是单顶点 ;因为 在每个 中都有邻点, 从不极大,所以它不会造成问题。若没有分离这一步, 的块原则上可能经过 延伸到 ,递归描述便说明不了 的块。
构造关联森林
定义 9.1.5
(块关联图)
的块关联图 是一个二部图,节点分为两类: 的每个原顶点各有一个节点,每个块另有一个新节点。当且仅当 时,连接顶点节点 和块节点 。
两类节点始终区分;即使原图恰有一个顶点也名为 ,它也不等于块节点。
定理 9.1.6
(块关联森林)
是森林,其连通分支与 的连通分支一一对应。 的每条边恰好属于一个块;两个不同的块至多共用一个顶点。
证明
(分割再粘合树的证明)
对 的每个非空连通分支分别按顶点数归纳。若它没有割点,整个分支就是唯一的块,关联图是星形树;边的唯一归属及交集结论也成立。单顶点分支包括在内。
否则,在割点 处按上面的方式分割。每个较小的 都满足归纳假设。分割定理说明它们的块正好是 所需的块;不同部分没有公共边,只共用原顶点 。因此这些关联树恰好共用节点 。将若干棵树在同一个节点粘合仍是树:结果连通;一个简单圈不可能离开某棵树后只经由同一公共节点返回而不重复该节点。边的唯一归属在每一部分内部由归纳成立,在不同部分之间由边集不交成立。不同块在同一部分内至多共用一个顶点,在不同部分内也只能共用 。所有结论得证。对于空图,块集和 都为空。
概念视角结构
把块看成边的等价类
若两条边相等或位于同一个圈上,就称它们相关。圈是连通且没有割点的,所以它包含于某一个块中;由边的唯一性,相关的边属于同一个块。反过来,2-连通图中任意两条边都位于同一个圈上,这是一个标准事实,本节不证明。因此这个关系是等价关系,其等价类恰好是含边的块的边集;一条桥自成一类。这种以边为本的描述只遗漏孤立顶点这种块。
定义 9.1.7
(块割森林)
的块割森林是 中由全部块节点以及属于至少两个块的原顶点节点所诱导的子图。
下面将证明后者恰好就是割点。暂时使用完整的关联森林 ,好处是每个可能的路径端点都已经有对应节点。
从唯一路径读出顶点故障
设不同顶点 和另一个顶点 属于 的同一分支。比较删除 后两张图中的连通性。 中的一条路径给出 中的游走:将路径的每条边 替换成 ,其中 是该边唯一所属的块。反过来, 中的路径交替经过顶点节点和块节点。把每段 替换成 内避开 的一条 – 路径。如果 ,使用 的连通性;如果 ,使用 没有割点的性质。两个不同的端点都保留下来,保证 非空。拼接得到 中的游走,再删除重复部分即可得到路径。
定理 9.1.8
(每个分离顶点都有路径证据)
设 在 中连通,且 。删除 分开 ,当且仅当原顶点节点 位于 中唯一的 – 路径上。
证明
(经由路径对应的证明)
若 不在包含 的分支中,删除它不影响两者的连通性,其节点也不在两者的关联树路径上。否则,前面的对应说明, 中有 – 路径当且仅当 中有这样的路径。在树中,删除一个节点会分开另外两个节点,当且仅当它位于两者的唯一路径上。对 中相应的树应用此性质即可。
这里有意排除了删除端点的情况:删掉 后,不再有一对都存活的顶点供我们比较连通性。原来 连通的条件也不可省。
若 不是孤立顶点,则其原关联树中, 的每个分支都含有存活的原顶点。该分支的第一个节点是一个包含 的块;块至少有两个顶点,另一个成员就在该分支内。由同样的路径对应,删除 后,它原来的分支恰好分成 个分支。因此
常见错误
(割点不一定只把分支分成两部分)
删除一个割点可能产生多于两个新部分,上式正好计算其数目:在星图 中,中心属于三个桥块,故 ,删除它后留下三个孤立顶点,分支数增加二。把“割点”理解为“恰好分成两部分”会少算;计算属于四个块的顶点被删除后的分支数时,也会犯同样的错。
所以,顶点是割点当且仅当它属于至少两个块。孤立顶点只属于自己的单顶点块,删除它却有 ,故它不是割点。从 中删除其余原顶点节点,只是逐一删去叶节点。因此紧凑的块割图确实是一片森林,原图每个分支对应一棵树;没有割点的分支对应单个块节点。
对照三个例子
例题 9.1.9
(桥森林看不见公共顶点)
对于三角形 ,完整关联树有路径 ,另有叶节点 。紧凑树是 。因此,除端点 外,只有删除 能分开 。每条边都在某个三角形上,没有桥,故桥森林只有一个节点。两种答案并不矛盾:桥森林描述边故障,块则描述顶点故障。
例题 9.1.10
(三角形、尾巴和孤立顶点)
取三角形 、边 和孤立顶点 。各块的顶点集是 。非平凡的紧凑树为
另有代表 的单独节点 。所以恰有 能分别分开 。删除 后,全图有三个分支:、 和 。由于 属于两个块,,公式给出 。若删除 ,分支数却从二降到一,这正是孤立顶点的例外。
例题 9.1.11
(两个重叠的圈未必是两个块)
取共用边 的三角形 。整个四顶点图没有割点:删除 或 留下三角形;删除 留下路径 ;删除 留下路径 。所以全图只有一个块,而不是两个三角形块。各三角形虽然没有割点,却不极大。真正不同的块不可能共用一条边,甚至不能共用两个顶点。
计数与有限构造
设 、、,块数为 。完整关联森林有 个节点、 个分支及 条边。森林的边数公式给出
第二个等式来自边的唯一归属。上面的带尾巴例子中,第一个和为 ,第二个和为 。这些等式可用于核对候选清单,但数值吻合本身不能证明各部分没有割点或具有极大性。
证明还给出有限构造:逐个处理连通分支;若当前图没有割点,就输出它;否则选一个割点,分成上述诱导部分并递归处理。每个子问题顶点更少,所以递归终止。必须保留原顶点标签,因为割点本来就会出现在几个递归部分中。可用前文的 DFS 判别寻找割点。这里证明了构造正确,却没有证明在重叠部分中反复搜索具有线性时间界;专门的边栈实现需要另外分析。
练习与解答
快速检查
(求路径 的全部块。哪些顶点分开 ?)
检查连续两条边能否同时位于一个没有割点的连通子图中。
解答 · 答案
每条边各是一个块。任何包含连续两条边的连通子图,都以两边的公共顶点为割点,因此不能成为更大的块。紧凑树为 ,所以恰有 分开两端。
快速检查
(至少有两个顶点的连通图中,一个顶点属于四个块。删除它后有多少个分支?若原来另外还有两个连通分支呢?)
使用关联森林的度数公式。
解答 · 答案
关联度数为四,所以它原来的分支分成四部分。不连通情形中,另外两个分支保留,总数为六。两种情形的分支数都增加三。
快速检查
(证明:两顶点块恰好是桥及其端点。)
两个方向都要论证:不是桥的边位于某个圈上;较大块中的桥会产生割点。
解答 · 答案
两顶点块只包含边 。若它不是桥,就有避开该边的 – 路径,连同 组成一个圈。圈没有割点,会扩大候选块,矛盾。反过来,桥属于某个块。至少三个顶点的无割点连通图不可能有桥:删除桥将顶点分为两个非空侧;至少一侧有两个顶点,删除该侧的桥端点后,该侧剩余顶点与另一侧分开。因此包含桥的块只能有桥的两个端点。
快速检查
(连通图有四个块,顶点数分别为 。求全图顶点数。边数也能确定吗?)
使用森林计数 。
解答 · 答案
由公式,,所以 。边数不确定:四顶点块可以是四边形圈,有四条边;也可以是完全图,有六条边。在两种构造中按同样方式接上一个三角形块及两个桥块,各部分仍是块,但总边数相差二。
快速检查
(设 是两个原本连通的不同顶点。它们能否同时属于两个不同块?若删除任意一个其他顶点后它们都仍连通,能否不属于任何公共块?)
观察 中 – 路径的内部节点。
解答 · 答案
第一个答案是否定的,因为不同块至多共用一个顶点。第二问先假设两顶点原来连通。若关联路径内部有原顶点节点,它就是一个分离顶点;若没有,路径只能是 ,所以两顶点属于同一个块。因此所述单顶点稳健性蕴含公共块。相邻端点可能只共用一个桥块:删除其他顶点不会删掉它们之间的边,故这个结论不能推出相邻端点间有两条内部顶点不交的路径。