算法分析与设计答案2023

第十章测试

1.

网络流满足容量约束，但一般不满足流量守恒约束。

A:对 B:错
答案:B
2.

设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。

A:错 B:对 3.

存在割 (A, B) 使流值 v(f) = 割的容量cap(A, B)，则割 (A, B)是最小割。

A:错 B:对 4.

给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

A:错 B:对 5.

有下界的流通问题不一定有可行流。

A:对 B:错 6.

Dinic算法的时间复杂度为（）

A:mn B:m²n C:m²logC D:mn² 7.

如果每条边的最大容量为1，则时间复杂度是O(nm)的网络流算法有

A:容量缩放算法 B:FF算法 C:Dinic算法 D:EK算法 8.

改进FF网络流算法，可以通过选择（  ）增广路，降低时间复杂度。

A:边数最少 B:最大容量 C:最短路径 D:最大瓶颈容量 9.

带需求的流通必须满足供给和 = 需求和

A:对 B:错 10.

匈牙利算法中起点和终点都是未匹配点的交错路径称为可增广路径，可增广路径有奇数条边。

A:对 B:错 11.

给定二分图G = <V, E>中无孤立点，其最大流算法求得最大流f, 则 G的最大匹配数=f.

A:对 B:错 12.设G = <V, E>中无孤立点。W为G的最小边覆盖, 若G中存在相邻边就移去其中一条。设移去的边集为N，则W-N是G的最大匹配。
A:错 B:对 13.

设 f是网络N的任意流，(A, B) 是N的任意 s-t 割，则流值f至多等于割的容量。

A:对 B:错