图与网络模型

1、课 题第五章 图与网络模型 5.1 图与网络的基本知识 5.2 树教学内容1、 图与网络的基本概念，连通图，图的矩阵表示，欧拉图与中国邮路问题；2、 树的基本概念和性质，图的生成树，最小生成树问题，根树及其应用；教学目标1、理解图、顶点的次、子图、网络、连通图、欧拉图、树以及生成树的概念；2、掌握欧拉定理及其推论，并且会利用欧拉定理解决实际问题；3、掌握寻找最优环游的两种方法：“Fleury”算法和“奇偶点图上作业法”；4、掌握寻找最小生成树的两种方法：“Kruskal算法”和“破圈法”；5、会利用给定权构造“Huffman树”；教学重点1、欧拉定理及其推论，并且会利用欧拉定理解决实际问题；2

2、、掌握寻找最优环游的两种方法：“Fleury”算法和“奇偶点图上作业法”；3、掌握寻找最小生成树的两种方法：“Kruskal算法”和“破圈法”；4、会利用给定权构造“Huffman树”；教学难点1、寻找最优环游的两种方法：“Fleury”算法 和“奇偶点图上作业法”；2、寻找最小生成树的两种方法：“Kruskal算法”和“破圈法”；3、会利用给定权构造“Huffman树”；双语教学内容、安排Graph 图 ， connected graph 连通图， sub-graph 子图， tree 树network 网络， Spanning tree 生成树Bipartite 二部图 minimum s

3、panning tree 最小生成树教学手段、措施 以板演为主，以多媒体和课堂讨论为辅作业、后记讨论题：P135: T2、T3、T5教学过程及教学设计备注5.0 图论发展史第一阶段：瑞士数学家欧拉（E. Euler）在1736年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯城堡“七桥难题”，从此开创了图论的历史新纪元；所谓“七桥难题”是指：18世纪的哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块:A、C两个小岛和B、D两块陆地（如图5-1）。为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而

4、久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现，但同时又不能说明这种方法不存在。1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决了问题。欧拉将这个问题归结为如图5-2 所示的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。 图5-1 图5-2 第二阶段：1847年，数学家基尔霍

5、夫（Kirchhoff）运用图论解决了电路理论中的求解联立方程的问题，他引入了“树”的概念，可惜由于他的思想超出了时代的发展而长期未被重视；到1857年，英国数学家凯莱（Cayley）又从化学的角度进一步扩展了“树”的概念，从此图论又有了新的发展。第三阶段：1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。如图5-3所示，要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。哈密尔顿根据这

6、个问题的特点，给出了一种解法如图5-4所示。 第四个阶段：20世纪以后，随着计算机的不断发展，图论也有了突飞猛进的进展，广泛应用于各科领域：如物理、化学、信息论，博弈论，计算机网络，等等；目前图论已经发展成完整的一个数学分支，并且越来越多的数学爱好者倾向于研究图论。5.1 图与网络的基本概念一、 图与网络的基本概念 1、图的相关概念及其分类引例： 在一次聚会中有五位代表其中与，与，与，与， 与是朋友，则我们可以用一个带有五个顶点、五条边的图形来表示这五位代表之间的朋友关系（图5-5）: 定义1、设是一个非空有限集合， 是与不相交的有限集合，一个图是指一个有序二元组，其中称为图的顶点集，称为的边

7、集；，. 如引例中五位代表之间的朋友关系可以用图来表示，其中：，.定义2、两个端点重合的边称为环；两点之间多于一条边的，称为多重边； 不含有环和多重边的图称为简单图。边与顶点的关系有如下几种典型情况：定义3、任意两个顶点之间都有边相连的无向简单图称为完全图，有个顶点的完全图。 定义4、图的点集可以分为两个非空子集即： ，使得中每一条边的两个端点必有一个端点属于，另一个端点属于，则称为二部图（偶图），记作：。2、顶点的次定义5、以点为端点的边数叫做顶点的次（度），记作: 。 例如上述引例图中：。 定理1、任何图中顶点次数的总和等于边数的2倍。 推论1.1、任何图中，次为奇数的顶点必有偶数个。 证

8、明：设必有下式成立: 由于2m为偶数，而 为若干偶数之和也是偶数。所以 也为偶数，即是偶数。 3、子图定义6、图和图，若，则称是的子图，记作：；特别的，当时，称为的生成子图。例1、 如下图中（b）为（a）的子图，（c）为（a）生成子图。 4、网络在实际问题中，往往只用图来描述所研究对象之间的关系还不行，与图联系在一起的，通常还有与点或边有关的某些参数指标，我们称之为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图成为网络。与无向图和有向图相对应，网络又分为无向网络和有向网络；例2、图5-11（a），（b）是常见的网络例子。 二、 连通图定义7、在无向图中，若

9、图中某些点与某些边的交替序列可以排成如下 的形式，且,则称这个点边序列为联接的一条链，链长为；没有重复顶点和边的链称为路；起点和终点重合的路称为回路。对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。例3、 如下图中是一条从到的链； 是一条从到的路； 是一条从到的回路。 三、 图的矩阵表示用矩阵表示图对研究图的性质及应用常常是比较方便的，图的矩阵表示方法有多种，下面介绍两种重要的矩阵：邻接矩阵和边权矩阵；定义8、网络（赋权图），边有权，构造矩阵其中：当时，否则为0 ，则称矩阵为网络的边权矩阵；网络图 中，构造一个矩阵，其中当时，否则为0；称图的邻接矩阵。例4、分别求下列两个网络

10、图的邻接矩阵和边权矩阵： 解：（1）图5-14的边权矩阵为： （2） 图5-15的邻接矩阵为：通过求解可以知道无向图的邻接矩阵和边权矩阵都是对称矩阵。四、中国邮路问题 1、欧拉道路与欧拉回路定义9、连通图中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路；若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路；具有欧拉回路的图称为欧拉图（E图）。在引言中提到哥尼斯堡“七桥问题”就是要在图中寻找一条欧拉回路。定理2、无向连通图是欧拉图，当且仅当中无奇点。推论2.1、无向连通图为欧拉图，当且仅当的边集可划分为若干个初等回路。推论2.2、无向连通图有欧拉道路，当且仅当中恰有两个奇点

11、。 2、中国邮路问题一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？这个问题是我国管梅谷同志在1962年首先提出的。因此国际上统称为中国邮路问题。用图论的语言描述：给定一个连通图，每边有非负权，要求一条回路过每边至少一次，且满足总权最小。 分析：由上述定理知，如果没有奇点，则是一个欧拉图，显然按欧拉回路走就是满足要求的过每边至少一次且总权最小的回路。如果中有奇点，要求连续走过每边至少一次，必然有些边不止一次走过，这相当于在图中对某些边增加一些重复边，使所得到的新图 没有奇点且满足总路程最短。由于总路程的长短取决

12、于所增加的重复边的长度，所以中国邮路问题也可以转为如下问题：在连通图中，求一个边集，把中属于的边均为二重边得到图，使其满足无奇点，且最小。定理3、设为一个连通的赋权图，则使附加边子集的权数为最小的充分必要条件是图中任意边至多重复一次，且中任意回路中重复边的权数之和不大于该回路总权数的一半。所谓中国邮路问题实际上就是从网络图中寻找权最小的欧拉回路即最优环游，对于欧拉图来讲欧拉图中的任意一条回路都是最优环游，下面介绍网络图中寻找最优环游的算法：“Fleury”算法的基本步骤：（1） 任意选取一个顶点，置；（2） 假定已经选出，再在中选取满足与关联，且尽可能不是割边；（3） 当（2）不能执行时，停止

13、；否则让，转（2）。下面通过一个例题来讨论当网络图为非欧拉图的连通图时，寻找最优环游的方法：“奇偶点图上作业法”的基本步骤；例 5、求解图5-16所示网络的中国邮路问题。 第一步：确定初始可行方案。先检查图中是否有奇点，如无奇点则已是欧拉图，找出欧拉回路即可。如有奇点，由前知奇点的个数为偶数，所以可以两两配对，每对顶点间选一条路，使得这条路上均为二重边。图5-16中有四个奇点，将，配对，连接的路有好几条，任取一条，如 ，类似地，对得到图5-17，已是欧拉图。对应这个可行方案，重复边的总长为：.第二步：调整可行方案，是重复边最多为一次。去掉各两条，得到图5-18，重复边总长度下降为：第三步：检查

14、图中每个初等圈是否满足定理条件（2）。如不满足则进行调整，直至满足为止。检查图5-18，发现圈重复边长度总和为14，大于该圈总长度的一半，可以做一次调整，以，得到图5-19，重复边总长度下降为： 再检查图5-19，圈总长度为24，而重复边长为13。以，得到图5-20，重复边总长度下降为15。检查图5-20，条件（1），（2）均满足，得到最优方案。途中任意欧拉回路即为最优邮递路线。 5.2 树一、树的概念和性质例 6、乒乓球单打比赛抽签后，可用图来表示相遇情况，如图5-21。 图5-21 定义10、 连通且不含圈的无向图称为树，树中次为1的点称为树叶，次大于1的点称为支点。定理3、 图，则下列关

15、于树的说法是等价的。（1）T是一个树。 （2）T无圈，且m=n-1。（3）T连通，且m=n-1。 （4）T无圈，但每加一新边即为一一个圈。 （5）T中任意两点，有唯一链相连 （6）T连通，但每舍去一边就不连通。 二、图的生成树定义11、 若图的生成子图是一棵树，则称该树为的生成树；或简称图的树。例 7、如图5-23中（b）为（a）图的生成树，边为树枝，为弦。 定理4、图有生成树的充分必要条件为是连通图。下面给出寻找连通图的生成树的两种算法：“避圈法”与“破圈法”；（1）“避圈法”是指首先将连通图中的所有的顶点都画出来，然后逐个的将图中的边加进去，每加一条边都要保证不含圈，直到加的边数是顶点数减

16、1为止，得到的连通图一定是图的生成树；（2）“破圈法”是指在给定的连通图中，逐个将图中的每一个圈都去掉一条边使其变成路，直到最后只剩下边数是顶点数减1条的连通图即为图的生成树。例 8、一个乡有9个自然村，其间道路如图5-26（a）所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？ 解：本问题用上述“破圈法”，任取一圈从中去掉边，再选圈，去掉边，以同样方法进行，直到无圈。图5-26（b）就是一种方案。三、 最小生成树问题定义12 、连通图每条边上有非负的权。一棵生成树的所有树枝上的权总和，称为这个生成树的权。具有最小的权的生成树被称为最小生成树，简称最小树。下面介绍寻找最小树

17、的两种算法。算法1（Kruskal）算法这个方法类似于生成树的“避圈法”，基本步骤如下：每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。例9、 仍用上节例8，若已知各条道路长度如图5-27（a）所示，各边上的数字表示距离，问如何拉线才能使用线最短？这就是一个最小生成树问题，用Kruskal算法。先将（a）中边按大小顺序由小至大排列：然后按照边的排列顺序，取定由于下一个未选中的最小权边构成圈，所以排除。选。得到（b）就是图G的一颗最小树，它的权是13。算法2“破圈法”基本步骤：（1）从图G中任选一棵树。（2）加上一条弦中立即生成一个圈。去掉此圈中

18、最大权边，得到新树，重复（2）在检查剩余的弦，直到所有的弦都检查完毕为止。例10、仍用例8，先求出图的一棵生成树如图5-28的（a），加弦,去掉最大权边：再加上弦,得圈,去掉最大权边直到全部的弦都已经试过，图5-28（b）即为所求。 四、根树及其应用定义13、若一个有向图在不考虑边的方向时是一棵树，则这个有向图为有向树。定义14、 有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树。根树中入次为0的点称为根；根树中出次为0的点称为叶。由根到某一顶点的道路长度（设每边长度为1），成为顶点的层次。例11、如图5-29所示的树是根树，其中为分枝点，其余各点为叶，顶点的层次为1，顶点的层

19、次为3等等。 定义15、在根树中，若每个顶点的次小于或等于，称这棵树为叉树。若每个顶点的出次恰好等于或零，则称这棵树为完全叉树。当=2时，称为二叉树、完全二叉树。在实际问题中常讨论叶子上的距离（层次）为，这样二叉树T的总权数 满足总权数最小的二叉树成为最优二叉树。霍夫曼（D A Huffman）给出了一个求最优二叉树的算法，所以又称霍夫曼树，算法基本步骤为：（1）将s个叶子节点按权由大排列，不失一般性，设（2）将二个具有最小权的叶子合并成一个分枝点，其权为，将新的分枝点作为一个叶子。令若s=1停止，否则转（1）。例12、最优检索问题。使用计算机进行图书分类。现在五类图书共100万册，其中有A类

20、50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分拣过程，可是总的运算（比较）次数最小？解 构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15，见图5-32（a）所示，按（b）进行分类。总权为：分拣过程是先把A类50万册从总数中捡出来，其次将B类20万册分检出来，然后再将E类15万册分检出来，最后再将D，C分检。例13、 某厂购进一批元件。欲进行检验后按质量分为六等。已知一等品的概率为0.45，二等品的概率为0.25，三等品0.12，四等品0.08，五等品0.05，等外品0.05。假设分等测试一次只能分辩出一种等级，而每次测试的时间皆为t。

21、问如何安排测试过程，使期望的时间达到最短？解：构造一棵具有6个叶子的最优二叉树的总权。经计算得 课 题第五章图与网络模型 5.3 最短路问题 5.4最大流问题教学内容1、 Dijkstra算法，逐次逼近算法，Floyd算法；2、 最大流相关概念，最大流-最小割定理，求最大流的标号算法，最大匹配问题教学目标1、理解最短路和最大流的相关概念；2、掌握求最短路的算法：Dijkstra算法和Floyd算法；3、掌握求最大流的标号算法及其应用； 教学重点1、求最短路的算法：Dijkstra算法和Floyd算法；2、求最大流的标号算法及其应用；教学难点1、求最短路的算法：Dijkstra算法和Floyd算

22、法；2、求最大流的标号算法及其应用；双语教学内容、安排Shortest path problem 最短路问题;maximum flow problem 最大流问题; matching 匹配; 教学手段、措施以板演为主，以多媒体和课堂讨论为辅作业、后记讨论题：P135: T6、T7教学过程及教学设计备注5.3 最短路问题 最短路问题的一般提法如下：设为连通图，图中各边，为图中任意两点，求一条道路，使它是从的所有道路中总的权最小的道路。即： 最小有些最短问题也可以使求网络中某指定点到其余所有结点的最短路问题，通过求网络中任意两点间的最短路来解决。下面我们介绍三种算法，可分别用于求解这几种最短路问题

23、。一、Dijkstra算法 本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求非负权网络最短路问题的最好方法；算法的基本步骤：（1）给。（2）若点为刚得到P标号的点，考虑这样的点属于E，且的T标号进行如下的更改： （3）比较所有具有T标号的点，把最小者改为P标号，即: 当存在两个以上最小者时，可同时改变为P标号。若全部均为P标号则停止。否则用转回（2）。 例1、用Dijkstra算法求图5-34中点的最短路。解： （1）首先给，给其余所有点T标号，（2）由于边属于E，且为T标号，所以修改这两个点的标号： （3）比较所有T标号，最

24、小，所以令。（4）为刚得到P标号的点，考察边端点。 （5）比较所有T标号，最小，所以令。（6）考虑点，有 （7）全部T标号中，（8）考察， （9）全部T标号中，（10）考察， （11）全部T标号中，。（12）考察 （13）全部T标号中，。（14）考察， （15）因只有一个T标号，计算结束。从到的最短路为，路长为。二、主次逼近算法 本算法可用于网络中有带有负权的边时，求某指定点到网络中任意点的最短路。算法的基本思路是基于以下事实：如果的最短路总沿着该路从，然后再沿边到达，则到的这条路必然也是到的最短路；若令表示从到的最短路长，为到的最短路的长，则必有方程： 用迭代方法解这个方程。开始时令 即用的

25、直接距离作初始解，若。从第二步起，是用迭代公式 求，当进行到第t步，若出现 则停止，点到各点的最短路长。例2、求图5-37中点到各点的最短路。 解 初始条件：第一轮迭代： 类似可得： 可以看出最短路长。全部计算过程可用表5-1表示。迭代进行到第六步时，发现则停止。表中最后一列数字分别表示点到各点的最短路长。如果需要知道点到各点的最短路径，可以采取“反向追踪”的办法。如需要求出点的最短路径，已知而在表中寻求满足等式的。再考察，由于。考察考察。由于递推公式中的，实际意义为从点、至多含有k-1个中间点的最短路权，所以在含有n个点的图中，如果不含有总的权和小于零的回路，求从点到任一点的最短路权，用上述

26、算法最多经过n-1次迭代必定收敛。例3、已知某地区的交通网络如图5-39所示，其中点代表居民区，便表示公路，为小区间公路距离，问区中心医院建在哪个小区，可使得距离最远的小区居民就诊时所走的路程最近？解： 这是一个网络选址问题，实际要求图的中心，可以化为一系列求最短路的问题；先求出到其他各点的最短路长，令 表示若医院建在，则离医院最远的小区距离为。再依次计算到其余各点最短路，类似求出中最小者即为所求.三、Floyd算法Floyd算法（1962）可以直接求出网络中任意两点间的最短路。为计算方便，令网络的权矩阵为的距离。其中 算法基本步骤为：（1）输入边权矩阵。（2）计算其中（3）的最短路长。 5.

27、4最大流问题一、最大流有关概念 定义1、设有向图，的每一条边上的非负数称为边的容量，仅有一个入次为0的点成为发点（源），一个出次为0的点称为收点（汇），其余的点为中间点，这样的网络称为容量网络，记作：。对任意中的边有流量，称集合为G的一个流。称满足下列条件的流为可行流：（1）容量限制条件：对G中每条边，有（2）平衡条件：对中间点，有（即中间点的物资的输入量与输出量相等）对收、发点有（即从点发出的物资总量等于点输入量）W为网络流的总流量。可行流总是存在的，例如就是一个流量为0的可行流，一个流，当，则称流对边是饱和的，否则称对不饱和。所谓最大流问题就是在容量网络中，寻找流量最大的可行流。定义2、容

28、量网络，为发、收点，若有边集为E的子集，将G分为两个子图其顶点集合分别记分属，满足：不连通；为的真子集，而仍连通，则称为G的割集，记。二、最大流-最小割 定理定理1、设f为网络G=(V,E,C)的任一可行流，流量为是分离的任一割集，则有。 定理2、（最大流-最小割定理）：任一网络G中，从到的最大流的流量等于分离的最小割的容量。定义3、容量网络，若为网络中从到的一条链，给定向为从到,上的边凡与同向称为前向边，凡与反向称为后向边，其集合分别用和表示，是一个可行流，如果满足则称为从到的（关于f的）可增广链。推论2.1、可行流f是最大流的充要条件是不存在从到的（关于f的）可增广链。三、求最大流的标号算

29、法设已有一个可行流f，标号的方法可分为两步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。1. 标号过程（1） 给发点以标号。（2） 选择一个已标号的顶点，对于的所有未给标号的邻接点按下列规则处理：（a） 若边，且，则令，并给以标号。（b） 若边，且时，则令，并给以标号。（3） 重复（2）直到收点被标号或不再有顶点可标号时为止。 若得到标号，说明存在一条可增广链，转（第2步）调整过程。若未获得标号，标号过程已无法进行时，说明已是最大流。2 调整过程（1）令（2）去掉所有标号，回到第1步，对可行流重新标号。下面通过一个例题来说明算法的基本步骤：例4、图5

30、-43表明一个网络及初始可行流，每条边上的有序数表示，求这个网络的最大流。 先给标以。检查的邻接点发现点满足，且令，给以标号。同理给点以标号。检查点的尚未标号的邻接点发现满足且令给以标号。检查点邻接的未标号点有，发现点满足且，令则给点以标号。点未标号，与邻接，边且所以令给以标号。类似前面的步骤，可由得到标号。由于已得到标号，说明存在增广链，所以标号过程结束，见图5-44。 转入调整过程，令为调整量，从点开始，由逆增广链方向按标号找到点，令。 再由点标号找到前一个点，并令。按点标号找到点。由于标号为为反向边，令。由点的标号在找到，令。由点找到，令调整过程结束，调整中的可增广链见图5-44，调整后

31、的可行流见图5-45。 重新开始标号过程，寻找可增广链，当标到点为以后，与点邻接的，点都不满足标号条件，所以标号无法再继续，而点并为得到标号，如图5-45。这时，即为最大流的流量，算法结束。用标号法在得到最大流的同时，可得到一个最小割。即图5-45中虚线所示。标号点集合为s，即，未标号点集合为此时割集，割集容量，与最大流的流量相等。四、最大匹配问题定义4、二部图，M是边集E的子集，若M中的任意两条边都没有公共端点，则称M为图G的一个匹配（也称对集）。M中任意条边的端点v称为（关于M的）饱和点，G中其他定点称为非饱和点。若不存在另一条匹配，则称M为最大匹配。例5、设有5位待业者，5项工作，他们各

32、自能胜任工作情况如图5-49所示，要求设计一个新业方案，使尽量多的人能就业。解 按前述方法增加虚拟的发、收的，用求最大流的标号法求解得到图5-49，在图中略去容量，只标出流量，。边上的流量都是1，所以让工作可得最大就业方案，即最多可以安排四个人就业。 课 题第五章图与网络模型 5.5 最小费用流问题 5.6 灾情巡视路线教学内容1、最小费用流的概念 2、求最小费用流的算法：“对偶算法”3、灾情巡视路线模型教学目标1、理解最小费用流的含义，了解灾情巡视路线模型；2、掌握求最小费用流的方法：“对偶算法”；教学重点 最小费用流的算法：“对偶算法”教学难点 最小费用流的算法：“对偶算法”双语教学内容、

33、安排 Minimum-cost flow 最小费用流; increment chain 可增广链; dual algorithm 对偶算法;教学手段、措施以板演为主，以多媒体和课堂讨论为辅作业、后记讨论题：P135: T8教学过程及教学设计备注 5.5最小费用流问题最小费用流问题的一般提法：已知容量网络,每条边（）除了已给的容量外，还给出了单位流量的费用，记。求的一个可行流，使得流量，且总费用最小.特别，当要求为最大流量时，此问题即为最小费用最大流问题。定义1、已知网络，是上的一个可行流，为从到的（关于的）可增广链，称为链的费用。最小费用流问题的常用算法有两种：（1）原始算法；（2）对偶算法。

34、下面只介绍对偶算法，本算法是有效算法。例1、如图5-51所示的可增广链中， ， 边上权为费用，则链的费用=（3+4+1+6）-（5+7）=2。 若是从到所有可增广链中费用最小的链，则称为最小费用可增广链。 对偶算法的基本思路：先找一个流量为的最小费用流，然后寻找从到的可增广链，用最大流方法将调整到，是流量为，且保证是在流量下的最小费用流，不断进行到为止。定理1：若是流量为的最小费用流，是关于的从到的一条最小费用可增广链，则经过调整流量得到新可行流（记为），一定是流量为的可行流中的最小费用流。由于，就是流量为0的最小费用流，所以初始最小费用流可以取，余下的问题是如何寻找关于的最小费用可增广链。定

35、义2：对网络，有可行流，保持原网络各点，每条边用两条方向相反的有向边代替，各边的权按如下规则：1 当边，令其中的意义是：这条边已饱和，不能再增大流量，否则要花费很高的代价，实际无法实现，因此权为的边可从网络中去掉。2 当边为原来中边的反向边，令这里的意义是：此边流量已减少到0，不能再减少，权为的边可从网络中去掉。这样得到的网络称为长度网络（将费用看成长度）。显然在中求关于的最小费用可增广链等价于在长度网络中求从到的最短路。寻求最小费用流的有效算法：“对偶算法”的基本步骤：（1） 取零流为初始可行流，即。（2） 若有，流量为，构造长度网络。（3） 在长度网络中求到的最短路。若不存在最短路，则已为

36、最大流，不存在流量等于的流，停止；否则转（4）。（4） 在中与这条最短路相应的可增广链上，作其中此时的流量为,若则停止，否则令代替返回（2）。例2、在图552（a）所示运输网络上，求流量为10的最小费用流，边上括号内为。 解：从开始作如图552（b），用Dijkstra算法求得网络中最短路为，在网络G中相应的可增广链上用最大流算法进行流的调整：， 结果见图5-52（c）。 作如图5-52（d），由于边上有负权，所以，求最短路不能用Dijkstra算法，可以用逐次逼近法。最短路为，在网络G内相应的可增广链上进行调整，得流，如图5-52（e）。 作如图5-52（f），得到从到的最短路为，在网络G内

37、调整得流，如图5-52（g）。即为所求的最小费用流。 5.6 灾情巡视路线 图553为某乡，（镇），村公路网示意图，公路边的数字为该路段的公里数。有一年夏天该县遭受水灾,为考察灾情，组织自救，县领导决定，带领有关部门负责人到全县各乡，（镇），村巡视。巡视路线指从县政府所在地出发，走遍各乡，镇，村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(1)假定各巡视人员在各乡（镇）停留时间小时，在各村停留时间小时，汽车行驶速度千米/小时。要在24小时内完成巡视，至少应分几组：给出这种分组下你认为最佳的巡视路线。(2)在上述关于，和的假定下，如果巡视人员足够多

38、，完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(3)若巡视组数已定（如三组），要求尽快完成巡视，讨论和,改变时最佳巡视路线的影响。以下我们参考当年的优秀答卷对此问题作分析。一、关于问题的数学模型本题给出了某县的道路交通网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的普遍性问题，也就是用若干条闭链覆盖图上的所在顶点，关使某些指标达到最优。在求本题的解之前，对原问题所给条件作一些适当的假设是必要的。例如，公路不考虑等级差别，也不受灾情或交通情况的影响，各条公路段段上汽车汽车行驶速度可以认为是均匀的，各巡视组巡视的乡（镇），村不

39、受行政区划的影响，即某乡（镇）与隶属于它的村不一定要分在同一组内，各巡视组统一行动，即不允许一个巡视组在分成若干小组等等。二、关于问题的具体求解本题的第一问，要求设计分三组巡视时使总路程最短，且各组尽可能均衡的巡视路线。这里有两个目标，若即三组的巡视路线长度从小到大分别为，则该两目标的数学表达式为：以及，但是这两个目标又是相互矛盾的，也就是不可能同时达到最小。因此具体求解时，应两者兼顾，用多目标的方法处理。为简单起见，根据实际问题灾情巡视的背景，一种较为合理的考虑是转换成一个目标函数，即分组以后，由于规模较小，最优巡视路线的设计就变的较为简单。一般可借助现成的软件求出精确解来，即便没有这类软件

40、采取近似算法或者直接搜索也都能较容易地找出很多的近似最优解。以下有两种参考答案，前者的总路程较短但均衡性较差，后者的均衡性相当好但总路程较长。第一组结果：第一组：O-C-G-34-35-32-30-Q-28-Q-29-R-31-33-A-1-O,总里程为153.1千米。第二组：O-P-2627-26-N-24-23-21-K-22-17-16-I-15-I-18-J-19-L-20-25-M-O,总里程为210.5千米。第三组：O-2-3-D-4-8-E-9-F-10-F-12-H-14-13-G-11-E-7-6-5-2-O,总里程为210.5千米。第二种结果：第一组：O-1-B-34-35-32-31-33-A-R-29-Q-30-Q-28-27-24-23-N-26-P-O,总里程为197.6千米。第二组：O-M-25-20-21-K-22-17-16-I-13-G-11-E-8-4-D-3-C-O,总里程为200.4千米。第三组：O-2-5-6-L-19-J-18-I-15-14-H-12-F-10-F-9-