算法设计 第6讲（下） 图论II：全源最短路、最大流与二分图匹配 章节练习

第6讲下 图论II全源最短路、最大流与二分图匹配 章节练习一、单项选择题共30题Floyd-Warshall算法第1-8题第1题Floyd-Warshall算法中记号 d_ij^(k) 表示的是A. 从顶点 i 到顶点 j 且最多包含 k 条边的最短路径权重B. 从顶点 i 到顶点 j 且中间顶点仅允许取自集合 {1, 2, …, k} 的最短路径权重C. 从顶点 i 到顶点 j 且恰好经过 k 个中间顶点的最短路径权重D. 从顶点 i 到顶点 j 且路径总长度不超过 k 的最短路径权重第2题Floyd-Warshall算法的递推公式为当 k 0 时 d_ij^(0) w_ij当 k ≥ 1 时 d_ij^(k) min(d_ij^(k-1), d_ik^(k-1) d_kj^(k-1))。其中 d_ik^(k-1) d_kj^(k-1) 所对应的路径含义是A. 从 i 到 j 不经过顶点 k 的最短路径B. 从 i 出发先到 k 再到 j且路径 i→k 和 k→j 的中间顶点均只允许取自 {1, 2, …, k-1} 的最短路径C. 从 i 到 j 经过 k 且只能以 k 为唯一中间顶点的最短路径D. 从 i 到 j 经过所有编号 ≤ k 的顶点的最短路径第3题在 Floyd-Warshall 算法中前驱矩阵 Π 的初始化规则是对于 i ≠ j 且 (i, j) ∈ Eπ_ij^(0) i否则 π_ij^(0) NIL。当算法在第 k 次迭代中发现 d_ij^(k-1) d_ik^(k-1) d_kj^(k-1) 时前驱矩阵 Π^(k) 应如何更新A. π_ij^(k) kB. π_ij^(k) π_kj^(k-1)C. π_ij^(k) π_ik^(k-1)D. π_ij^(k) j第4题Floyd-Warshall 算法运行结束后若距离矩阵 D 中存在某个对角线元素 d_ii 0这意味着A. 图中存在从顶点 i 出发的正权环B. 图中存在从顶点 i 出发的零权环C. 图中存在从顶点 i 出发可达的负权环D. 算法出现数值计算错误第5题Floyd-Warshall 算法能正确处理以下哪种情况A. 图中存在负权边但无负权环B. 图中存在负权环C. 图中存在正权环D. 以上情况都能正确处理第6题设图 G 有 |V| n 个顶点Floyd-Warshall 算法的时间复杂度和空间复杂度分别是A. O(n³) 和 O(n²)B. O(n²) 和 O(n³)C. O(n³) 和 O(n³)D. O(n² log n) 和 O(n²)第7题在 Floyd-Warshall 算法的某次迭代中已知 d_35^(2) 10d_34^(2) 3d_45^(2) 6则 d_35^(3) 的值为A. 9B. 10C. 3D. 6第8题关于 Floyd-Warshall 算法与重复执行 |V| 次 Dijkstra 算法使用二叉堆实现的比较以下说法正确的是A. Floyd-Warshall 时间复杂度恒为 O(V³)Dijkstra 重复执行总时间为 O(V(E V)log V)因此 Floyd-Warshall 在任何情况下都更慢B. Floyd-Warshall 允许负权边且能处理图的负权环检测而 Dijkstra 要求非负权边C. 两种算法都基于动态规划思想D. 两种算法都无法检测负权环Johnson算法第9-15题第9题Johnson 算法解决的核心问题是A. 带负权边的单源最短路径问题B. 带负权边但无负权环的全源最短路径问题C. 带负权边的全源最短路径问题允许负权环存在D. 非负权边的全源最短路径问题第10题Johnson 算法的第一步是引入一个超级源点 s并用零权边连接 s 到所有原图顶点。这一步骤的主要目的是A. 增加图的连通性B. 为后续 Bellman-Ford 算法计算势函数 h(v) 提供统一的源点C. 消除原图中的负权边D. 将图转化为稀疏图第11题Johnson 算法中通过 Bellman-Ford 算法从超级源点 s 计算得到的最短路径距离 δ(s, v) 被用作势函数 h(v)。根据三角不等式对于任意边 (u, v) ∈ E以下哪个不等式成立A. h(v) ≤ h(u) w(u, v)B. h(v) ≥ h(u) w(u, v)C. h(v) h(u) w(u, v)D. h(v) ≤ h(u) – w(u, v)第12题Johnson 算法中边 (u, v) 被重赋权为 ŵ(u, v) w(u, v) h(u) – h(v)。以下关于 ŵ 的性质描述正确的是A. ŵ(u, v) 可能为负但不影响 Dijkstra 算法的正确性B. ŵ(u, v) 一定为非负因为由三角不等式可推出 w(u, v) h(u) – h(v) ≥ 0C. ŵ(u, v) 一定为正数D. ŵ(u, v) 与 h 函数的具体取值无关第13题在 Johnson 算法中对每条边进行重赋权后原图上的最短路径距离 δ(u, v) 与重赋权图上的最短路径距离 δ̂(u, v) 之间的关系是A. δ(u, v) δ̂(u, v)B. δ(u, v) δ̂(u, v) h(u) – h(v)C. δ(u, v) δ̂(u, v) h(v) – h(u)D. δ(u, v) δ̂(u, v) h(u) h(v)第14题Johnson 算法的总体时间复杂度可表示为使用斐波那契堆实现 DijkstraA. O(V³)B. O(VE V² log V)C. O(V²E)D. O(V² E)第15题Johnson 算法中重赋权操作 ŵ(u, v) w(u, v) h(u) – h(v) 不会改变图中负权环的存在性这是因为A. ŵ 和 w 相差一个常数因子B. 对于任意环 C ⟨v₀, v₁, …, v_k⟩v_k v₀有 ŵ© w© h(v₀) – h(v_k) w©环的总权重不变C. 重赋权操作仅改变非负边的权值D. 势函数 h 使得所有边权变为非负从而不可能存在负权环最大流与Edmonds-Karp算法第16-23题第16题一个流网络 G (V, E) 中对于源点 s、汇点 t流 f 是一个满足以下条件的函数A. 对所有 (u, v) ∈ E 有 0 ≤ f(u, v) ≤ c(u, v)对所有 u ∈ V – {s, t} 满足 ∑_{v} f(u, v) ∑_{v} f(v, u)B. 对所有 (u, v) ∈ E 有 0 ≤ f(u, v) ≤ c(u, v)对所有 u ∈ V 满足 ∑_{v} f(u, v) ∑_{v} f(v, u)C. 对所有 (u, v) ∈ E 有 0 ≤ f(u, v) ≤ c(u, v)仅对源点 s 和汇点 t 保持流量守恒D. 对所有 (u, v) ∈ E 有 0 ≤ f(u, v) ≤ c(u, v)对所有 u ∈ V – {s, t} 满足 ∑_{v} f(u, v) 0第17题给定流网络 G (V, E) 和当前流 f残存网络 G_f 的构造规则是A. G_f 仅包含原图中满足 f(u, v) c(u, v) 的边容量为 c(u, v) – f(u, v)B. G_f 包含原图中所有边每条边容量为 c(u, v) – f(u, v)同时为每条原边添加反向边 (v, u)容量为 f(u, v)C. G_f 仅包含原图中 f(u, v) 0 的边容量为 f(u, v)D. G_f 不包含任何反向边仅保留有剩余容量的正向边第18题在 Ford-Fulkerson 方法中增广路径 p 是指残存网络 G_f 中从源点 s 到汇点 t 的一条路径。该路径的瓶颈值bottleneck定义为A. 路径上所有边的正向容量之和B. 路径上所有边的残存容量之和C. 路径上各边残存容量的最小值D. 路径上各边正向容量的最小值第19题Edmonds-Karp 算法与 Ford-Fulkerson 方法的关键区别在于A. Edmonds-Karp 使用广度优先搜索BFS寻找边数最短的增广路径而 Ford-Fulkerson 可以使用任意方式寻找增广路径B. Edmonds-Karp 使用深度优先搜索DFS寻找增广路径C. Edmonds-Karp 不使用残存网络D. Edmonds-Karp 不能处理非整数容量第20题Edmonds-Karp 算法的时间复杂度为A. O(V · E²)B. O(V² · E)C. O(E · |f*|)其中 |f*| 为最大流值D. O(V · E)第21题对于流网络 G (V, E) 的一个割 (S, T)其中 s ∈ S, t ∈ T, S ∪ T V, S ∩ T ∅其容量定义为A. 从 S 到 T 的所有边上的容量之和B. 从 S 到 T 的所有边上的流量之和C. 从 S 到 T 的所有边上的容量之和减去从 T 到 S 的所有边上的容量之和D. 从 S 到 T 的所有边上的容量之和加上从 T 到 S 的所有边上的容量之和第22题最大流-最小割定理Max-Flow Min-Cut Theorem指出A. 最大流的值等于所有割中容量最大的那个割的容量B. 最大流的值等于所有割中容量最小的那个割的容量C. 最大流的值等于源点到汇点的最短路径长度D. 最大流的值等于图中所有边容量之和第23题在 Ford-Fulkerson 算法中每次沿增广路径增广流量后残存网络的变化是A. 增广路径上各边的反向边容量减少正向边容量增加B. 增广路径上各边的正向边残存容量减少可能消失反向边残存容量增加可能出现C. 正向边和反向边的容量同时减少D. 残存网络不发生变化二分图匹配与Hungarian算法第24-30题第24题在二分图 G (L ∪ R, E) 中一个匹配 M 是边集 E 的子集满足A. M 中的任意两条边可以共享同一个顶点B. M 中的任意两条边都不共享同一个顶点C. M 必须包含 L 和 R 中所有顶点的关联边D. M 中边的数量等于 |L| 和 |R| 中的最小值第25题给定二分图 G (L ∪ R, E) 和匹配 M关于交替路径alternating path的定义正确的是A. 路径中的边全部属于匹配 MB. 路径中的边全部不属于匹配 MC. 路径中匹配边和非匹配边交替出现D. 路径中匹配边的数量等于非匹配边的数量第26题对于二分图 G 和匹配 M一条增广路径augmenting path是一条交替路径满足A. 起点和终点都是已匹配顶点B. 起点和终点都是未匹配顶点C. 起点是未匹配顶点终点是已匹配顶点D. 路径上匹配边的数量等于非匹配边的数量加 1第27题Berge 引理Berge’s Lemma指出A. 匹配 M 是最大匹配当且仅当图中不存在关于 M 的增广路径B. 匹配 M 是最大匹配当且仅当图中存在一条交替路径C. 增广路径的长度总是偶数D. 最大匹配一定是完美匹配第28题在 Hungarian 树算法DFS/BFS 实现中当找到一条增广路径后执行边翻转flip操作的结果是A. 移除增广路径上的所有边B. 将增广路径上的匹配边变为非匹配边非匹配边变为匹配边C. 仅将增广路径上的第一条边和最后一条边翻转D. 将增广路径上的所有边从图中删除第29题在二分图匹配中通过一条增广路径执行一次边翻转操作后匹配 M 的大小会A. 增加 1B. 增加 2C. 减少 1D. 保持不变第30题使用 DFS 实现的 Hungarian 算法Kuhn 算法求二分图最大匹配的时间复杂度为A. O(V E)B. O(V · E)C. O(V²)D. O(VE²)二、判断题共20题正确打 ✓错误打 ✗Floyd-Warshall算法第1-5题 Floyd-Warshall 算法允许图中存在负权边只要不存在负权环即可正确运行。 Floyd-Warshall 算法初始化时距离矩阵 D 的对角线元素全部设置为 0。 Floyd-Warshall 算法的前驱矩阵 Π 中对角线元素 π_ii 始终为 NIL。 Floyd-Warshall 算法本质上是一种动态规划算法其递推公式体现了是否经过顶点 k的 0/1 决策思想。 Floyd-Warshall 算法运行结束后如果图中存在从某顶点出发可达的负权环则距离矩阵 D 的对角线上一定存在负数。Johnson算法第6-10题 Johnson 算法引入超级源点后需要先使用 Bellman-Ford 算法计算超级源点到所有顶点的最短距离以此作为势函数 h(v)。 重赋权公式 ŵ(u, v) w(u, v) h(u) – h(v) 使得每条边的权重变为非负这是由三角不等式 h(v) ≤ h(u) w(u, v) 保证的。 Johnson 算法中对原图进行重赋权后最短路径的结构即构成路径的顶点序列可能发生改变。 Johnson 算法适用于稠密图其时间复杂度优于 Floyd-Warshall 算法。 在 Johnson 算法中最后的距离恢复公式为 δ(u, v) δ̂(u, v) h(v) – h(u)其中 δ̂(u, v) 是在重赋权图上运行 Dijkstra 得到的距离。最大流与Edmonds-Karp算法第11-15题 在残存网络 G_f 中如果边 (u, v) 的当前流量 f(u, v) 0则存在一条从 v 到 u 的反向边其容量为 f(u, v)。 Ford-Fulkerson 方法中当容量为整数时每次迭代沿增广路径至少能增加 1 单位的流量因此算法必然终止。 Edmonds-Karp 算法使用 BFS 寻找边数最少的增广路径保证了算法能在多项式时间内结束。 最大流-最小割定理指出最大流的值等于任意一个割 (S, T) 的容量。 在流网络中如果割 (S, T) 是最小割则所有从 S 指向 T 的边都已经饱和流量等于容量且所有从 T 指向 S 的边流量为 0。二分图匹配与Hungarian算法第16-20题 一条增广路径包含的边数为奇数且非匹配边比匹配边多一条。 Berge 引理是设计和分析二分图匹配算法的理论基础它建立了最大匹配与增广路径之间的等价关系。 在 Hungarian 树算法中每次成功增广后匹配的大小增加 1。 完美匹配一定是最大匹配但最大匹配不一定是完美匹配。 在二分图匹配中如果从所有未匹配的左部顶点出发都无法找到增广路径则根据 Berge 引理当前匹配是最大匹配。三、参考答案单项选择题答案题号答案解析1Bd_ij^(k) 允许中间顶点只从 {1, 2, …, k} 中选择。注意中间顶点不包含 i 和 j 本身。当 k 0 时表示不经过任何中间顶点的直接边。2B路径 i → k 的中间顶点来自 {1, …, k-1}路径 k → j 的中间顶点也来自 {1, …, k-1}合起来表示经过顶点 k 且 k 是最大编号中间顶点的路径。3B当选择经过 k 的路径时j 的前驱应与从 k 到 j 的最短路径上 j 的前驱相同即 π_kj^(k-1)。因为新路径中 i 到 k 段不改变 j 的前驱关系。4C对角线元素 d_ii 0 意味着存在一条从 i 出发经过若干顶点再回到 i 的路径总权重为负即存在从 i 可达的负权环。5AFloyd-Warshall 允许负权边存在Bellman-Ford 也允许但不允许负权环此时最短路径无定义可趋于 -∞。正权环不影响最短路径计算因最短路径必为简单路径。6A三重循环k, i, j各从 1 到 n时间复杂度 Θ(n³)距离矩阵和前驱矩阵各需 Θ(n²) 空间。7Ad_35^(3) min(d_35^(2), d_34^(2) d_45^(2)) min(10, 3 6) 9。8BFloyd-Warshall 允许负权边且对角线可检测负环Dijkstra 要求非负权边。在稀疏图上 Johnson 算法Dijkstra 重赋权可能更快稠密图上 Floyd 不一定更慢。Floyd-Warshall 是 DPDijkstra 是贪心。9BJohnson 算法专门处理带负权边但无负权环的全源最短路径问题。通过重赋权将负权边转化为非负权边再调用10B超级源点 s 用零权边连接所有原图顶点后运行 Bellman-Ford 计算从 s 到各顶点的最短距离 δ(s, v)。该距离作为势函数 h(v)用于后续重赋权。11A由三角不等式Lemma 24.10δ(s, v) ≤ δ(s, u) w(u, v)即 h(v) ≤ h(u) w(u, v)。12B由第 11 题的三角不等式移项得w(u, v) h(u) – h(v) ≥ 0。因此 ŵ(u, v) 一定为非负保证了 Dijkstra 算法的适用条件。13C因为 δ̂(u, v) ŵ§ w§ h(u) – h(v) δ(u, v) h(u) – h(v)所以 δ(u, v) δ̂(u, v) – h(u) h(v) δ̂(u, v) h(v) – h(u)。14BBellman-Ford O(VE) 15B对于任意环 C ⟨v₀, v₁, …, v_k⟩v_k v₀ŵ© Σ[w(v_{i-1}, v_i) h(v_{i-1}) – h(v_i)] w© h(v₀) – h(v_k) w©。环权重不变因此负权环的存在性不变。16A流 f 需满足两个条件(1) 容量约束0 ≤ f(u, v) ≤ c(u, v)(2) 流量守恒除源点 s 和汇点 t 外每个顶点的流入等于流出∑ f(u, v) ∑ f(v, u)。17B残存网络包含(1) 正向边若 f(u, v) c(u, v)则边 (u, v) 存在残存容量为 c(u, v) – f(u, v)(2) 反向边若 f(u, v) 0则边 (v, u) 存在容量为 f(u, v)。18C瓶颈值定义为增广路径上各边残存容量的最小值记作 bottleneck§ min{c_f(u, v) : (u, v) ∈ p}。本次可增广的流量即为瓶颈值。19AFord-Fulkerson 是一种方法method框架增广路径的寻找方式不限Edmonds-Karp 是具体实现algorithm固定使用 BFS 寻找边数最少的增广路径。20AEdmonds-Karp 的时间复杂度为 O(V · E²)。证明要点每条边作为瓶颈的次数不超过 O(V) 次每次作为瓶颈后从残存网络中消失最短路径距离严格增加。每次 BFS 耗时 O(E)总时间 O(VE²)。21A割 (S, T) 的容量定义为所有从 S 指向 T 的边上的容量之和c(S, T) Σ_{u ∈ S, v ∈ T} c(u, v)。22B最大流-最小割定理在任意流网络中最大流的值等于最小割的容量即 max23B沿增广路径增广流量后路径上各正向边的残存容量减去瓶颈值可能降为 0各反向边的残存容量加上瓶颈值可能从无到有。24B匹配的定义M ⊆ E 且 M 中任意两条边没有公共顶点即顶点不相交。匹配不要求覆盖所有顶点。25C交替路径是指路径上的边交替属于匹配 M 和属于非匹配 E – M。26B增广路径是交替路径的特殊情况起点和终点都是未匹配顶点。路径上非匹配边数 匹配边数 1。27ABerge 引理M 是最大匹配当且仅当图中不存在关于 M 的增广路径。这是所有增广路径类匹配算法的理论基础。28B边翻转flip将增广路径上的匹配边全部变为非匹配边非匹配边全部变为匹配边。29A增广路径上非匹配边比匹配边多一条翻转后匹配边数量净增 1。30B每次 DFS 增广耗时 O(E)最多进行 O(V) 次增广匹配大小上限为判断题答案题号答案解析1✓Floyd-Warshall 允许负权边存在但不允许负权环此时最短路径可趋于 -∞算法无法给出有限结果。2✓d_ii^(0) 0因为从 i 到自身且不含任何边的路径权重为 0。在迭代过程中对角线可能变为负值检测负环。3✓从 i 到 i 的最短路径没有前驱节点因此 π_ii 在所有迭代中始终保持为 NIL。4✓递推公式 d_ij^(k) min(d_ij^(k-1), d_ik^(k-1) d_kj^(k-1)) 对应于不使用顶点 k和使用顶点 k两种决策是典型的 DP 思路。5✓如果存在从 i 出发可达的负权环则从 i 绕该环回到 i 的路径总权重为负导致 d_ii 0。因此对角线负数可作为负环存在的判据。6✓超级源点 s 与所有原图顶点以零权边相连后Bellman-Ford 从 s 出发计算最短路径距离作为势函数 h(v)。Bellman-Ford 可正确处理负权边。7✓由三角不等式 h(v) ≤ h(u) w(u, v) 移项即得 w(u, v) h(u) – h(v) ≥ 0故 ŵ(u, v) 非负。8✗引理 25.1 严格证明对于任意路径 pŵ§ w§ h(v₀) – h(v_k)。因此 w(p₁) w(p₂) 当且仅当 ŵ(p₁) ŵ(p₂)最短路径的相对顺序和结构不变。9✗Johnson 算法适用于稀疏图E O(V) 时 O(V² log V) 优于 Floyd 的 O(V³)在稠密图E Θ(V²)上 Johnson 为 O(V³ log V)比 Floyd 的 O(V³) 更差。10✓重赋权图上 Dijkstra 得到 δ̂(u, v) δ(u, v) h(u) – h(v)移项即得 δ(u, v) δ̂(u, v) h(v) – h(u)。11✓残存网络 G_f 中对每条流量 f(u, v) 0 的原边 (u, v)添加反向边 (v, u)容量 c_f(v, u) f(u, v)允许算法撤销已分配的流量。12✓当容量为整数时瓶颈值为正整数≥ 1每次增广至少增加 1 单位流量。最大流值为有限整数故算法必然在有限步内终止。13✓BFS 保证每次找边数最少的增广路径。每条边作为瓶颈的次数 ≤ O(V) 次每次作为瓶颈后残存网络中 s→t 最短距离严格增加总迭代次数 O(VE)每次 BFS O(E)总 O(VE²)。14✗最大流等于最小割容量最小的割的容量而非任意割的容量。割 (S, T) 的容量是流值的一个上界只有最小割才与最大流精确相等。15✗当 (S, T) 是最小割时所有从 S 到 T 的边确实饱和f(u, v) c(u, v)。但从 T 到 S 的边流量不一定为 0这些边可以有正向流量从 T 到 S但它们不影响割的容量定义。16✓增广路径上非匹配边比匹配边多一条。设非匹配边 k1 条、匹配边 k 条总边数 2k1 为奇数。17✓Berge 引理将最大匹配的判断转化为增广路径的存在性判断是 Hungarian 算法等增广路径类算法的理论基础。18✓每次成功增广将路径上的匹配边→非匹配边非匹配边→匹配边匹配大小净增 1。19✓完美匹配覆盖所有顶点匹配大小 20✓根据 Berge 引理不存在关于 M 的增广路径等价于 M 是最大匹配。从所有未匹配左部顶点出发搜索增广路径是 Hungarian 算法的标准做法。