管理运筹学习题

减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．对下面两图，试分别求出从起点到终点的最短路线。