图与网络优化及网络分析-经济模型讲义教案

1、图与网络优化十七，十八世纪时，出现了一些有趣的问题，如迷宫问题、博弈问题、回路问题及棋盘上马的行走线路之类的游戏问题，吸引了许多学者。学者们将这些看起来无足轻重的问题抽象为数学问题，从而开辟了图论这门新学科的研究。从以下例子中可以初步领略图论这门学科的起源与发展。例10-1 在18世纪的东欧有个小城哥尼斯堡（今俄罗斯加里宁格勒），在城中有一条河普雷格尔河流贯全城，在河的两岸及河中心的两个小岛之间有7座小桥相通，如图10-1所示。当时哥尼斯堡的居民中热衷于讨论这样一个话题：一个人怎样才能一次走遍七座桥，且每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，没有人能够找到这样的走法，但是又

2、无法说明这种走法不存在。这就是著名的哥尼斯堡七桥问题。图10-1 哥尼斯堡七桥问题示意图1736年欧拉（Euler）发表了图论方面的第一篇论文。欧拉用A、B、C、D表示4个城区，用7条线表示7座桥，将哥尼斯堡七桥问题抽象为一个图论模型，如图10-2所示，从而将哥尼斯堡七桥问题抽象为一个数学问题：能否从某一点出发，经过图中每条边一次且仅一次，并回到出发点，即一笔画问题，也称之为欧拉回路。图10-2 哥尼斯堡七桥问题的图模型欧拉论证了这样的回路是不存在的，并且将问题进行了一般化处理，即对于任意多的城区和任意多的桥，给出了是否存在欧拉回路的判定规则：（1）如果连接奇数桥的顶点多于两个，则不存在欧拉回

3、路；（2）如果只有两个点连接奇数桥，可以从这两个地方之一出发，找到欧拉回路；（3）如果没有一个点连奇数桥，则无论从哪里出发，都能找到欧拉回路。例10-2 （环球旅行问题）1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。如图10-3所示。它与七桥问题不同的是，前者是要在图中找一条经过每边一次且仅一次的路，通称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，通称为哈密尔顿回路。哈密尔顿根

4、据这个问题的特点，给出了一种解法，如图10-4所示。v1图10-4v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v16v17v18v19v20图10-3例10-3 （中国邮路问题）中国邮路问题由我国数学家管梅谷先生在1962年首先提出：一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？图10-5 中国邮路问题的图模型如果将这个问题抽象成图论的语言，就是给定一个各点相互连通的图，如图10-5所示，连通图的每条边的权值为对应的街道的长度（距离），要在图中求一回路，使得回路的总权值（总长度）最小。该问题与哥尼斯堡七桥问

5、题的显著区别是邮递员要完成任务可能必须在某些街道上重复走若干次。图论的第一本专著是匈牙利数学家O.Koing写的“有限图与无限图的理论”发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经历了200年年之久，总的来说这一时期图论的发展是缓慢的。直到20世纪中期，随着计算机的发展与离散数学问题具有越来越重要的地位，使得作为提供离散模型的图论得以迅速发展，成为运筹学的一个重要分支。§10.1 图与网络的基本概念一、无向图设是一个有个顶点的非空集合：；是一个有条无向边的集合：，则称和这两个集合构成了一个无向图，记为无向图。中任一条边若连接顶点和，则记该边为（或），并称与为无向边

6、的两个端点，且边与顶点及相关联，顶点和顶点相邻。对于图，有时为说明问题，顶点集和无向边集也可以分别表示为和。一般用和表示图中顶点个数和边的条数。实际上无向图是一个由顶点和无向边构成的一个网络结构。一般我们可以作出其几何图，并直接对几何图进行分析。请看以下几个无向图的几何图。图10-6 简单图 图10-7 完备图 图10-8 带平行边的无向图平行边若无向图的两条不同的边和具有相同的端点，则称和为的平行边。如图10-8中的和为平行边，和也是平行边。简单图若无向图中不存在平行边，则称为简单图。图10-5、图10-6都是简单图。完备图若无向图中的任意两个顶点之间都恰好有一条边相关联，则称为一个完备图。

7、图10-7是一个完备图。子图若两个无向图和满足，则称图是图的子图，记为。显然图10-6是图10-7和图10-8的子图。生成子图若图是图的子图，且满足，则称图是图的生成子图。显然生成子图的顶点不能减少，图10-6也是图10-7和图10-8的生成子图。导出子图设无向图，对于非空边集，将图中所有与中的边相关联顶点的全体记为，则称子图为图的导出子图。如在图10-8中取，相应的，从而得到导出子图，见图10-9。 图10-9 生成子图 图10-10 链、开链、初等链示意图 图10-11 闭链、回路示意图链无向图中的一个由顶点和边交错组成的非空有限序列。如其中要求，则称为中的一条连接顶点与的一条链。如在图1

8、0-8中，即为一条链，见图10-10。如果无向图是一个简单图，链可以用它的顶点序列简化表示，并且将所有属于链的所有边的全体记为。如果一条链的起始顶点和最后顶点相同，即，则称为一条闭链，否则称为开链。图10-8中的链为一条开链（见图10-10），链为一条闭链（见图10-11）。初等链如果开链中的全部顶点互不相同，则称为一条初等链。图10-10中所示的链即为一条初等链。回路在一个闭链中，除了初始顶点和结束顶点为相同顶点，没有其他相同的两个顶点，则称闭链为一个回路，回路也称为圈。上述闭炼就是一个回路（见图10-11）。连通图在无向图中，若其中任意两个顶点和之间都存在一条链，则称为连通图，称顶点和在内

9、连通。不是连通图，则称为分离图。图10-9所示的图就是一个分离图。割边在一个连通图中，如果存在一条边，将取走后所得的图为一个分离图，则称边为图的割边。在图10-10所示为一个连通图，边就是一个割边。赋权连通图在一个连通图中，对每一条边，指定一个实数，以表示每条边的权重，则称为一个赋权连通图，记为。通常若，也可以记为，或者时，如图10-5所示为一个赋权连通图，赋权连通图也称为网络。赋权连通图是网络规划考虑的一个重要对象。根据实际问题的需要，每条边的权重可以是时间、距离、成本等相应的数值。二、有向图弧在一个网络图中带方向的边称为弧。弧必须有一个起点和一个终点。若弧的起点为、终点为，则记为。弧只能按

10、所示方向行进，用带箭头的线表示，如图10-12所示。 图10-12 弧的表示 图10-13 有向图示意图 图10-14有向图示意图有向图设是一个有个顶点的非空集合：；是一个有条弧的集合：，则称和这两个集合构成了一个有向图，记为有向图。如图10-12，图10-13所示。入度在有向图中，以顶点为终点的弧的数量称为的入度。出度在有向图中，以顶点为起点的弧的数量称为的出度。平行边有向图的不同的弧和的起点和终点对应相同，则称弧和为的平行边。如图10-14中的和就是平行边。孤立点有向图的顶点集中不与弧集中任一条边关联的点称为的孤立点。如图10-14中的顶点就是一个孤立点。简单图如果有向图中没有平行边，则称

11、为简单图。图10-13所示图是一个简单图。完备图如果有向图中任意两个顶点和之间都恰有两条边和与其关联，则称为完备图。基本图如果将有向图中的所有边的方向去除就得到一个相应的无向图，则称为的基本图，称为的定向图。子图若两个有向图和满足，则称为的子图，记为。导出子图有向图,若，,则称有向图为的关于的导出子图。导出生成子图若是有向图的关于的导出子图，则图称为的关于的导出生成子图，记为。同构图若有向图和的顶点集和以及边集和之间在保持关联性质的条件下一一对应，则称和为同构图。图10-15中(a)和(b)就是一对同构图。(a) (b)图10-15 同构图实际上，同构图的实质是两个图可以在不增加顶点和边的前提

12、下互相转化，只要将一个图的顶点进行必要的挪动，就可以转化为另一个图。链若是有向图的基本图，是中的一条链，则也称为的一条链。初等链若是有向图的基本图，是中的一条初等链，则也称为的一条初等链。路是有向图的一条链，且，则称为的顶点到的一条单向路，简称路。路径若有向图的路中的每个顶点都不相同，则称为一条单向路径，简称路径，同时称顶点可达顶点。回路若有向图的路中的第一个顶点和最后一个顶点相同，则称为一个单向回路，简称回路。赋权有向图和赋权连通图一样，在一个有向图中，对每一有向条边，指定一个实数，以表示每条边的权重，则称为一个赋权有向图，记为。通常若，也可以记为，或者时，。赋权有向图也是网络的一种。三、图

13、的矩阵表示在实际问题中，我们遇到的图往往比较庞大。比如一个城市的公交系统，公交站点形成了图的顶点，公交线路形成了图的弧，这样就形成了一个庞大的有向图。用人工去分析这样的一个图中顶点之间、顶点与边之间的关联关系是不现实的，必须借助计算机等工具进行处理。那么如何将图的有关信息输入到计算机中？一种简单的办法就是构造关联矩阵和邻接矩阵。1、无向图的关联矩阵和邻接矩阵设为一个无向图，其中，构造一个矩阵，其中称矩阵为无向图的关联矩阵，也记为。关联矩阵描述无向图顶点与边的关联状态。 如果构造矩阵，其中为连接顶点和的边的数量，则称为无向图的邻接矩阵，也记为。邻接矩阵描述的是无向图顶点间的邻接状态。例10-4

14、写出图10-7所示无向图的关联矩阵和邻接矩阵。解：设图10-7所示无向图为，和关系见表10-1。 表10-1一般，我们在关联矩阵的左边标出图的各顶点，在矩阵上方标出图的各边，得图的关联矩阵同样，在邻接矩阵的左边和上面标出图的各顶点，可以得到图邻接矩阵从例10-4中，可以总结出无向图的关联矩阵的几个特点：（1）无向图的关联矩阵的第行各元素之和为与顶点关联的边的数量，而的任何一列元素之和总是2；（2）无向图的邻接矩阵为一个对称矩阵。2、有向图的关联矩阵和邻接矩阵对于有向图，其中，同样可以构造一个关联矩阵和邻接矩阵，其中，,我们知道，无向图的邻接矩阵是对称矩阵，那么有向图的邻接矩阵是否为对称矩阵呢？

15、例10-5 计算图10-14所示有向图的关联矩阵和邻接矩阵解：设图10-14所示有向图为，和关系见表10-2。 表10-2图的关联矩阵和邻接矩阵为：同样从例10-5 中，也可以总结出有向图的关联矩阵的几个特点：（1）有向图的关联矩阵的第行非零元素的个数为与顶点关联的边的数量，而的任何一列元素之和总是0；（2）有向图的邻接矩阵不一定对称；（3）有向图的邻接矩阵的第行各元素之和为以顶点为起点的弧的数量，第列各元素之和为以顶点为终点的弧的数量。§10.2 最小支撑树问题树是图论中最简单但却十分重要的图，在自然科学和社会科学中的许多领域有着广泛的应用。一、树树是一种特殊的无向图，也称为无向树

16、，要求图中无回路并且连通，树中的边称为枝。树一般用表示。树的等价定义如果是一棵树，则下列命题等价。（1）连通且无回路；（2）无回路且只有条边，即；（3）连通且只有条边；（4）无回路，但在不相邻的任意两个顶点之间加上一条边，恰好得到一个回路；（5）连通，但去掉的任何一条边，将不再连通；（6）的任意两个顶点之间有且仅有唯一一条初等链。该等价定义请读者自证。有向树在有向图中存在一个顶点，且至的其他顶点都恰有一条路径，则称为有向树，为的树根，简称根。请读者朋友思考，无向树有根吗？二、支撑树支撑树若是无向图的生成子图，并且同时又是树，则称是的支撑树，也称为生成树。图中属于支撑树的边仍称为树枝，不在生成树

17、中的边成为弦。在图10-16中，图为图的支撑树，为根，为支撑树的树枝，其他边为弦。 图10-16 图与支撑树的关系定理10-1 图有支撑树的充分必要条件是为连通图。证明：必要性显然成立；充分性：任取顶点，令集合，此时支撑树的边集合。因为图为连通图，与之间必有边相连，不妨设为其中一边，取重复以上步骤，可得同样可以找到边满足其一端在中，另一端在中，显然不会与中的边构成回路。依此类推，当时，得到，即图中有条边且无回路，因此，即为一棵树，且为图的支撑树。证毕。 该定理的证明属于一种构造性的证明，该方法给出了如何寻求图的支撑树。例10-6 在一个有九个区域的小区安装有限电视网络，小区道路如图10-17(

18、a)所示，有限电视网络线必须沿道路架设，应如何架设？解：根据定理10.1得到图10-17(a)的两棵不同的支撑树，见图10-17(b)、(c)。 (a) (b) (c)图10-17从例10-6中可以看出，支撑树显然不一定是唯一的。三、最小支撑树在例10-6中，如果将小区道路长度作为考虑的因素，则图10-17(a)将成为一个赋权连通图。相应问题转化为一个最小支撑树问题。 赋权图和赋权有向图中的边和弧可以根据实际问题的需要，赋予不同的含义，如时间、距离、成本等。给定一个网络，设是的支撑树，称中所有边的权数之和为树的权，记为，即 由于网络的支撑树不是唯一的，不同的支撑树的权也将不一样，如果的支撑树满

19、足 或则称为的最小支撑树，简称最小树。对于一个连通的网络，如何寻找或构造一个最小支撑树，通常称为最小支撑树问题。 例10-7在例题10-6中的图上添上权，表示小区道路的距离，如图10-18所示，则应如何架设有限电视网络线才能使成本最低？假设架设单位距离电视网络线的费用相同。图10-18解：由于小区的道路长短不一，架设网络线必须考虑成本因素，因此变成了一个构造最小支撑树问题。该问题支撑树有多棵，为构造最小支撑树，结合该例我们介绍两种方法。方法一：Kruskal算法 Kruskal算法的基本思想是先将网络中的边全部去除，然后逐步挑选边构成最小支撑树，要求每次挑选的边是备选边中权最小的，并且确保与已

20、经选好的边不产生回路。Kruskal算法也称为加边算法，见图10-19。 (a) (b)图10-19 该小区有限电视网络线的架设方式见图10-19(b)，总长度为18。方法二：破圈法破圈法和Kruskal算法的方向相反，逐步将网络中权最大的边去除，直至网络形成支撑树。破圈法也称为破回路法，破圈法具体步骤见图10-20。 (a) (b)图10-20 该小区有限电视网络线的架设方式见图10-20(b)，总长度为18。Kruskal算法步骤如下：（1）将图的条边按权的递增顺序排列：（2）令， ，循环变量赋值（3）设，若，转（6），否则令（4）对满足的，令（5）若中的顶点个数，算法终止，否则转（6）（

21、6）若，终止，图为非连通图，无支撑树，否则，令，转（3）。Kruskal算法是一种“避圈”的算法，破圈法的算法步骤请读者自己完成。例10-8 使用Kruskal算法求图10-21所示网络的一棵最小支撑树。图10-21解：根据Kruskal算法，求最小支撑树的过程见图10-22(a)(g)，图10-21(h)就是该问题的最小支撑树。 (a) (b) (c)(d) (e) (f) (g) (h)图10-22§10.3 最短路问题最短路问题是网络优化理论中最基本的问题之一。在生产实践、运输管理和工程建设等很多活动中，如运输线路、生产安排、销售网点布局、管道线网铺设等问题，都与寻找一个图的“

22、最短路径”问题密切相关。一、最短路径对于一个赋权有向图，。若为一条顶点至的有向路径，则称为路径的长度。由于顶点至的有向路径不一定是唯一的，因此一定存在一条有向路径，使得我们称为顶点至的最短路径，为顶点至的最短路径的长度，并记为。一般求有向图中顶点至的最短路径时可以假定是一个完备图，当然这是一个大胆的假定，但这将给我们寻求最短路径提供方便。其实如果中某两个顶点至之间存在平行边，则可以保留其权重最小的边，将其他的平行边去除；同样如果至之间不存在弧，则可假设有一条弧，并且其权重。经过上述的假定，在有向图中，如果，则称至之间不存在最短路径，即至之间不连通，否则至之间最少存在一条最短路径。本节，我们介绍

23、三种获取最短路径的算法。二、Dijkstra算法Dijkstra算法是当前公认的求无负赋权有向图最短路径的最好算法，该算法是Dijkstra于1959年提出，因此而得名。假设顶点至的最短路径为，其长度记为。引理10-1 若为顶点至的最短路径，则其子路径和分别为顶点至和顶点至的最短路径。根据引理10-1，我们可以这样选取中的顶点至其他任意顶点的最短路径：若为顶点至的最短路径，且顶点在上，则上顶点至的子路径即为至的最短路径。Dijkstra算法采用标号的方法，如求顶点至其余顶点的最短路径Dijkstra算法步骤如下：第一步：,取；取，,；第二步：对于，令，取，第三步：若，中至的路径不存在，算法终止

24、，第四步：若，则输出最短路径的长度，算法终止，否则转第二步。上述Dijkstra算法可以给出最短路径长度是否存在及其长度，如果还要给出具体的最短路径，则要将每一步中的记录下来，同时记录其列顶点。在比较简单的赋权有向图的实际计算中，常采用一种表格形式的Dijkstra算法，具体形式见例10-9。例10-9 求图10-23(a)所示的赋权有向图顶点到其余各点的最短路径及其长度。(a) (b)图10-23解：采用Dijkstra算法，步骤如下： ，； ，前列顶点； ，前列顶点； ，前列顶点； ，前列顶点； ，前列顶点； ，前列顶点； ，前列顶点。综合以上过程，得到顶点到其余各点的最短路径及其长度，如

25、图10-23(b)所示。三、逐次逼近算法Dijkstra算法只能给出无负赋权有向图的最短路径，如果网络中出现了负赋权的弧，Dijkstra算法将给出错误的结果。引理10-2 在赋权有向图中，如果到的最短路径总沿着该路径从先到某一点，然后再沿边到达，则到的这条路径也是到的最短路径。令为到的最短路径长度，则为到最短路径长度，且其中为边的长度，当与之间无边时，上述方程可以构造迭代法进行迭代当出现时，迭代终止，并且即是到的最短路径长度。 例10-10 求图10-24(a)所示网络中到各点的最短路径。 (a) (b)图10-24解：初始条件为开始进行迭代，结果见表10-3。表10-30553000000

26、00555555550335000000-3033333333033833000-3036333330366633096633迭代到第7步时，迭代终止，顶点到的最短路径长度在表中的最后一列，见表10-4，其中顶点到的最短路径长度为3。表10-4 上面只给出了最短路径的长度，若需要求出详细的最短路径，可以采取反向追踪法。反向追踪法步骤：1），利用，得出，记录；2），利用，得出，记录；3），利用，得出，记录；4），利用，得出，记录；5），利用，得出，记录；6），利用，得出，记录；7），利用，得出，记录；得到最短路径见图10-24(b)：1）,长度5；2）,长度3；3）,长度3。最短路问题在实际有应

27、用中有着广泛的用途，网络中边的权重不一定就是其长度，根据实际需要，边可以表示实际活动的成本、时间等，因此，最短路径问题也可以用于解决一系列活动的总成本最小或总时间最小等实际问题。例10-11 最小运行费用问题某工厂计划了一笔21000元的资金，用于购买一台设备并用于后续四年的运行，也可以在接下来的三年一次或多次将老设备出售并重新购买新设备，具体数据见表10-5。该工厂应该如何使用该笔资金，使四年内购买设备和运行总费用最少？表10-5购买价格设备使用年限及运行费用设备使用后买出价格新设备1年后2年后3年后使用1年使用2年使用3年使用4年120002000300045006500850065004

28、5003000解：问题的本质是该工厂在第一年购进设备后，什么时间更换设备，使得四年内总费用最省。事实上这类问题可以化为最短路问题，见图10-25，顶点中数字代表相应年份，各方向边的权重为相应决策的购车和运行费用。图10-25 设备采购网络图仍采用逐次逼近法进行迭代，迭代过程见表10-6。 表10-60123400550010500170002500000010550010500170005500550055002055001050010500105001050030550017000160001600040250002100021000迭代3次后终止，最短路长度为21000，采用反向追踪法，最

29、短路为即该工厂于第一年年初购进设备，并于第二年年末将旧设备售出后再购进新的设备，直至用到第四年末，总费用为21000元。四、Floyd算法Dijkstra算法和逐次逼近法可以给出网络从某一起始顶点到其他顶点的最短路，但是某些问题中，要求网络中任意两顶点间的最短路。当然该类问题可以使用上述两种方法通过依次改变起始顶点的方法计算，但是显然计算工作量是相当大的。下面介绍一种不仅能求某一点到其他各点的最短路，还能求各点到某一点的最短路和任意两顶点间的最短路的算法Floyd算法。在Floyd算法中权值正负不限。该方法于1962年提出。1、权矩阵设是一个赋权有向图，其中,为弧的权重，当和间没有边相连时。构

30、造网络的权矩阵，其中如图10-26的网络中，距离矩阵为：v1v2v3v6v5v434253-244133613-1 图10-262、求各点至某点的最短路设要寻求各点至某点的最短路。由于从到的最短路不一定是从直达，也可经过一个、两个，或n-2个中间点才能到达，因此，为便于讨论，我们把从一点直达另一点称为走一步，并且把原地踏步（即从到）也视为走步。这样，我们令走k步到达的最短路,则由于从走k步到达的路都可分为两段:先从走一步到达,其最短距离为,再从走k-1步到达,其最短距离为,因此有 （10-1） 令 则按（10-1）式，列矩阵中的第i个元素是权矩阵W的第i行与列矩阵 的对应元素求和取最小而计算的

31、。记为 这种运算类似于矩阵的乘法运算，称为矩阵的摹乘运算。当所有时,到的最短路必不含圈,即途中经过的点不会重复。由于网络中总共有n个结点，所以从到的最短路最多只需走n-1步,而走n步的最短路必然要在某点原地踏一步,实际上与走n-1步的最短路一致,故有 这意味着最多只需经过n-1次矩阵摹乘运算就能求各点到的最短路。实际计算中,只要出现，说明走k步和走k-1步的最短距离是一致，就可结束运算。而列矩阵中的元素就是各点到的最短距离。例10-12 求图10-26所示网络中各点到的最短路。解：权矩阵为从各点最多走一步到的最短距离为从各点最多走二步到的最短距离为：从各点最多走三步到的最短距离为：从各点最多走

32、四步到的最短距离为：从各点最多走五步到的最短距离为：由于，运算结束。从而求得各点到的最短距离如列矩阵所示。3、求某点至各点的最短路设要寻求某点至各点的最短路。令走k步到达的最短路,则可以把从走k步到达的路都可分为两段:先从走k-1步到达,其最短距离为,再从走一步到达,其最短距离为,因此有 （10-2） 令 矩阵摹乘迭代公式：只要计算中出现就可结束。例10-13 求图10-26所示网络中点到各点的最短路。解：权矩阵为从最多走一步到各点的最短距离为：从最多走两步到各点的最短距离为：从最多走三步到各点的最短距离为：从最多走四步到各点的最短距离为：从最多走五步到各点的最短距离为：由于，计算结束，求得最

33、到各点的最短距离如行矩阵所示。4、求网络中各点到各点的最短距离设矩阵表示网络中各点经过k步中间点到达各点的最短距离矩阵。则，即一步距离矩阵为权矩阵。且，此处为矩阵摹乘法，其中即网络中各点经过k步中间点到达各点的最短距离可分为两段：先求出各点到各点经过k-1步的最短距离矩阵，然后在k-1步的基础上再走一步求最短距离。例10-14 某地区7个村镇之间的现有交通道路如图10-27所示。弧上的数字为各村镇之间道路的长度。求各村之间的最短距离？14235677342264435127 图10-27解：写出权矩阵由于，结束运算，求得各村之间的最短距离如矩阵所示。例10-15 对于例题10-14中的网络即图

34、10-27，假设现在要在某村建一商店和小学，试问：（1）商店应该建在何处，能使各村都离它较近？（2）已知各村的小学生人数如表10-7所示，则小学应该建在何处，能使各村小学生走的总路程最短？表10-7村镇1234567小学生人数40254530203550解：（1）这是一个求网络的中心问题。网络的中心即是各村到该点的距离都较短。先求出网络中任意两点之间的最短距离，列在下表10-8中。表10-8 vjvi最短距离矩阵123456710345781010230324577343055688452502355(min)57452013768563102871078532010然后，对最短距离矩阵每行求

35、最大值，列在表10-8的最后一列。其含义是若商店设在处，其他各村到商店的最长距离。如第一行的最大值为10，说明若商店设在处，其他各村到商店的最长距离是10。再次，在表10-8的最后一列求最小值，所在行对应的5最小，说明若把商店建在村，则其余各村到商店的最长距离不超过5。所以，商店应该建在村。（2）建小学与建商店不同，它还需要考虑各村的小学生人数，要尽可以使小学生人数最多的村离小学最近。因此，这是一个求网络的重心问题。设各村的小学生人数为权重。同样先求出网络中任意两点之间的最短距离矩阵D，然后用村的小学生人数乘以D阵的第i行，得表10-9。表10-9 vjvi123456710345781023

36、03245734305568452502355745201368563102710785320132592010958708509251215再将表中每列数字相加，得小学建于村时各村小学生走的总路程，最后按最小选取网络的重心。因表10-9中最小，所以小学应该建在村。§10.4 最大流问题 最大流问题在交通运输网络中运输流、供水网络水流、通讯网络中信息流、金融系统中的现金流等问题中有着广泛的应用。一、基本概念若有向图中弧上的数字（权）表示通过该弧的容量，而所要解决的问题是从网络的出发点（源）到网络的终点（汇）通过的最大流，诸如此类问题称为最大流问题。例10-16 某企业为了保证其某地区

37、营销中心的配件供应，要求从其生产的工厂运送尽可能多的配件到营销中心，运输网络如图10-28所示，弧上的数据为流量限制。问应如何安排运输，可获得从到的最大运输能力？图10-28为了更好地介绍最大流问题，我们引入几个概念。容量网络设为一个赋权有向连通图，每条弧的非负权重为该弧的最大流容量。如果中仅有一个入度为0的顶点和一个出度为0的顶点，则称为一个容量网络或运输网络。其中称为源，称为汇，称其余顶点为中间点。容量网络一般记为，其中为弧的最大流容量集合。图10-28所示的即为一个容量网络。由于在一个容量网络中，每条弧都有容量限制，因此在整个网络中的流必须受到一定限制，如果假设表示弧上的流量，则必须受到

38、如下约束：（1）容量限制条件：对中的任意一条弧,；（2）平衡条件：对中的任意一个中间点,要求,即中间点的总流入量和总流出量相等,净流量(流出量与流入量之差)为零；对源和汇,要求,即从源发出的流量必须与汇接受到的流量相等.可行流满足以上两个条件的流量的集合称为一个可行流，记为。显然可行流一定存在。最大流问题就是在一个容量网络中寻找流量最大的可行流。饱和弧如果容量网络中某弧上的流量等于其容量限制，即，则称为的饱和弧。前向弧、后向弧假设为容量网络中从到的链，并且规定和为链的方向，链上与链的方向一致的弧称为前向弧，与链的方向相反的弧称为后向弧。前向弧集合用表示，后向弧集合用表示，如图10-29所示，和

39、为后向弧，其余为前向弧。图10-29可增广链假设是容量网络的一个可行流，如果满足则称为从和的（关于的）可增广链。割集容量网络,和为源和汇，若存在弧集，将网络分为两个子图和，其顶点集合分别为和，和为别属于和，则称弧集为的一个割集。割集容量为容量网络的一割集，称中所有弧的容量之和为的割集容量。最小割集容量网络一般有多个割集，其中割集容量最小的割集称为的最小割集，其割集容量称为的最小割集容量。(a) (b) (c)图10-30例10-16 在图10-30(a)所示的容量网络中，分别就顶点集和求其割集和割集容量。解：（1），参见图10-28(b)所示，割集显然是从到或者是到的必经之路。（2），参见图1

40、0-28(c)所示，割集显然也是从到或者是到的必经之路，将割集从网络中剔除，则网络一定中断。二、最大流最小割集定理在例10-16中我们指出，在容量网络中，割集是由到的必经之路，无论拿掉哪个割集，到都将不再连通，所以，任何一个可行流的流量都不会超过任一割集的容量。因此，容量网络的最大流与最小割集容量满足下面的定理。定理10-2 设为网络的任一可行流，流量为，为分离到的一个割集，则有。从定理10-2不难想象，最大流问题可以转化为寻找一个可行流和一个割集，使得的流量，而实际上是网络中的最小割集，因此我们有下面的最大流最小割定理。定理10-3 （最大流最小割集定理）任意一个容量网络中，从源到汇的最大流

41、的流量等于分离、的最小割集容量。证明：假设是一个最大流，流量为，用下面的方法定义顶点集合：令；若顶点，且，则令；若顶点，且，则令。在这种定义下，一定不属于，否则，若，则得到一条从到的链，规定从到为的方向，如图10-30所示。根据的定义，上的前向弧上必有，而后向弧上必有，为此，我们令且 我们定义： 显然，可以验证也是的可行流，且其流量为 与为最大流相矛盾，因此，不属于。于是，可令,从而。于是得到的一个割集，对于该割集中的任意弧有 同时，的流量满足=所以，最大流的流量等于最小割集容量。证毕。 根据定理10-2和可增广链的定义，不难得到以下推论。推论10-1 可行流是最大流的充要条件是不存在从到关于

42、的可增广链。三、最大流算法计算网络的最大流，虽然可以通过枚举法从最小割集中得到，但是即使求出了最小割集，也不能得到网络中流量的详细分布，因此，枚举法不是一种有效的方法。求最大流的有效算法通常使用标号算法。根据定理10-3和推论10-1，从一个可行流开始，寻找一条从到的可增广链，直到找不到可增广链为止，最后的流量即为最大流。标号算法一般分为两个过程：第一是标号过程，通过标号来寻找可增广链，第二是调整过程，沿可增广链调整流以增加流量。步骤1：标号过程（1）对于源，标号为；（2）选择每个已经标号的顶点，对于的所有未给标号的邻接点，作如下处理：若，且，则令，并且将标号为。表示是的后续点。若，且，则令，

43、并且将标号为。表示是的前列点。（3）重复步骤（2），直到汇被标号不再有顶点可被标号。若被标号，则得到一条可增广链，继续调整过程。若根据（2），不能获得标号，则说明已经是最大流。步骤2：调整过程调整一般反向进行，重新计算各条弧的流量。用表示调整后的弧的流量，令将调整后的流的标号全部去除，并重复步骤1和步骤2的标号和调整过程，对重新进行标号，直到不能再进行标号为止。例10-17 计算如图10-31所示的网络从到的最大流。弧上记号表示为，其中为一个已知的可行流。图10-31解：使用标号法求该网络的最大流。步骤1：标号过程将标号为，；检查的邻接点，满足，令 ，将标号为。检查的邻接点，满足，令 ，将标号

44、为。检查的邻接点，满足，令 ，将标号为。得到可增广链：,。步骤2：调整过程由结果如图10-32(a)所示。 图10-32(a) 第一次迭代标号、调整 图10-32(b) 第二次迭代标号、调整对图10-32(a)继续步骤1和步骤2，得到可增广链，其中。得到第二次迭代标号、调整网络，见图10-32(b)。继续标号过程，发现与和邻接的点已经不满足标号条件，标号过程无法继续，此时即为最大流量，算法结束。例10-18 在例10-16中,该企业应如何安排运输，可获得从到的最大运输能力？ 解：在图10-28中，弧上记号只有最大流容量，没有给出已知的可行流，为了采用标号法计算最大流，将可行流的所有流量计算为0

45、，如图10-33。采取标号法计算最大流。图10-33步骤1：标号过程将标号为，；检查的邻接点，满足，令 ，将标号为。检查的邻接点，满足，令 ，将标号为。检查的邻接点，满足，令 ，将标号为。得到可增广链，。步骤2:调整过程由结果如图10-34(a)所示。 (a)第一次标号、调整() (b)第一次标号、调整() (c)第一次标号、调整() (d)第一次标号、调整()图10-34经过4次标号调整，已经达到最大流容量限制，不再满足标号条件，标号过程无法继续。令，为最小割集，其容量即为网络的最大流量，。因此，该企业只要按照图10-34(d)的方式安排运输，即可获得从到的最大运输能力，最大运输能力为150

46、。§10.5 最小费用最大流问题 在上一节中我们介绍了最大流问题，但是在最大流问题中只考虑了流的大小，没有考虑流的成本。实际上，在许多实际问题中，要求同时考虑流的大小和成本。在例10-16中，某企业为了保证其某地区营销中心的配件供应，要求从其生产的工厂运送尽可能多的配件到营销中心，运输网络如图10-28所示，弧上数据为流量限制，同时给出了每条弧上的单位流量费用，如图10-31所示，该企业应如何安排运输，在获得从到的最大运输能力的前提下运输成本最小？图10-35一、最小费用流问题已知容量网络，每条弧上除了给出最大流容量外，还给出了单位流量的成本，一般将带成本的容量网络成为赋权容量网络，

47、记为。求得一个可行流，使得流量，且总费用达到最小。这一类问题称为最小费用流问题。特别地，当要求为最大流时，此类问题即称为最小费用最大流问题。最小费用流问题一般采用对偶算法求解，在介绍对偶算法之前，先介绍几个有关可增广链的概念。已知是一个赋权容量网络，是上的一个可行流，是从源到收点的一条关于的可增广链。给出以下概念：链的费用称为的费用，记为，其中为的前向弧集合，为的后向弧集合。最小费用可增广链若是从源到汇所有可增广链中费用最小的链，则称为最小费用可增广链。对偶算法基本思路：先寻找一个流量满足的最小费用流，然后寻找从到的可增广链，用最大流方法将调整到，使的流量为，并保证是在流量下的最小费用流，继续

48、以上步骤，直到为止。由于对偶算法中要求是在流量下的最小费用流，为此不加证明给出定理10-4。定理10-4 若是流量为下的最小费用流，是关于的从到的一条最小费用可增广链，则经过调整流量后得到的新可行流一定是流量为下的最小费用流。由于，因此通常在选取初始最小费用流时，取，接下来的问题是如何寻找关于的最小费用可增广链，为此，我们引进长度网络的概念。在赋权容量网络中，对于可行流，保持原网络各顶点，每条弧用两条方向相反的弧代替，各弧的权重按如下规则：1当弧，令，的意义是：这条弧已经饱和，不能再增加流量，否则花费的代价太高，实际无法实现，因此，权的弧可以从网络中去除。2当弧为原网络中弧的反向弧，令，的意义是该弧流量已经减少到0，不能再减少，实际上权为的弧也可以从网络中去除。由以上规则定义的网络称为长度网络，记为，其本质是将费用看成长度。显然在中求关于的最小费用可增广链相当于在长度网络中求从到的最短路，可以利用Dijkstra求解最短路。二、对偶算法基本步骤1、初始可行流取零流，即。2、若有可行流流量满足，构造长度网络。3、用Dijkstra算法求长度网络中从到的最短路。若不存在最短路，则即为最大流，不存在流量为的流，算法停止，否则继续第4步。4、在中与这条最短路相应的可增广链上，作，其中