WORD格式
C、任何不连通图都不是树 D、树是边数最少的图 3
【单选题】
下图中的最小树所有边的权数之和为 ( )。
46.png A、26 B、24 C、23 D、20 4【多选题】
求图的最小支撑树，主要有哪些方法 AB A、“避圈法” Kruskal 算法 B、 “破圈法” (管梅谷算法 ) C、Dijkstra 标号法 D、 Warshall- Floyd 算法 B
5【判断题】
Dijkstra 标号法可以求任意两点之间的最短路。 6【判断题】
图的最小支撑树一定唯一。 第二十六讲 最大流问题
1
【单选题】
专业资料整理X
WORD格式
下列说法正确的是 A、割集是子图
B、割量等于割集中弧的流量之和 C、 割量大于等于最大流量 D、割量小于等于最大流量 2
【单选题】 下列说法错误的是 A
A、容量不超过流量 B、流量非负 C、容量非负
D、发点流出的合流等于收点流入的合流 3
【单选题】 求最大流的方法有
B A、 “避圈法 ” Kruskal算法 B、Ford-Fulkerson 法 C、Dijkstra 标号法 D、Warshall- Floyd 算法 4
【单选题】
甲乙两城市之间存在一公路网络， 为了判断两小时内能否有 9000 辆车从甲城到乙城，应借助 (
专业资料整理
WORD格式
)。
A、树的生成法 B、求最大流法 C、求最小生成树法 D、求最短路法 5【判断题】
最大流等于最大流量。 X 6【判断题】
可行流是最大流的充要条件是不存在发点到收点的增广链。第二十七讲 最小费用最大流问题
1
【单选题】 下列说法正确的是 A、最大流量等于最大割量 B、最大流量等于最小割量 C、任意流量不小于最小割量 D、最大流量不小于任意割量 2
【单选题】
关于最大流量问题，以下叙述
( )正确。 D
A、一个容量网络的最大流是唯一确定的 B、达到最大流的方案是唯一的
C、当用标号法求最大流时，可能得到不同的最大流方案 D、当最大流方案不唯一时，得到的最大流量相同。
专业资料整理
Y
WORD格式
3【多选题】
关于增广链，以下叙述 ( )正确。 BC A、
增广链是一条从发点到收点的有向链，这条链上各条边的方向必一致。 B、
增广链是一条从发点到收点的有向链，这条链上各条边的方向可不一致。 C、
增广链上与发点到收点方向一致的边必须是非饱和边， 方向相反的边必须是流量大于零的 边。 D、
增广链上与发点到收点方向一致的边必须是流量小于容量的边， 方向相反的边必须是流量等 于零的边。 4【判断题】
某个网络最小费用最大流与这个网络的最大流相比较，它们的最大流量值相等，但流量不相 同。 Y 5【判断题】
计算最小费用最大流，要同时将最短路问题与最大流问题的算法结合起来。
专业资料整理
超星尔雅《运筹学》答案
