知到答案算法分析与设计（山东联盟）智慧树答案_2022年

第十章

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