第7章图与网络分析练习题及答案

第七章 图与网络分析

一、单项选择题

1．关于可行流，以下叙述不正确的是（ ）

A.可行流的流量大于零而小于容量限制条件

B．在网络的任一中间点，可行流满足流人量=流出量

C．各条有向边上的流量均为零的流是一个可行流

D．可行流的流量小于或等于容量限制条件而大于或等于零

2．关于最小树，以下叙述（ ）正确。

A.最小树是一个网络中连通所有点而边数最少的图

B．最小树是一个网络中连通所有的点，而权数最少的图

C．一个网络中的最大权边必不包含在其最小树内

D．一个网络的最小树一般是唯一的。

3．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（ ）

A. 边缘结点 B.未接结点 C.已接结点 D.最重要结点

4.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（ ）

A.连接的总长度最大 B.连接的总长度最小 C.连接的总长度为0 D.计算总长度

5．最小树问题就是在网络图中，找出若干条边，连接（ ）

A.相邻结点 B.头尾结点 C.部分结点 D.所有结点

6．任一树中的边数和它的点数之间的关系是（ ）

A.边数等于点数减1 B.边数等于点数加1 C.点数等于边数减1 D.点数等于边数加1

7．最大流问题中，对于一个可行流，ViVj有向边上的流量fij必须满足的条件之一是（ ）

A.0≤fij≥cij B.0≥fij≤cij C. 0≤fij≤cij D. 0≥fij≥cij

8.一个连通图中的最小树可能不唯一，其权（ ）

A.是唯一确定的 B.可能不唯一 C.可能不存在 D.一定有多个

二、多项选择题

1.关于图论中图的概念，以下叙述正确的的（ ）

A.图中的边可以是有向边，也可以是无向边 B.图中的各条边上可以标注权

C.结点数等于边数的连通图必含圈 D.结点数等于边数的图必连通 E.图中的边只能是有向边

2.关于最短路，以下叙述不正确的有（ ）

A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的

B．从起点出发到终点的最短路是唯一的

C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上

D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上

E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上

3.关于增广链，以下叙述正确的有（ ）

A．增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致

B．增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致

C．增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边

D．增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边

E．增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边

4.在下图中，根据（a） 生成的支撑树有（ ）

三 、应用题

1.下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做?最小的总长度是多少

?

2．对下面的连通图，试求出最小树。

3．用标号法求下图所示的最大流问题，弧上数字为容量和初始可行流量。

4．

5．

参考答案

一、单项选择题

1-5．ABBDD 6-8．ACA

二、多项选择题

1. ABC 2.BCDE 3. BC 4. BCD

三、应用题

2.解：

3．最大流f*=15

4．

5．