第八章 图与网络分析

一、填空题

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．最小树是一个网络中连通所有点而边数最少的图B．最小树是一个网络中连通所有的点，而权数最少的图C．一个网络中的最大权边必不包含在其最小树内D．一个网络的最小树一般是不唯一的。

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

A．可行流的流量大于零而小于容量限制条件B．在网络的任一中间点，可行流满足流人量=流出量。C．各条有向边上的流量均为零的流是一个可行流D．可行流的流量小于容量限制条件而大于或等于零。 三、多选题

1．关于图论中图的概念，以下叙述(123)正确。 (1)图中的边可以是有向边，也可以是无向边 (2)图中的各条边上可以标注权。(3)结点数等于边数的连通图必含圈(4)结点数等于边数的图必连通。 2．关于树的概念，以下叙述(123)正确。

1)树中的边数等于点数减1(2)树中再添一条边后必含圈。(3)树中删去一条边后必不连通(4)树中两点之间的通路可能不唯一。

3．从连通图中生成树，以下叙述(134)正确。

(1)任一连通图必有支撑树 (2)任一连通图生成的支撑树必唯一(3)在支撑树中再增加一条边后必含圈(4)任一连通图生成的各个支撑树其边数必相同 4．在下图中，(abcd)不是根据(a)生成的支撑树。

5．从赋权连通图中生成最小树，以下叙述(124)不正确。

(1)任一连通图生成的各个最小树，其总长度必相等(2)任一连通图生成的各个最小树，其边数必相等。(3)任一连通图中具有最小权的边必包含在生成的最小树上。(4)最小树中可能包括连通图中的最大权边。

6．从起点到终点的最短路线，以下叙述(123)不正确。 1)从起点出发的最小权有向边必含在最短路线中。 (2)整个图中权最小的有向边必包含在最短路线中。(3)整个图中权最大的有向边可能含在最短路线中 (4)从起点到终点的最短路线是唯一的。

7．关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述( 123)不正确。 (1)增广路上的有向边的方向必须是从发点指向收点的(2)增广路上的有向边，必须都是不饱和边 (3)增广路上不能有零流边(4)增广路上与发点到收点方向一致的有向边不能是饱和边，相反方向的有向边不能是零流边 8．关于树，以下叙述(ABCE)正确。

A．树是连通、无圈的图B．任一树，添加一条边便含圈C．任一树的边数等于点数减1。D．任一树的点数等于边数减1E．任一树，去掉_条边便不连通。 9．关于最短路，以下叙述(ACDE)不正确。

A从起点出发到终点的最短路是唯一的。B．从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的。C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上。 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上。 10．关于增广路，以下叙述(BC )正确。

A．增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致。B．增广路是一条从发点到收点的有向路，这条路上各条边的方向可不一致。C．增广路上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。D．增广路上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边。E．增广路上与发点到收点方向一致的边必须是流量为零的边，方向相反的边必须是流量大于零的边。

四、名词解释

1、树:在图论中，具有连通和不含圈特点的图称为树。 2．权：在图中，边旁标注的数字称为权。

3．网络：在图论中，给边或有向边赋了权的图称为网络

4．最大流问题：最大流问题是指在网络图中，在单位时间内，从发点到收点的最大流量 5．最大流问题中流量：最大流问题中流量是指单位时间的发点的流出量或收点的流入量。 6．容量：最大流问题中，每条有向边单位时间的最大通过能力称为容量 7．饱合边：容量与流量相等的有向边称为饱合边。 8零流边：流量为零的有向边称为零流边

9.生成树：若树T是无向图G的生成树，则称T是G 的生成树。.。 10根：有向图G中可以到达图中任一顶点的顶点u称为G的根。 11枝：树中的边称为枝。

12.平行边：具有相同端点的边叫平行边。

13根树：若有向图G有根u，且它的基本图是一棵树，则称G为以u为根的根树。 四、计算题

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

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

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

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

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

6．下面网络中，点①，②是油井，点⑥是原油脱水处理厂，点③、④、⑤是泵站，各管道的每小时最大通过能力(吨／小时)如有向边上的标注。求从油井①、②每小时能输送到脱水处理厂的最大流量。

(提示：虚设一个发点S，令有向边(S，1)，(S，2)的容量为

∞)。

名词 十一章

1、 需求：需求就是库存的输出。

2、 存贮费：一般是指每存贮单位物资单位时间所需花费的费用。 3、 缺货损失费：一般指由于中断供应影响生产造成的损失赔偿费。

4、 订货批量Q：存贮系统根据需求，为补充某种物资的库存而向供货厂商一次订货或采购

的数量。

5、 订货间隔期T：两次订货的时间间隔可订货合同中规定的两次进货之间的时间间隔。 6、 记账间隔期R：指库存记账制度中的间隔记账制所规定的时间。 十二章

1、 预测：是决策的基础，它借助于经济学、概率论与数理统计、现代管理科学、系统论和

计算机科学等所提供的理论及方法，通过适当的模型技术，分析和预测研究对象的发展趋势。 十三章

1、 决策：凡是根据预定目标而采取某种行动方案所作出的选择或决定就称为决策。

2、 单纯选优决策：是指根据已掌握的数据，不需再加工计算，或仅进行方案指标值的简单

计算，通过比较便可以直接选出最优方案的决策方法。

3、 模型选 优决策：是在决策对象的客观状态完全确定的条件下，建立一定的符合实际经

济状况的数学模型，进而通过对模型的求解来选择最优方案的方法。 4、 非确定型决策：是一种在决策分析过程中，对决策方案付诸实施后可能遇到的客观状态，

虽然能够进行估计，但却无法确定每一种客观状态出现的概率的决策。

5、 风险型决策：是一种在分析过程中，对方案付诸实施后可能遇到的客观状态，不仅在决

策分析时能够加以估计，而且对每一种状态出现的概率大小也有所掌握。

6、 决策树：就是对一个决策问题画一张图，用更容易了解的形式来表示有关信息。 十四章

1、 排队论：排队论所讨论的是一个系统对一群体提供某种服务时该群体占用此服务系统时

所呈现的状态。

2、 排队规则：是描述顾客来到服务系统时，服务机构是否充许，顾客是否愿意排队，在排

队等待情形下服务的顺序。

3、 M/G/1排队系统：是单服务台系统，其顾客到达服从参数为λ的泊松分布，服务时间属

一般分布。 随机排队模型：称服务员个数为随机变量的排队系统为随机排队服务系统，相应的模型为随机排队模型。