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

1、第七章 图与网络分析一、单项选择题1关于可行流，以下叙述不正确的是（ ）A.可行流的流量大于零而小于容量限制条件 B在网络的任一中间点，可行流满足流人量=流出量C各条有向边上的流量均为零的流是一个可行流 D可行流的流量小于或等于容量限制条件而大于或等于零2关于最小树，以下叙述（ ）正确。A.最小树是一个网络中连通所有点而边数最少的图 B最小树是一个网络中连通所有的点，而权数最少的图C一个网络中的最大权边必不包含在其最小树内 D一个网络的最小树一般是唯一的。3最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（ ）A. 边缘结点 B.未接结点 C.已接结点 D.最重要结点4

2、.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（ ）A.连接的总长度最大 B.连接的总长度最小 C.连接的总长度为0 D.计算总长度5最小树问题就是在网络图中，找出若干条边，连接（ ）A.相邻结点 B.头尾结点 C.部分结点 D.所有结点6任一树中的边数和它的点数之间的关系是（ ）A.边数等于点数减1 B.边数等于点数加1 C.点数等于边数减1 D.点数等于边数加17最大流问题中，对于一个可行流，ViVj有向边上的流量fij必须满足的条件之一是（ ）A.0fijcij B.0fijcij C. 0fijcij D. 0fijcij8.一个连通图中的最小树可能不唯一，其权（ ）A.

3、是唯一确定的 B.可能不唯一 C.可能不存在 D.一定有多个二、多项选择题1.关于图论中图的概念，以下叙述正确的的（ ） A.图中的边可以是有向边，也可以是无向边 B.图中的各条边上可以标注权 C.结点数等于边数的连通图必含圈 D.结点数等于边数的图必连通 E.图中的边只能是有向边2.关于最短路，以下叙述不正确的有（ ） A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的B从起点出发到终点的最短路是唯一的C从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上E整个网络的最大权边的一定不包含在从起

4、点到终点的最短路线上3.关于增广链，以下叙述正确的有（ ） A增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致 B增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致 C增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边 D增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边 E增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边4.在下图中，根据（a） 生成的支撑树有（ ） 三 、应用题1.下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做?最小的总长度是多少? 2对下面的连通图，试求出最小树。 3用标号法求下图所示的最大流问题，弧上数字为容量和初始可行流量。45 参考答案一、单项选择题1