学习提示: 本页包含各道练习的完整解答;请先自行尝试,再展开解答。
删除一条连接与删除一个交汇点,是不同的故障。环能够提供绕开某条边的替代路线,但所有路线仍可能经过某个顶点。因此不能直接把桥的判据原封不动地用于寻找割点。
我们不只输出是或否,而是计算删除各顶点后剩下多少连通分量。数量本身揭示证明:某些 DFS 子树独立成块,其余则连接到被删顶点上方的部分。DFS 根上方没有任何部分,所以其公式必须不同。
这里的删除都是从同一原图出发、分别假设的一次删点。我们不是先删除一个顶点、更新图,再删除另一个。方法静态分析所有可能的单顶点故障。
明确删除的对象
设 为顶点 上的有限无向图,允许 、自环和平行边。删除 指移除顶点与全部关联边。 时剩余图有 个顶点;空图有零个连通分量。
定义 10.3.1
(用连通分量数增加定义割点)
令 为原图连通分量数。对每个顶点 ,令 为 的分量数。 是割点,当且仅当
删除孤立顶点使数量减一,所以它不是割点。若原图只有一个顶点,删除后剩零个分量。
只有原本包含 的分量会分裂或消失,其余 个分量不变。我们要确定多少新部分取代这个原分量。
概念视角结构
分隔就是路线必须经过 v
等价地, 是割点,当且仅当存在两个异于 的顶点 ,它们在 中连通,却每条连接两者的路线都经过 。这时 和 落在 的不同分量。分量数 则说明这类顶点对共落在多少块之中。
哪些 DFS 子树可以不经父顶点逃出?
运行 DFS 森林,记录每个顶点的发现时间 与 DFS 父顶点。树子顶点是直接从当前顶点首次发现的顶点,并不包括所有发现时间更大的相邻顶点。
顶点 完成时, 是从 出发,沿零条或多条 DFS 树边向下,再经过至多一条通往祖先的非树边,可到达的最早发现时间;允许完全不移动。初始化为 。已完成子顶点贡献其 low 值,连向已发现端点的非树边贡献该端点的发现时间。已发现的后代具有更晚的发现时间,不会降低一个已经不大于当前顶点自身发现时间的值。
无向图有两个重要结构性质。非树边连接祖先与后代,自环是退化情形。同一顶点的不同 DFS 子树之间也不存在直接连边:先探索的子树若检查到这种边,就会在返回前发现另一端,把它纳入同一子树。
定理 10.3.2
(非根顶点的分离子顶点判定)
设 为非根顶点, 为 的树子顶点。删去 后, 的子树与 上方部分相连,当且仅当 ;它成为独立的分量,当且仅当
只返回 ,在 本身被删除后就没有帮助,所以分离条件是非严格的。
证明透视
每个符合条件的子顶点产生一个独立分量
删除 后, 子树中的 DFS 树边仍使其中所有顶点连通。离开该子树的任何边必须通向 或祖先,因为无关子树之间没有连边。如果 ,便没有这样的边到达 的严格祖先。删除 因而让整个子树与其余部分分开,形成一个分量。
如果 ,子树存在通向严格祖先的逃出边。结合子树内部树路径与这条边,就能不经过 连接到上方部分。
非根 的父侧部分非空,并通过剩余 DFS 树边连通。所有不分离的子树都加入它。每个分离子树额外贡献一个分量,也不能与其他子树合并。因此若 个子顶点满足非严格条件,原分量恰好变成 个分量。
反例模式
等号能够保护边,却不能保护被删端点
取顶点 0、1、2,一条边 与两条平行边 。从 0 开始 DFS,顶点 2 是 1 的子顶点。第二条平行边返回 1,因此 。
两条 都不是桥:删除一条仍有另一条。但是删除顶点 1 会同时移除两条副本及 ,将顶点 0 与 2 分开,所以 1 是割点。使用严格的桥条件 会漏掉它。返回即将被删除的顶点,不是一条能够保留的逃出路线。
根只有子树部分,没有父侧部分
设 DFS 根 有 个树子顶点。删除 后,各子树仍分别连通,但不同子树不能彼此连通。这 个子树覆盖其原分量中除 之外的全部顶点。
证明透视
根公式只计算真正存在的部分
根不存在父侧分量。删除后,原分量恰好成为 个分量。这包括 :根原本是孤立顶点,其分量直接消失。返回根的边也随根一起删除,无法在之后连接子树。
所以根是割点,当且仅当 。只有一个子顶点的根,即使有很多关联边,也不是割点,因为这些边可能全部进入同一 DFS 子树。
把局部分裂与其余不变的 个分量合并,得到完整删点计数:
定理 10.3.3
(删点后的分量数)
对 的每个顶点 ,设 为 的连通分量数,
其中 是 的 DFS 树子顶点数, 是满足 的树子顶点 的个数。
非根判据是 ,根判据是 。两者都从同一个分量数定义推导而来,并不是两条互不相关、只能记忆的例外。
反例模式
非根公式会为根虚构父侧分量
根只有一个树子顶点时,其原分量中只剩一个部分。根的所有子顶点都符合低链接判定,因为同一 DFS 树中不可能有早于根的祖先。直接使用 ,会得到 ,而正确计数为 。
孤立根也一样,错误公式返回 ,正确值则为 。缺少父侧部分正是根的计算不同的原因;改看根的度数,并不能解决这个问题。
常见错误
(忘记不变的分量)
公式 保留其余 个原有分量。对有 个分量的图中的孤立根,若写成 ,就是声称没有分量剩下。正确的值是 ,正如七个顶点的例子:删去顶点 6 后剩下一个分量。
在不连通示例中计算故障
例题 10.3.4
(两个割点与一个孤立点产生不同影响)
取 ,按以下顺序输入边:
前五个顶点组成两个共用顶点 2 的三角形,顶点 5 连在 4 上,6 为孤立顶点。初始 。外层按标签递增考虑根,邻接项保留插入顺序时,第一棵 DFS 树是链 ,6 是另一个根。
| 顶点 | DFS 父顶点 | 发现时间 | Low 值 | 删除后分量数 |
|---|---|---|---|---|
| 0 | 无 | 0 | 0 | 2 |
| 1 | 0 | 1 | 0 | 2 |
| 2 | 1 | 2 | 0 | 3 |
| 3 | 2 | 3 | 2 | 2 |
| 4 | 3 | 4 | 2 | 3 |
| 5 | 4 | 5 | 5 | 2 |
| 6 | 无 | 6 | 6 | 1 |
顶点 2 有分离子顶点 3,因为 。删除后留下 、 与 。顶点 4 有分离子顶点 5;删除后留下 、 与 。这两个顶点就是割点。
根 0 只有一个 DFS 子顶点,所以删除后数量仍为 2。删除孤立根 6 则移除整个分量,使数量降到 1。返回的删点计数数组为 。
在多重图实现中保持低链接含义
每个输入边实例使用独立 ID,并将两次关联项存为同一 ID。探索顶点时,只跳过到父顶点所用的那一条边。另一条平行边仍属于非树边,可以贡献父顶点的发现时间。自环既不影响最小值,也不增加树子顶点数。
复制一条边不会改变删点后的划分,因为没有新增可达顶点对。不过,边的身份对这里所证明的精确 low 值仍有必要,也使表示方式与桥等对边敏感的应用一致。不要从平行边示例误推边的重数本身能够创造新割点。
常见错误
(按顶点而不是按边 ID 跳过父顶点)
若 DFS 跳过所有通向父顶点的边,而不是只跳过到达时所用的那一条,树边的平行副本就会被忽略。在边 加上两条 的例子中,这会令 ,而不是 。这里割点的答案不变,因为两个值都满足 ,但存储的 low 值是错的,以它为基础的桥判定会把 当成桥,尽管仍有平行副本。
显式 DFS 栈记录顶点与下一个邻接下标。发现新顶点时,增加父顶点的树子计数。子栈帧完成时,把其最终 low 值传给父顶点一次,非严格判定则增加父顶点的分离子计数。根也可能累计这个计数,但最终答案改用它的树子计数。
下面函数假设 为整数,每条边是含两个整数端点的配对。它拒绝负 与越界端点,只读边而不修改调用者列表。结果为 (original_count, deletion_counts, articulation_vertices),最后一项的顶点标签按递增顺序排列。
def vertex_deletion_components(n, edges):
if n < 0:
raise ValueError("the vertex count must be nonnegative")
graph = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
if not (0 <= u < n and 0 <= v < n):
raise ValueError("edge endpoint outside the vertex range")
graph[u].append((v, edge_id))
graph[v].append((u, edge_id))
tin = [-1] * n
low = [0] * n
parent = [-1] * n
parent_edge = [-1] * n
children = [0] * n
separating = [0] * n
timer = 0
original_count = 0
for root in range(n):
if tin[root] != -1:
continue
original_count += 1
tin[root] = low[root] = timer
timer += 1
stack = [(root, 0)]
while stack:
vertex, index = stack[-1]
if index < len(graph[vertex]):
neighbor, edge_id = graph[vertex][index]
stack[-1] = (vertex, index + 1)
if edge_id == parent_edge[vertex]:
continue
if tin[neighbor] == -1:
parent[neighbor] = vertex
parent_edge[neighbor] = edge_id
children[vertex] += 1
tin[neighbor] = low[neighbor] = timer
timer += 1
stack.append((neighbor, 0))
else:
low[vertex] = min(low[vertex], tin[neighbor])
else:
stack.pop()
predecessor = parent[vertex]
if predecessor != -1:
low[predecessor] = min(low[predecessor], low[vertex])
if low[vertex] >= tin[predecessor]:
separating[predecessor] += 1
deletion_counts = [
original_count - 1 + children[v]
if parent[v] == -1 else original_count + separating[v]
for v in range(n)
]
articulation_vertices = [
v for v in range(n) if deletion_counts[v] > original_count
]
return original_count, deletion_counts, articulation_vertices
全局连通分量数只在整个森林探索完毕之后使用。 且无边时,结果为 (0, [], []),没有需要考虑删除的顶点。负端点标签会提前被拒绝,防止 Python 将它解释为从末尾开始的下标。
例题 10.3.5
(根在图中的度数,不决定其 DFS 子顶点数)
星形图有边 、、,根为 0。每个叶子都开始一棵新子树。删除 0 后留下三个分量,因此它是割点。删除任意叶子则剩一个分量。
三角形 若从 0 经过 1 探索,顶点 2 从 1 被发现。根 0 的度数为二,却只有一个树子顶点。删除后仍有边 ,所以只剩一个连通分量。另一个相邻顶点属于后代,而非第二个树子顶点。应计算直接从根发现的次数,而不是所有邻居的数量。
例题 10.3.6
(路径上的自环不改变结果)
取 及边 。自环使顶点 0 多两个边端,两者都检查已被发现的顶点 0,所以 。DFS 树是链 ,。顶点 2 有 ,所以顶点 1 有一个分离子顶点,。顶点 0 是有一个树子顶点的根,所以 。顶点 2 不是根且没有子顶点,所以 。函数返回 (1, [1, 2, 1], [1]):只有顶点 1 是割点,自环不起作用。
复杂度与结论的边界
若输入有 个边实例,邻接表示有 个关联项,自环也存两次。每个顶点发现一次,每个关联项检查一次,每个完成子顶点做常数返回工作。因此构建、遍历和输出共需 时间及 额外存储单元,不依赖递归深度。这是标准图操作界,不是任意大整数标签的位复杂度界。
最终删点计数和割点集合不依赖 DFS 根或边顺序,但发现时间、low 值和父项数组可以改变。它们也不回答同时删除两个顶点的问题。另一个被删顶点可能破坏证明所用的逃出路径,所以不能直接组合单次故障答案。
论证针对无向连通性。有向强连通需要不同分析;这里使用的“不相关 DFS 子树之间没有边”,并不是任意有向 DFS 的性质。应把故障对象、图类型与低链接值含义一同保留在定理中。
练习与完整解答
快速检查
(1. 连通图的非根顶点 v 有三个 DFS 子顶点,low 值为 2、5、7,而 tin[v]=5。删除 v 后有多少分量?v 是否为割点?)
解答 · 1. 等号也对应分离子顶点
Low 值 5、7 的两个子顶点满足条件,所以 ;值为 2 的子树连接到父侧分量。由 ,总数为 。它超过原分量数,因此 是割点。只计算严格不等式,会错误地漏掉只能返回 的子树。
快速检查
(2. 图有 c=4 个分量。DFS 根分别有零、一、三个树子顶点时,D(r) 各是多少?哪些根是割点?)
解答 · 2. 恰好替换一个原分量
使用 ,三个答案分别是 、、。只有三个子顶点的根会增加数量,因此是割点。零子顶点表示孤立根,整个分量消失;一个子顶点则留下一个替代分量。
快速检查
(3. 七顶点示例中,分别列出删除 2 与删除 6 后的分量。为什么这是两个相互独立的假设结果?)
解答 · 3. 保留其余原分量
删除 2 留下 、 和 ,计数为 3。从原图删除 6 则只剩分量 ,计数为 1。第二个答案并非从已经删掉 2 的图开始;每个数组值都指向原图不变时,另一次独立的单顶点删除。
快速检查
(4. 有边 0-1 与两条 1-2 的图中,为什么 1 是割点,而任意一条 1-2 都不是桥?增加重复边是否改变删点计数?)
解答 · 4. 删点同时移除全部平行副本
删除一条 仍有另一条连接这两个端点。删除顶点 1 则移除全部关联边,留下孤立顶点 0、2,分量数由一增为二。更多重复副本不会改变删点前后的可达顶点对,所以不改变这些计数。额外平行边对精确 low 值 的计算仍有作用。
快速检查
(5. 三角形中的 DFS 根有两个邻居,却只有一个树子顶点,两者有何区别?删除根后是什么结果?为什么度数至少二不足以判断根?)
解答 · 5. 后代邻居不是新发现的子顶点
沿根的一条边开始后,第一个子顶点会在根检查另一条边之前先发现第二个邻居。两个邻居都在同一子树。删除根后仍有边连接它们,所以剩一个分量,根不是割点。度数计算相邻边结构,而根定理计算分开的 DFS 子树。
快速检查
(6. 迭代实现为什么要等子栈帧完成才传播 low[child]?把初始发现时间当成最终 low 值会导致什么错误?)
解答 · 6. 后代逃出信息在返回时才完整
新发现的子顶点只知道自身发现时间,后代之后可能找到到达祖先的非树边,降低正确值。只传播初始值,可能错误地声明子树分离。例如三角形 的非树边 2 到 0 会将 降至 0;若用初始 对父顶点 1 作判定,就会错误地将 1 视为割点。显式栈帧的完成事件,保证父顶点最终判定前,全部后代信息已经到达。