算法分析与设计（山东联盟）第十章测试_智慧树知到答案2021年

第十章 网络流算法：介绍最大流最小割、最大流算法、最小费用最大流算法，最大流算法的改进、推广与应用，二分图最大匹配算法、最佳匹配算法与应用。10.1最大流最小割:介绍网络、最大流与最小割，最大流最小割定理和算法。
10.2最大流算法:介绍最大流算法的改进方法，容量缩放和最短路算法。
10.3预流推进算法:介绍最高标号预流推进算法。
10.4最大流推广:介绍最大流算法的推广和应用实例。
10.5最小费用最大流:介绍最小费用最大流算法和应用实例
10.6二分匹配:介绍二分图的性质、二分测试和二分匹配算法
10.7二分匹配应用:介绍二分匹配、独立集、顶点覆盖、路径覆盖的关系、性质与应用实例。
10.8最佳匹配:介绍最佳匹配的概念和算法、最佳匹配算法的转化。

[判断题]网络流满足容量约束，但一般不满足流量守恒约束。
错
对
答案：错
[判断题]设G = 为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。
对
错[判断题]存在割 (A, B) 使流值 v(f) = 割的容量cap(A, B)，则割 (A, B)是最小割。
错
对[判断题]给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。
对
错[判断题]有下界的流通问题不一定有可行流。
对
错[单选题]Dinic算法的时间复杂度为（）
m2logC
mn
m2n
mn2[单选题]如果每条边的最大容量为1，则时间复杂度是O(nm)的网络流算法有
EK算法
FF算法
容量缩放算法
Dinic算法[多选题]改进FF网络流算法，可以通过选择（  ）增广路，降低时间复杂度。
最大容量
最大瓶颈容量
最短路径
边数最少[判断题]带需求的流通必须满足供给和 = 需求和
错
对[判断题]匈牙利算法中起点和终点都是未匹配点的交错路径称为可增广路径，可增广路径有奇数条边。
错
对[判断题]给定二分图G = 中无孤立点，其最大流算法求得最大流f, 则 G的最大匹配数=f.
对
错[判断题]设G = 中无孤立点。W为G的最小边覆盖, 若G中存在相邻边就移去其中一条。设移去的边集为N，则W-N是G的最大匹配。
对
错[判断题]设 f是网络N的任意流，(A, B) 是N的任意 s-t 割，则流值f至多等于割的容量。
错
对