内容发布更新时间 : 2024/6/30 18:54:21星期一 下面是文章的全部内容请认真阅读。

第八章 图与网

络分析 一、填空题

1．图的最基本要素是点、点与点之间构成的边 2．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。 3．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。 4．在图论中，图是反映研究对象_之间_特定关系的一种工具。

5．任一树中的边数必定是它的点数减1。 6．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。

7．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。

8．求最短路问题的计算方法是从0≤fij≤cij开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。 二、单选题

1、关于图论中图的概念，以下叙述(B)正确。 A图中的有向边表示研究对象，结点表示衔接关系。 B图中的点表示研究对象，边表示点与点之间的关系。C图中任意两点之间必有边。 D图的边数必定等于点数减1。

2．关于树的概念，以下叙述(B)正确。

A树中的点数等于边数减1 B连通无圈的图必定是树 C含n个点的树是唯一的 D任一树中，去掉一条边仍为树。

3．一个连通图中的最小树(B)，其权(A)。

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

4．关于最大流量问题，以下叙述(D)正确。 A一个容量网络的最大流是唯一确定的B达到最大流的方案是唯一的C当用标号法求最大流时，可能得到不同的最大流方案D当最大流方案不唯一时，得到的最大流量亦可能不相同。

5．图论中的图，以下叙述(C)不正确。

A．图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。B．图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。C．图论中的边表示研究对象，点表示研究对象之间的特定关系。 D．图论中的图，可以改变点与点的相互位置。只要不改变点与点的连接关系。 6．关于最小树，以下叙述(B)正确。

A．最小树是一个网络中连通所有点而边数最少的图增广路上不能有零流边(4)增广路上与发点到收点11枝：树中的边称为枝。

B．最小树是一个网络中连通所有的点，而权数最少的方向一致的有向边不能是饱和边，相反方向的有向12.平行边：具有相同端点的边叫平行边。

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

13根树：若有向图G有根u，且它的基本图是一棵树，D．一个网络的最小树一般是不唯一的。 8．关于树，以下叙述(ABCE)正确。

则称G为以u为根的根树。

7．关于可行流，以下叙述(A)不正确。

A．树是连通、无圈的图B．任一树，添加一条边便 A．可行流的流量大于零而小于容量限制条件B．在含圈C．任一树的边数等于点数减1。D．任一树的点 网络的任一中间点，可行流满足流人量=流出量。C．各数等于边数减1E．任一树，去掉_条边便不连通。 条有向边上的流量均为零的流是一个可行流D．可行流9．关于最短路，以下叙述(ACDE)不正确。

的流量小于容量限制条件而大于或等于零。 A从起点出发到终点的最短路是唯一的。B．从起 三、多选题

点出发到终点的最短路不一定是唯一的，但其最短路 1．关于图论中图的概念，以下叙述(123)正确。 线的长度是确定的。C．从起点出发的有向边中的最小 (1)图中的边可以是有向边，也可以是无向边 (2)权边，一定包含在起点到终点的最短路上D．从起点出 图中的各条边上可以标注权。(3)结点数等于边数的连发的有向边中的最大权边，一定不包含在起点到终点 通图必含圈(4)结点数等于边数的图必连通。 的最短路上。 E．整个网络的最大权边的一定不包含 2．关于树的概念，以下叙述(123)正确。 在从起点到终点的最短路线上。

1)树中的边数等于点数减1(2)树中再添一条边后10．关于增广路，以下叙述(BC )正确。

必含圈。(3)树中删去一条边后必不连通(4)树中两点A．增广路是一条从发点到收点的有向路，这条路 之间的通路可能不唯一。

上各条边的方向必一致。B．增广路是一条从发点到收 3．从连通图中生成树，以下叙述(134)正确。 点的有向路，这条路上各条边的方向可不一致。C．增 (1)任一连通图必有支撑树 (2)任一连通图生成广路上与发点到收点方向一致的边必须是非饱和边， 的支撑树必唯一(3)在支撑树中再增加一条边后必含方向相反的边必须是流量大于零的边。D．增广路上与 圈(4)任一连通图生成的各个支撑树其边数必相同 发点到收点方向一致的边必须是流量小于容量的边， 4．在下图中，(abcd)不是根据(a)生成的支撑树。

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

四、名词解释

1、树 :在图论中，具有连通和不含圈特点的图称为树。

5．从赋权连通图中生成最小树，以下叙述(124)不2．权：在图中，边旁标注的数字称为权。

正确。

3．网络：在图论中，给边或有向边赋了权的图称为网(1)任一连通图生成的各个最小树，其总长度必相 络

等(2)任一连通图生成的各个最小树，其边数必相等。4．最大流问题：最大流问题是指在网络图中，在单位 (3)任一连通图中具有最小权的边必包含在生成的最时间内，从发点到收点的最大流量

小树上。(4)最小树中可能包括连通图中的最大权边。 5．最大流问题中流量：最大流问题中流量是指单位时 6．从起点到终点的最短路线，以下叙述(123)不正 间的发点的流出量或收点的流入量。

确。

6．容量：最大流问题中，每条有向边单位时间的最大 1)从起点出发的最小权有向边必含在最短路线通过能力称为容量

中。 (2)整个图中权最小的有向边必包含在最短路线7．饱合边：容量与流量相等的有向边称为饱合边。 中。(3)整个图中权最大的有向边可能含在最短路线中 8零流边：流量为零的有向边称为零流边

(4)从起点到终点的最短路线是唯一的。

7．关于带收发点的容量网络中从发点到收点的一条增9.生成树：若树T是无向图G的生成树，则称T是G 的生成树。.。

广路，以下叙述( 123)不正确。

(1)增广路上的有向边的方向必须是从发点指向收10根：有向图G中可以到达图中任一顶点的顶点u称 为G的根。

点的(2)增广路上的有向边，必须都是不饱和边 (3)

四、计算题

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

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

3、 第1题中的交通图，求城市A到D沿公路走的最短路的路长及路径。

4．对下面两图，试分别求出从起点到终点的最短路线。

5．分别求出下面两图中从发点到收点的最大流。每条有向边上的数字为该边的容量限制。