运筹学学习资料-运筹学习题集-第六章.docx

运筹学学习资料-运筹学习题集-第六章.docx判断正误，如果错误请更正
第六章网络模型
连通图G的部分树是取图G的点和G的所有边组成的树。
Di jkstra算法要求边的长度非负。
Floyd算法要求边的长度非负。
割集中弧的流量之和称为割量。
最小割集等于最大流量。
求最小树可用破圈法。
在最短路问题中，发点到收点的最短路长是唯一的。
在最大流问题中，最大流是唯一的。
最大流问题是找一条从发点到收点的路，使得通过这条路的流量最大。
容量Ci j是弧（i, j）的实际通过量。
可行流是最大流的充要条件是不存在发点到收点的增广链。
任意可行流的流量不超过任意割量。
任意可行流的流量不小于最小割量。
可行流的流量等于每条弧上的流量之和。
Di jkstra算法是求最大流的一种算法。
避圈法（加边法）是：去掉图中所有边，从最短边开始添加，加边的过程中不能形 成圈，直到有n条边（n为图的点数）。
连通图一定有支撑树。
P是一条增广链，则后向弧上满足流量f〉=0。
最大流量等于最大流。
旅行售货员问题是遍历每一条边的问题。
选择题
在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。
第6章 网络模型
P关于可行流f的增广链，则在u上有 A对任意（i,j）eu、，有f*=Cn B 对任意（i,j） c L, fij〈=Cij C 对任意（i,j）eiT,有 f,」〈=C" D 对 任意（i, j） c 有 f“〉0 E 对任意（i, j） c u ,有 f“〉=0
连通图G有n个点，其部分树是T ,则有A T有n点n条边B T的长度等于 G的每条边的长度之和。C T有n个点n-1条边D T有n-1个点n条边
设P是图G到Vs到Vt的最段短路，则有A P的最短路长等于Vs到Vt的最大流 量B P的长度等于G的每条边的长度之和C P的长度等于P的每条边的长度 之和D P有n个点n-1条边
求最短路的计算方法有 A Dijkstra法B Floyd法C加边法D破圈法E Ford-fulkerson 算法
求最大流的方法有A Dijkstra法B Floyd法C加边法D 破圈法E Ford-fulkerson 算法
下列说法正确的是A割集是子图 B割量等于割集中弧的流量之和C割 量大于等于最大流量D割量小于等于最大流量
下列错误的结论是A容量不超过流量B流量非负C容量非负D发点流 出的合流等于流入收点的合流
下列正确的结论是A最大流等于最大流量B可行流是最大流当且仅当存在发 点到收点的增广链C可行流是最大流当且仅当不存在发点到收点的增广链D 调整量等于增广链上点标号的最大值
下列正确的结论是A最大流量等于最大截量B最大流量等于最小截量C任 意流量不小于最小截量D最大流量不小于任意截量
计算题
。
[6] 6
7 2 4
解答： 最小支撑树为，权值为35；
3 4
① »② >@ ④
LIP 11
⑤ ⑥ ⑦ ®
4 6 ] 3