实用文档

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 标号法可以求任意两点之间的最短路。X 6【判断题】

图的最小支撑树一定唯一。 第二十六讲 最大流问题 1

【单选题】

实用文档

下列说法正确的是 A、割集是子图

B、割量等于割集中弧的流量之和 C、 割量大于等于最大流量 D、割量小于等于最大流量 2

【单选题】 下列说法错误的是A A、容量不超过流量 B、流量非负 C、容量非负

D、发点流出的合流等于收点流入的合流 3

【单选题】 求最大流的方法有B

A、 “避圈法”Kruskal 算法 B、Ford-Fulkerson 法 C、Dijkstra 标号法 D、Warshall- Floyd 算法 4

【单选题】

甲乙两城市之间存在一公路网络，为了判断两小时内能否有 9000 辆车从甲城到乙城，应借 助(

实用文档

)。

A、树的生成法 B、求最大流法 C、求最小生成树法 D、求最短路法 5【判断题】

最大流等于最大流量。X 6【判断题】

可行流是最大流的充要条件是不存在发点到收点的增广链。Y 第二十七讲 最小费用最大流问题 1

【单选题】 下列说法正确的是 A、最大流量等于最大割量 B、最大流量等于最小割量 C、任意流量不小于最小割量 D、最大流量不小于任意割量 2

【单选题】

关于最大流量问题，以下叙述( )正确。D A、一个容量网络的最大流是唯一确定的 B、达到最大流的方案是唯一的

C、当用标号法求最大流时，可能得到不同的最大流方案 D、当最大流方案不唯一时，得到的最大流量相同。

实用文档

3【多选题】

关于增广链，以下叙述( )正确。BC A、

增广链是一条从发点到收点的有向链，这条链上各条边的方向必一致。 B、

增广链是一条从发点到收点的有向链，这条链上各条边的方向可不一致。 C、

增广链上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的 边。 D、

增广链上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等 于零的边。 4【判断题】

某个网络最小费用最大流与这个网络的最大流相比较，它们的最大流量值相等，但流量不相 同。Y 5【判断题】

计算最小费用最大流，要同时将最短路问题与最大流问题的算法结合起来。