六、图与网络分析 第11章 图与网络优化 第12章 网络计划

六、图与网络分析 图论 运筹学的重要分支 主要应用领域 图论理论和方法应用实例 物理学、化学、控制论、信息论、科学管理、电子计算机等 在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。 各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 清华大学出版社

六、图与网络分析 图论的起源与发展 欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。 七桥问题： 哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图10-1(a) 欧拉将此问题归结为如图10-1(b)所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图10-1(b)中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。 图10-1 清华大学出版社

第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题 第11章 图与网络优化 第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题

第1节 图的基本概念 铁路交通图 人们为反映一些对象之间关系时，常会用示意图。 例1 下图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的连线代表这两个城市之间的铁路线。 其他示意图的例子 电话线分布图、煤气管道图、航空线图等。 清华大学出版社

第1节 图的基本概念 比赛情况图 例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。 例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。 已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点 分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，如图10-3所示。 图10-3 比赛情况图 清华大学出版社

第1节 图的基本概念 例3 某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。用点 分别代表这八种药品，若药品vi和药品vj是不能存放在同一个库房的，则在vi和vj之间联一条线。 从这个图中可以看到，至少要有四个库房，因为 必须存放在不同的库房里。 事实上，四个库房就足够了。例如 各存放在一个库房里(这一类寻求库房的最少个数问题，属于图论中的所谓染色问题，一般情况下是尚未解决的)。 药品存放图 清华大学出版社

第1节 图的基本概念 比赛情况图 图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系 图：是反映对象之间关系的一种抽象 点：代表研究的对象； 连线：表示两个对象之间特定的关系。 图：是反映对象之间关系的一种抽象 一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。 如例2，也可以用图10-5所示的图去反映五个球队的比赛情况，与图10-3没有本质区别。 比赛情况图 图10-5 清华大学出版社

第1节 图的基本概念 比赛胜负图 关系的对称性和非对称性： 几个例子中涉及到的对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙与甲也有这种关系。 实际生活中，有许多关系不具有这种对称性。 如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图10-3中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。 例如，如果球队v1胜了球队v2，可以从v1引一条带箭头的连线到v2 类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输中的“单行线”，部门之间的领导与被领导的关系，一项工程中各工序之间的先后关系等。 比赛胜负图 清华大学出版社

第1节 图的基本概念 图的概念 图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。 两点之间不带箭头的连线称为边，带箭头的连线称为弧。 如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记为 ，式中V，E分别是G的点集合和边集合。一条连结点 的边记为［ ］(或［ ］)。 如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为( )。 清华大学出版社

第1节 图的基本概念 无向图的例子 其中 无向图 图10-7 清华大学出版社

第1节 图的基本概念 有向图的例子 其中 有向图 图10-8 清华大学出版社

第1节 图的基本概念 图的重要概念（续） 图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D))，分别简记为p，q。 无向图G=(V，E)常用的一些名词和记号： 若边e =［u，v］∈E，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关连边。 若图G中，某个边e的两个端点相同，则称e是环(如图10-7中的e7)。 若两个点之间有多于一条的边，称这些边为多重边(如图10-7中的e1,e2)。 清华大学出版社

第1节 图的基本概念 图论中几个重要记号和术语 图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)或 q(D)，分别简记为p，q。 无向图G=(V，E)常用的一些名词和记号： 若边e =［u，v］∈E，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关连边。 若图G中，某个边e的两个端点相同，则称e是环(如图10-7中的e7)。 若两个点之间有多于一条的边，称这些边为多重边(如图10-7中的e1,e2)。 清华大学出版社

第1节 图的基本概念 图论中几个重要记号和术语（续） 一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。 以点v为端点的边的个数称为v的次，记为dG(v)或d(v)。如图10-7中，d(v1)=4，d(v2)=3，d(v3)=3，d(v4)=4(环e7在计算d(v4)时算作两次)。 称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。 清华大学出版社

第1节 图的基本概念 定理1 图G=(V，E)中，所有点的次之和是边数的两倍，即 证明：显然，在计算各点的次时，每条边被它的端点各用了一次。 次为奇数的点，称为奇点，否则称为偶点。 清华大学出版社

第1节 图的基本概念 定理2 任一个图中，奇点的个数为偶数。 证明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有 定理2 任一个图中，奇点的个数为偶数。 证明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有 因 是偶数， 也是偶数，故 必定也是偶数，从而V1的点数是偶数。 清华大学出版社

第1节 图的基本概念 图论中几个重要记号和术语（续） 给定一个图G=(V,E)和一个点、边交错序列 , 如果满足 (t=1，2，…，k-1) 则称为一条联结 的链，记为 称点 为链的中间点。 清华大学出版社

第1节 图的基本概念 图论中几个重要记号和术语（续） 链 中，若 ，则称之为一个圈，记为 。 若链 中，点 都是不同的，则称之为初等链；若圈 链 中，若 ，则称之为一个圈，记为 。 若链 中，点 都是不同的，则称之为初等链；若圈 中， 都是不同的，则称之为初等圈。 若链(圈)中含的边均不相同，则称之为简单圈。以后说到链(圈)，除非特别交代，均指初等链(圈)。 清华大学出版社

第1节 图的基本概念 例子 初等链与初等圈 图10-9中， 是一条简单链，但不是初等链， 是一条初等链。图中不存在联结v1和v9的链。 是一个初等圈， 是简单圈，但不是初等圈。 初等链与初等圈 图10-9 清华大学出版社

第1节 图的基本概念 连通图 图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。 图10-9是一个不连通图，它有两个连通分图。 清华大学出版社

第1节 图的基本概念 支撑子图 给了一个图G=(V，E)，如果G′=(V′，E′)，使V=V′及E′∈E ，则称G′是G的一个支撑子图。 设v∈V(G)，用G−v表示从图G中去掉点v及v的关联边后得到的一个图。 若G如图10-10(a)所示，则G − v3见图10-10(b)，图10-10(c)是图G的一个支撑子图。 图10-10 清华大学出版社

第1节 图的基本概念 和有向图有关的概念和术语 设给定一个有向图，D=(V，A)，从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G(D)。 给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。 设 是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链(圈)。 如果 是D中的一条链，并且对t=1，2，…，k-1，均有 ，称之为从 的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路(回路)。 清华大学出版社

第1节 图的基本概念 有向图的例子 是一个回路； 图10-8。 是从v1到v6的路； 是一条链，但不是路。 对无向图，链与路(圈与回路)两个概念是一致的。 类似于无向图，可定义简单有向图、多重有向图。 图10-8是一个简单有向图。 清华大学出版社

第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题 第10章 图与网络优化 第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题

第2节 树 2.1 树及其性质 2.2 图的支撑树 2.3 最小支撑树问题 清华大学出版社

2.1 树及其性质 树：一类极其简单然而却很有用的图。 例4 图10-11 已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话(允许通过其他城市)，并且电话线的根数最少。 图10-11 清华大学出版社

2.1 树及其性质 用五个点v1，v2，v3，v4，v5代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可以用一个图来表示。为了使任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图10-11代表了满足要求的一个电话线网。 清华大学出版社

2.1 树及其性质 定义1（树的定义） 一个无圈的连通图称为树。 例5 某工厂的组织机构如下所示 工厂组织机构图 清华大学出版社

2.1 树及其性质 如果用图表示，该工厂的组织机构图就是一个树(如图10-12所示)。 树 图10-12 清华大学出版社

2.1 树及其性质 定理3 设图G=(V，E)是一个树，p(G)≥2，则G中至少有两个悬挂点。 证明:令 是G中含边数最多的一条初等链，因p(G)≥2，并且G是连通的，故链P中至少有一条边，从而v1与vk是不同的。现在来证明：v1是悬挂点，即d(v1)=1。 用反证法，如果d(v1)≥2，则存在边 使m≠2。若点vm不在P上，那么 是G中的一条初等链，它含的边数比P多一条，这与P是含边数最多的初等链矛盾。若点vm在P上，那么 是G中的一个圈，这与树的定义矛盾。于是必有d(v1)=1，即v1是悬挂点。同理可证vk也是悬挂点，因而G至少有两个悬挂点。 清华大学出版社

2.1 树及其性质 定理4 图G=(V，E)是一个树的充分必要条件是G不含圈，且恰有p−1条边。 这与q(G)=p(G) − 1的假设矛盾。 证明：必要性。设G是一个树，根据定义，G不含圈，故只要证明G恰有p −1条边。对点数p施行数学归纳法。p=1，2时，结论显然成立。假设对点数p≤n时，结论成立。设树G含n+1个点。由定理3，G含悬挂点，设v1是G的一个悬挂点，考虑图G − v1，易见p(G − v1)=n，q(G − v1)=q(G) − 1。因G − v1是n个点的树，由归纳假设，q(G − v1)=n − 1，于是q(G)=q(G − v1)+1=(n−1)+1=n=p(G) −1。 充分性 。只要证明G是连通的。用反证法，设G是不连通的，G含s个连通分图G1，G2，…，Gs(s≥2)。因每个Gi(i=1，2，…，s)是连通的，并且不含圈，故每个Gi是树。设Gi有pi个点，则由必要性，Gi有pi− 1条边，于是 这与q(G)=p(G) − 1的假设矛盾。 清华大学出版社

2.1 树及其性质 定理5 图G=(V，E)是一个树的充分必要条件是G是连通图，并且q(G)=p(G) − 1 证明：必要性 。设G是树，根据定义，G是连通图，由定理4，q(G)=p(G)−1。 充分性 。只要证明G不含圈，对点数施行归纳。p(G)=1，2时，结论显然成立。 设p(G)=n(n≥1)时结论成立。现设p(G)=n+1，首先证明G必有悬挂点。若不然，因G是连通的，且p(G)≥2，故对每个点vi，有d(vi)≥2。从而 这与q(G)=p(G)−1矛盾，故G必有悬挂点。设v1是G的一个悬挂点，考虑G−v1，这个图仍是连通的，q(G − v1)=q(G) − 1=p(G) − 2=p(G − v1) − 1，由归纳假设知G − v1不含圈，于是G也不含圈。 清华大学出版社

2.1 树及其性质 定理6 图G是树的充分必要条件是任意两个顶点之间恰有一条链。 证明 必要性。 因G是连通的，故任两个点之间至少有一条链。但如果某两个点之间有两条链的话，那么图G中含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。 充分性 。设图G中任两个点之间恰有一条链，那么易见G是连通的。如果G中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设矛盾，故G不含圈，于是G是树。 清华大学出版社

2.1 树及其性质 由定理6，很容易推出如下结论： (1) 从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。这样，例4中所要求的电话线网就是以这五个城市为点的一个树。 (2) 在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。 如图10-11中，添加 ，就得到一个圈 ，如果从这个圈中去掉一条边 ，就得到如图10-13所示的树。 图10-13 清华大学出版社

2.2 图的支撑树 定义2 设图T=(V，E′)是图G=(V，E)的支撑子图，如果图T=(V，E′)是一个树，则称T是G的一个支撑树。 图10-14(b)是图10-14(a)所示图的一个支撑树。 图10-14 清华大学出版社

2.2 图的支撑树 若T=(V，E′)是G=(V，E)的一个支撑树，则显然，树T中边的个数是p(G) − 1，G中不属于树T的边数是q(G) − p(G)+1。 清华大学出版社

2.2 图的支撑树 定理7 图G有支撑树的充分必要条件是图G是连通的。 证明：必要性是显然的。 充分性。设图G是连通图，如果G不含圈，那么G本身是一个树，从而G是它自身的一个支撑树。现设G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树(因为易见G1是连通的)；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk，它不含圈，于是Gk是G的一个支撑树。 定理7充分性的证明，提供了一个寻求连通图的支撑树的方法。这就是任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑树，称这种方法为“破圈法”。 清华大学出版社

2.2 图的支撑树 例6 在图10-15中，用破圈法求出图的一个支撑树。 例6 在图10-15中，用破圈法求出图的一个支撑树。 解 取一个圈 ，从这个圈中去掉边 ；在余下的图中，再取一个圈 ，去掉边 ；在余下的图中，从圈 中去掉边；再从圈中去掉边 。这时，剩余的图中不含圈，于是得到一个支撑树，如图10-15中粗线所示。 也可以用另一种方法来寻求连通图的支撑树。在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条 与不构成圈的边e3，一般，设已有 ，找一条与 中的任何一些边不构成圈的边ek+1。重复这个过程，直到不能进行为止。这时，由所有取出的边所构成的图是一个支撑树，称这种方法为“避圈法”。 清华大学出版社

2.2 图的支撑树 图10-16 图10-15 清华大学出版社

2.3 最小支撑树问题 例7 在图10-16中，用避圈法求出一个支撑树。 例7 在图10-16中，用避圈法求出一个支撑树。 解 首先任取边e1，因e2与e1不构成圈，所以可以取e2，因为e5与 不构成圈，故可以取e5(因e3与 构成一个圈 ，所以不能取e3)；因e6与 不构成圈，故可取e6；因e8与 不构成圈，故可取e8(注意，因e7与 中的e5，e6构成圈 ，故不能取e7)。这时由 所构成的图就是一个支撑树，如图10-16中粗线所示。 实际上，由定理4，5可知，在“破圈法”中去掉的边数必是q(G) − p(G)+1条，在“避圈法”中取出的边数必定是p(G) − 1条。 清华大学出版社

2.3 最小支撑树问题 定义3 给图G=(V，E)，对G中的每一条边 ，相应地有一个数wij，则称这样的图G为赋权图，wij称为边 上的权。 这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等。 赋权图在图的理论及其应用方面有重要的地位。赋权图不仅指出了各点之间的邻接关系，而且同时也表示了各点之间的数量关系。所以，赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。 清华大学出版社

2.3 最小支撑树问题 设有一个连通图G=(V，E)，每一边e= ，有一个非负权 w(e)=wij (wij ≥0) 定义4 如果T=(V，E′)是G的一个支撑树，称E′中所有边的权之和为支撑树T的权，记为w(T)。即 如果支撑树T* 的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树)。即 式中对G的所有支撑树T取最小。 清华大学出版社

2.3 最小支撑树问题 最小支撑树问题 最小支撑树问题就是要求给定连通赋权图G的最小支撑树。 例子 下面介绍两个求解最小支撑树的方法。 假设给定一些城市，已知每对城市间交通线的建造费用。要求建造一个联结这些城市的交通网，使总的建造费用最小，这个问题就是赋权图上的最小树问题。 下面介绍两个求解最小支撑树的方法。 清华大学出版社

2.3 最小支撑树问题 1. 避圈法(kruskal) 开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选一条权最小的。(每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条)。 算法的具体步骤如下： 第1步：令i=1， 。 第2步：选一条边 ，使ei是使 不含圈的所有边e( )中权最小的边。令 ，如果这样的边不存在，则T=(V，Ei-1)是最小树。 第3步：把i换成i+1，转入第2步。 清华大学出版社

2.3 最小支撑树问题 在证明这个方法的正确性之前，先介绍一个例子。 例8 某工厂内联结六个车间的道路网如图10-17(a)所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。 清华大学出版社

2.3 最小支撑树问题 解 这个问题就是求如图10-17(a)所示的赋权图上的最小树，用避圈法求解。 i=1,E0=Ø，从E中选最小权边［v2，v3］，E1=｛［v2，v3］｝； i=2,从E＼E1中选最小权边［v2，v4］(［v2，v4］与［v2，v3］不构成圈)，E2=｛［v2，v3］，［v2，v4］｝； i=3，从E＼E2中选［v4，v5］((V，E2∪｛［v4，v5］｝)不含圈)，令E3=｛［v2，v3］，［v2，v4］，［v4，v5］｝； i=4，从E＼E3中选［v5，v6］(或选［v4，v6］)((V，E3∪｛［v5，v6］｝)不含圈)，令E4=｛［v2，v3］，［v2，v4］，［v4，v5］，［v5，v6］｝； i=5，从E＼E4中选［v1，v2］((V，E4∪｛［v1，v2］｝)不含圈)。注意，因［v4，v6］与已选边［v4，v5］，［v5，v6］构成圈，所以虽然［v4，v6］的权小于［v1，v2］的权，但这时不能选［v4，v6］)，令E5=｛［v2，v3］，［v2，v4］，［v4，v5］，［v5，v6］，［v1，v2］｝； i=6，这时，任一条未选的边都与已选的边构成圈，所以算法终止。 (V，E5)就是要求的最小树，即电话线总长最小的电话线网方案(图10-17(b))，电话线总长为15单位。 清华大学出版社

2.3 最小支撑树问题 证明避圈法的正确性。 令G=(V，E)是连通赋权图，根据2.2中所述可知：方法一终止时，T=(V，Ei-1)是支撑树，并且这时i=p(G)。记 E(T)=｛e1，e2，…，ep-1｝ 式中p=p(G)，T的权为 清华大学出版社

2.3 最小支撑树问题 反证法：设T不是最小支撑树，在G的所有支撑树中，令H是与T的公共边数最大的最小支撑树。因T与H不是同一个支撑树，故T中至少有一条边不在H中。令ei(1≤i≤p-1)是第一个不属于H的边，把ei放入H中，必得到一个且仅一个圈，记这个圈为C。因为T是不含圈的，故C中必有一条边不属于T，记这条边为e。在H中去掉e，增加ei，就得到G的另一个支撑树T0，可见 因为 (因H是最小支撑树)，推出 。但根据算法，ei是使(V,｛e1，e2，…，ei｝)不含圈的权最小的边，而(V,｛e1，e2，…，ei-1，e｝)也是不含圈的，故必有 ，从而 。这就是说T0也是G的一个最小支撑树，但是T0与T的公共边数比H与T的公共边数多一条，这与H的选取矛盾。 清华大学出版社

2.3 最小支撑树问题 2. 破圈法 任取一个圈，从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。 清华大学出版社

2.3 最小支撑树问题 例9 用破圈法求图10-17(a)所示赋权图的最小支撑树。 解:任取一个圈，比如(v1，v2，v3，v1)，边［v1，v3］是这个圈中权最大的边，于是丢去［v1，v3］；再取圈(v3，v5，v2，v3)，去掉［v2，v5］；取圈(v3，v5，v4，v2，v3)，去掉［v3，v2］；取圈(v5，v6，v4，v5)，这个圈中，［v5，v6］及［v4，v6］都是权最大的边，去掉其中的一条，比如说［v4，v6］。这时得到一个不含圈的图(如图10-17(b)所示)，即为最小树。 破圈法的证明从略。 清华大学出版社

第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题 第10章 图与网络优化 第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题

第3节 最短路问题 3.1 引例 3.2 最短路算法 3.3 应用举例 清华大学出版社

3.1 引例 例10 已知如图10-18所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求使图10-18总费用最小的旅行路线。 图10-18 清华大学出版社

3.1 引例 由上例可见 从v1到v8的旅行路线有很多 例如可以从v1出发，依次经过v2，v5，然后到v8；也可以从v1出发，依次经过v3，v4，v6，v7，然后到v8等。 不同的路线所需总费用是不同的。 用图的语言来描述，从v1到v8的一条旅行路线就是图中从v1到v8的一条路；一条旅行路线的总费用就是相应的从v1到v8的路中所有弧旁数字之和。 清华大学出版社

3.1 引例 一般意义的最短路问题 给定一个赋权有向图，即给了一个有向图D=(V，A)，对每一个弧a=(vi，vj)，相应地赋予了权数；又给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路P0，使 式中对D中所有从vs到vt的路P取最小，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs，vt)。显然，d(vs，vt)与d(vt，vs)不一定相等。 最短路问题是一类重要的优化问题，它不仅可以直接应用于解决生产实际中的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且还经常作为一个基本工具，用于解决其他优化问题。 清华大学出版社

3.2 最短路算法 在一个赋权有向图中寻求最短路的方法，实际上求从给定一个点vs到任一个点vj的最短路。 如下事实是经常要利用的 如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。事实上，如果这个结论不成立，设Q是从vs到vi的最短路，令P′是从vs沿Q到达vi，再从vi沿P到达vj的路，那么，P′的权就比P的权小，这与P是从vs到vj的最短路矛盾。 清华大学出版社

3.2 最短路算法 首先介绍所有wij≥0情形下的求最短路的方法。 Dijkstra方法的基本思想 从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p−1步，就可以求出从vs到各点的最短路。 清华大学出版社

3.2 最短路算法 以例10为例说明该方法的基本思想。 例10中，s=1。因为所有wij≥0，故有d(v1，v1)=0。这时，v1是具P标号的点。 现考查从v1发出的三条弧，(v1，v2)，(v1，v3)，和(v1，v4)。 如果从v1出发沿(v1，v2)到达v2，需要d(v1，v1)+w12=6单位的费用； 如果从v1出发，沿(v1，v3)到达v3，则需要d(v1，v1)+w13=3单位的费用； 类似地，若沿(v1，v4)到达v4，需要d(v1，v1)+w14=1单位的费用。 因为 min｛d(v1,,v1)+ω12,d(v1,v1)+w13，d(v1,v1)+w14｝=d(v1,v1)+w14=1 所以从v1出发到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1，v4)，d(v1，v4)=1。这样就可以使v4变成具P标号的点。 清华大学出版社

3.2 最短路算法 现考查从v1及v4指向其余点的弧 由上已知，从v1出发，分别沿(v1，v2)、(v1，v3)到达v2，v3，需要6单位或3单位的费用，而从v4出发沿(v4，v6)到达v6，所需要的费用是d(v1，v4)+ w46=1+10=11单位，因为 min｛d(v1，v1)+w12，d(v1，v1)+w13，d(v1，v4)+w46｝=d(v1，v1)+w13=3 可以断言，从v1到v3的最短路是(v1，v3)，d(v1，v3)=3。这样又可以使点v3变成具P标号的点。 重复这个过程，可以求出从v1到任一点的最短路。 清华大学出版社

3.2 最短路算法 在Dijkstra方法中 P，T分别表示某个点的P标号、T标号， Si表示第i步时，具P标号点的集合。 为了在求出从vs到各点的距离的同时，也求出从vs到各点的最短路，给每个点v以一个λ值。算法终止时，如果λ(v)=m，表示在从vs到v的最短路上，v的前一个点是vm；如果λ(v)=M，则表示D中不含从vs到v的路；λ(v)=0表示v=vs。 清华大学出版社

3.2 最短路算法 Dijkstra方法的具体步骤：给定赋权有向图D=(V，A)。 开始(i=0)令S0=｛vs｝，P(vs)=0，λ(vs)=0，对每一个v≠vs，令T(v)=+∞，λ(v)=M，令k=s。 ① 如果Si=V，算法终止，这时，对每个v∈Si，d(vs，v)=P(v)；否则转入②。 ② 考查每个使(vk，vj)∈A且的点vj。 如果T(vj)＞P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把λ(vj)修改为k；否则转入③。 ③ 令。 如果，则把的T标号变为P标号，令，把i换成i+1，转入①；否则终止，这时对每一个v∈Si，d(vs，v)=P(v)，而对每一个，d(vs，v)=T(v)。 清华大学出版社

3.2 最短路算法 用Dijkstra方法求例10中从v1到各个顶点的最短路 这时s=1。 (1) i=0， S0=｛v1｝，P(v1)=0，λ(v1)=0，T(vi)=+∞，λ(vi)=M (i=2，3，…，9)，以及k=1。 转入②，因(v1，v2)∈A，，P(v1)+w12＜T(v2)，故把T(v2)修改为P(v1)+w12=6，λ(v2)修改为1； 同理，把T(v3)修改为P(v1)+w13=3，λ(v3)修改为1；把T(v4)修改为P(v1)+w14=1，λ(v4)修改为1。 转入③，在所有的T标号中T(v4)=1最小，于是令P(v4)=1，令S1=S0∪｛v4｝=｛v1，v4｝，k=4。 (2) i=1 转入②，把T(v6)修改为P(v4)+w46=11，λ(v6)修改为4。 转入③，在所有T标号中，T(v3)=3最小，于是令P(v3)=3，令S2=｛v1，v4，v3｝，k=3。 清华大学出版社

3.2 最短路算法 (3) i=2 转入②，因(v3，v2)∈A，v2S2，T(v2)＞P(v3)+w32，把T(v2)修改为P(v3)+w32=5，λ(v2)修改为3。 转入③，在所有T标号中，T(v2)=5最小，于是令P(v2)=5，S3=｛v1，v4，v3，v2｝，k=2。 (4) i=3 转入②，把T(v5)修改为P(v2)+w25=6，λ(v5)修改为2。 转入③，在所有T标号中，T(v5)=6最小，于是令P(v5)=6，S4=｛v1，v4，v3，v2，v5｝，k=5。 (5) i=4 转入②，把T(v6)，T(v7)，T(v8)分别修改为10，9，12，把λ(v6)，λ(v7)，λ(v8)修改为5。 转入③，在所有T标号中，T(v7)=9最小，于是令 P(v7)=9，S5=｛v1，v4，v3，v2，v5，v7｝，k=7 清华大学出版社

3.2 最短路算法 (6) i=5 转入②，(v7，v8)∈A，，但因T(v8)＜P(v7)+ω73，故T(v8)不变。 转入③，在所有T标号中，T(v6)=10最小，令 P(v6)=10，S6=｛v1，v4，v3，v2，v5，v7，v6｝，k=6。 (7) i=6 转入②，从v6出发没有弧指向不属于S6的点，故直接转入③。 转入③，在所有T标号中，T(v8)=12最小，令 P(v8)=12，S7=｛v1，v4，v3，v2，v5，v7，v6，v8｝，k=8。 (8) i=7 转入③，这时仅有的T标号点为v9，T(v9)=+∞，算法终止。 清华大学出版社

3.2 最短路算法 算法终止时的有关结果如下： P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6， P(v7)=9，P(v6)=10，P(v8)=12，T(v9)=+∞ λ(v1)=0，λ(v4)=1，λ(v3)=1，λ(v2)=3，λ(v5)=2， λ(v7)=5，λ(v6)=5，λ(v8)=5，λ(v9)=M 表明：对i=1，2，…，8，d(v1，vi)=P(vi)，而从v1到v9不存在路，根据λ值可以求出从v1到vi的最短路(i=1，2，…，8)。 例如，为求v1到v8的最短路，考查λ(v8)，因λ(v8)=5，故最短路包含弧(v5，v8)；再考查λ(v5)，因λ(v5)=2，故最短路包含弧(v2，v5)；类推，λ(v2)=3，λ(v3)=1，于是最短路包含弧(v3，v2)，及(v1，v3)，这样从v1到v8的最短路是(v1，v3，v2，v5，v8)。 清华大学出版社

3.2 最短路算法 有向图的最短路算法 上面介绍了如何在一个赋权有向图中，求从一个顶点vs到各个顶点的最短路。 对于赋权(无向)图G=(V，E)，因为沿边［vi，vj］既可以从vi到达vj，也可以沿vj到达vi，所以边［vi，vj］可以看作是两条弧(vi，vj)及(vj，vi)，它们具有相同的权w［vi，vj］。这样，在一个赋权图中，如果所有的w ij≥0，只要把Dijkstra方法中的“②考查每个使(vk，vj)∈A且的点vj”改为“②考查每个使［vk，vj］∈E且的点vj”，同样地可以求出从vs到各点的最短路(对于无向图，即为最短链)。 清华大学出版社

3.2 最短路算法 例11 用Dijkstra方法求图10-19所示的赋权图中，从v1到v8的最短路。 图10-19 清华大学出版社

3.2 最短路算法 解 计算的最后结果为 P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。 λ(v1)=0，λ(v4)=1，λ(v5)=1，λ(v2)=3，λ(v5)=2，λ(v9)=5，λ(v7)=5，λ(v6)=5，λ(v8)=9。 这样从v1到v8的最短链为(v1，v3，v2，v5，v9，v8)，总权为11。 清华大学出版社

3.2 最短路算法 证明Dijkstra方法的正确性。 只要证明对于每一个点v∈Si，P(v)是从vs到v的最短路的权，即d(vs,v)=P(v)即可。 对i施行归纳，i=0时，结论显然正确。设对i=n时，结论成立，即对每一个v∈Sn，d(vs,v)=P(v)。现在考查i=n+1，因 ，所以只要证明 。根据算法， 是这时的具最小T标号的点，即 这里为了清晰起见，用Tn(v)表示当i=n执行步骤③时点v的T标号。 清华大学出版社

3.2 最短路算法 假设H是D中任一条从vs到的路，因为vs∈Sn，而 ，那么从vs出发，沿H必存在一条弧，它的始点属于Sn，而终点不属于Sn。假设(vr，v1)是第一条这样的弧， 由归纳假设，P(vr)是从vs到vr的最短路的权，于是 清华大学出版社

3.2 最短路算法 根据方法中T标号的修改规则，因vr∈Sn， ，故 。 而 ，故 (因为所有的wij≥0，故 )。 而 ，故 (因为所有的wij≥0，故 )。 这就证明了 是从vs到 的最短路的权，由方法， ，这样就证明了 清华大学出版社

3.2 最短路算法 Dijkstra算法只适用于所有wij≥0的情形，当赋权有向图中存在负权时，则算法失效。例如在如图10-20所示的赋权有向图中，如果用Dijkstra方法，可得出从v1到v2的最短路的权是1，但这显然是不对的，因为从v1到v2的最短路是(v1，v3，v2)，权是-1。 图10-20 清华大学出版社

3.2 最短路算法 现介绍当赋权有向图中存在具负权弧时，求最短路的方法。 为方便起见，不妨设从任一点vi到任一个点vj都有一条弧(如果在D中， ，则添加弧(vi，vj)。令wij=+∞)。 显然，从vs到vj的最短路总是从vs出发，沿着一条路到某个点vi，再沿(vi，vj)到vj的(这里vi可以是vs本身)，由本节开始时介绍的一个结论可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d(vs，vj)必满足如下方程： 清华大学出版社

3.2 最短路算法 为了求得这个方程的解d(vs，v1)，d(vs，v2)，…，d(vs，vp)(这里p=p(D))，可用如下递推公式： 开始时，令 ,(j=1，2，…，p) 对t=2,…3, j=1，2，…，p 若进行到某一步，例如第k步时，对所有j=1，2，…，p，有 则 即为vs到各点的最短路的权。 清华大学出版社

3.2 最短路算法 例12 求图10-21所示赋权有向图中从v1到各点的最短路。 解 利用上述递推公式，求解结果如表10-1所示(表中未写数字的空格内是+∞)。 图10-21 清华大学出版社

3.2 最短路算法 表10-1 (表中未写数字的空格内是+∞) 清华大学出版社

3.2 最短路算法 可以看到，当t=4时，对所有j=1，2，…，8，有 ，于是表中最后一列0，-5，-2，-7，-3，-1，-5，6就分别是从v1到v1，v2，…，v8的最短路的权。 为了进一步求得从vs到各点的最短路，可以类似于Dijkstra方法中，给每一个点以λ值开始， λ(vs)=0，λ(vi)=s (i≠s) 清华大学出版社

3.2 最短路算法 在迭代过程中，如果 则把这时的λ(vj)修改为i0。迭代终止时，根据各点的λ值，可以得到从vs到各点的最短路。 寻求最短路的另一个办法是在求出最短路的权以后，采用“反向追踪”的方法。比如已知d(vs，vj)，则寻求一个点vk，使d(vs，vk)+wk j=d(vs，vj)，记录下(vk，vj)，再考查d(vs，vk)，寻求一点vi，使d(vs，vi)+wi k=d(vs，vk)，如此等等，直至到达vs为止，于是从vs到vj的最短路是(vs,…,vi，vk，vj) 清华大学出版社

3.2 最短路算法 如例3，由表10-1已知，d(v1，v8)=6， 因d(v1，v6)+w68=(-1)+7=d(v1，v8)，故记下(v6，v8)。 因d(v1，v3)+w36=d(v1，v6)，故记下(v3，v6)。 因d(v1，v7)+w73=d(v1，v3)，从而从v1到v8的最短路是(v1，v3，v6，v8)。 清华大学出版社

3.2 最短路算法 定义5 设D是赋权有向图，C是D中的一个回路，如果C的权w(C)小于零，则称C是D中的一个负回路。 不难证明： (1) 如果D是不含负回路的赋权有向图，那么，从vs到任一个点的最短路必可取为初等路，从而最多包含p-2个中间点； (2) 上述递推公式中的 是在至多包含t-1个中间点的限制条件下，从vs到vj的最短路的权。 由(1)、(2)可知：当D中不含负回路时，上述算法最多经过p-1次迭代必定收敛，即对所有的j=1，2，…，p，均有 ，从而求出从vs到各个顶点的最短路的权。 清华大学出版社

3.2 最短路算法 如果经过p-1次迭代，存在某个j，使 ，则说明D中含有负回路。显然，这时从vs到vj的路的权是没有下界的。 为了加快收敛速度，可以利用如下的递推公式。 (j=1，2，…，p)，(t=2，3，…) 清华大学出版社

3.2 最短路算法 J.Y.Yen提出一个改进的递推算法： 对t=2，4，6，…，按j=1，2，…，p的顺序计算： 对t=3，5，7，…，按j=p，p-1，…，1的顺序计算： 同样地，当对所有的j=1，2，…，p 时，算法终止。 清华大学出版社

3.3 应用举例 例13 设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格为： 第1年 第2年 第3年 第4年 第5年 11 12 13 清华大学出版社

3.3 应用举例 还已知使用不同时间(年)的设备所需要的维修费用为： 使用年数 0～1 1～2 2～3 3～4 4～5 维修费用 5 6 8 11 18 可供选择的设备更新方案显然是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为5，五年合计为25。于是五年总的支付费用为59+25=84。 又如决定在第一、三、五年各购进一台，这个方案的设备购置费为11+12+13=36，维修费为5+6+5+6+5=27。五年总的支付费用为63。 清华大学出版社

3.3 应用举例 如何制定使得总的支付费用最少的设备更新计划呢?可以把这个问题化为最短路问题，见图10-22。 图10-22 清华大学出版社

3.3 应用举例 用点vi代表“第i年年初购进一台新设备”这种状态(加设一点v6，可以理解为第5年年底)。从vi到vi+1，…，v6各画一条弧。弧(vi，vj)表示在第i年年初购进的设备一直使用到第j年年初(即第j-1年底)。 每条弧的权可按已知资料计算出来。例如，(v1，v4)是第1年年初购进一台新设备(支付购置费11)，一直使用到第3年年底(支付维修费5+6+8=19)，故(v1，v4)上的权为30。 这样一来，制定一个最优的设备更新计划问题就等价于寻求从v1到v6的最短路的问题。 按求解最短路的计算方法，｛v1，v3，v6｝及｛v1，v4，v6｝均为最短路，即有两个最优方案。一个方案是在第1年、第3年各购置一台新设备；另一个方案是在第1年、第4年各购置一台新设备。五年总的支付费用均为53。 清华大学出版社

第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题 第10章 图与网络优化 第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题

引言 许多系统包含了流量问题。例如，公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等。 图10-23是联结某产品产地v1和销地v6的交通网，每一弧(vi，vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从v1输送到v6。现在要求制定一个运输方案使从v1运到v6的产品数量最多。 图10-24给出了一个运输方案，每条弧旁的数字表示在这个方案中，每条运输线上的运输数量。这个方案使8个单位的产品从v1运到v6，在这个交通网上输送量是否还可以增多，或者说这个运输网络中，从v1到v6的最大输送量是多少呢?本节就是要研究类似这样的问题。 清华大学出版社

引言 图10-24 图10-23 清华大学出版社

第4节 网络最大流问题 4.1 基本概念与基本定理 4.2 寻求最大流的标号法 清华大学出版社

4.1 基本概念与基本定理 1.网络与流 定义6 给一个有向图D=(V，A)，在V中指定了一点称为发点(记为vs)，而另一点称为收点(记为vt)，其余的点叫中间点。对于每一个弧(vi，vj)∈A，对应有一个c(vi，vj)≥0(或简写为ci j)，称为弧的容量。通常我们就把这样的D叫作一个网络。记作 D=(V，A，C) 所谓网络上的流，是指定义在弧集合A上的一个函数f =｛f(vi，vj)｝，并称f(vi，vj)为弧(vi,vj)上的流量(有时也简记作fi j)。 例如图10-23就是一个网络，指定v1是发点，v6是收点，其他的点是中间点。弧旁的数字为cij。 图10-24所示的运输方案，就可看作是这个网络上的一个流，每个弧上的运输量就是该弧上的流量，即f12=5，f24=2，f13=3，f34=1等。 清华大学出版社

4.1 基本概念与基本定理 2. 可行流与最大流 在运输网络的实际问题中可以看出，对于流有两个明显的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量；由于中间点只起转运作用，所以中间点的流量必为零。易见发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。因此有： 清华大学出版社

4.1 基本概念与基本定理 定义7 满足下述条件的流f称为可行流： (1) 容量限制条件：对每一弧(vi，vj)∈A 0≤fij≤cij (2) 平衡条件： 对于中间点：流出量等于流入量，即对每个i(i≠s,t)有 对于发点vs，记 对于收点vt，记 式中v(f )称为这个可行流的流量，即发点的净输出量(或收点的净输入量)。 清华大学出版社

4.1 基本概念与基本定理 可行流总是存在的。比如令所有弧的流量fij=0，就得到一个可行流(称为零流)。其流量v(f)=0。 0≤fij≤cij (vi，vj)∈A ① ② 最大流问题是一个特殊的线性规划问题。即求一组｛fij｝，在满足条件①和②下使v(f)达到极大。将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。 清华大学出版社

4.1 基本概念与基本定理 3.增广链 若给一个可行流f=｛fij｝，我们把网络中使fij=cij的弧称为饱和弧，使fij＜cij的弧称为非饱和弧。使fij=0的弧称为零流弧，使fij＞0的弧称为非零流弧。 图10-24中，(v5，v4)是饱和弧，其他的弧为非饱和弧。所有弧都是非零流弧。 若μ是网络中联结发点vs和收点vt的一条链，我们定义链的方向是从vs到vt，则链上的弧被分为两类： 一类是弧的方向与链的方向一致，叫做前向弧。前向弧的全体记为μ+。 另一类弧与链的方向相反，称为后向弧。后向弧的全体记为μ-。 清华大学出版社

4.1 基本概念与基本定理 定义8 设f是一个可行流，μ是从vs到vt的一条链，若μ满足下列条件，称之为(关于可行流f的)增广链。 在弧(vi，vj)∈μ+上，0≤fij＜cij，即μ+中每一弧是非饱和弧。 在弧(vi，vj)∈μ-上，0＜fij≤cij，即μ-中每一弧是非零流弧。 图10-24中，链μ=(v1，v2，v3，v4，v5，v6)是一条增广链。因为μ+和μ-中的弧满足增广链的条件。比如： (v1，v2)∈ μ+ ，f12=5＜c12=10 (v5，v4)∈ μ- ，f54=3＞0 清华大学出版社

4.1 基本概念与基本定理 4. 截集与截量 设S,T⊂V，S∩T=Ø，我们把始点在S中，终点在T中的所有弧构成的集合，记为(S，T)。 定义9 给网络D=(V，A，C)，若点集V被剖分为两个非空集合，使 ，则把弧集 称为是(分离vs和vt的)截集。 显然，若把某一截集的弧从网络中丢去，则从vs到vt便不存在路。所以，直观上说，截集是从vs到vt的必经之道。 清华大学出版社

4.2 寻求最大流的标号法 定义10 给一截集 ，把截集 中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c ，即 不难证明，任何一个可行流的流量v(f )都不会超过任一截集的容量。即 v(f )≤c 显然，若对于一个可行流f *，网络中有一个截集 ，使v(f *)c ，则f*是最大流，而 必定是D的所有截集中，容量最小的一个，即最小截集。 清华大学出版社

4.2 寻求最大流的标号法 定理8 流f *最大流，当且仅当不存在关于f *增广链。 证明 若f *是最大流，设D中存在关于f *的增广链μ，令 由增广链的定义，可知θ＞0，令 不难验证 是一个可行流，且v(f**)=v(f*)+θ＞v(f*)。这与f *是最大流的假设矛盾。 清华大学出版社

4.2 寻求最大流的标号法 现在设D中不存在关于f *的增广链，证明f *是最大流。我们利用下面的方法来定义V*1： 令vs∈V1* 若vi∈V1*，且fij＜cij，则令vj∈V1* 若vi∈V1*，且fji＞0， 则令vj∈V1* 因为不存在关于f的增广链，故 记 于是得到一个截集 显然必有 所以 。于是f必是最大流。定理得证。 清华大学出版社

4.2 寻求最大流的标号法 最大流量最小截量定理： 由上述证明中可见，若f *是最大流，则网络中必存在一个截集 ，使 于是有如下重要的结论： 任一个网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。 清华大学出版社

4.2 寻求最大流的标号法 定理8为我们提供了寻求网络中最大流的一个方法。若给了一个可行流f，只要判断D中有无关于f的增广链。如果有增广链，则可以按定理8前半部证明中的办法，改进f，得到一个流量增大的新的可行流。如果没有增广链，则得到最大流。而利用定理8后半部证明中定义V1*的办法，可以根据vt是否属于V1*来判断D中有无关于f的增广链。 实际计算时，用给顶点标号的方法来定义V1*。在标号过程中，有标号的顶点表示是V1*中的点，没有标号的点表示不是V1*中的点。一旦vt有了标号，就表明找到一条增广链；如果标号过程进行不下去，而vt尚未标号，则说明不存在增广链，于是得到最大流。而且同时也得到一个最小截集。 清华大学出版社

4.2 寻求最大流的标号法 1.标号过程 开始，先给vs标上(0，+∞)，这时vs是标号而未检查的点，其余都是未标号点。一般，取一个标号而未检查的点vi，对一切未标号点vj： (1) 若在弧(vi，vj)上，fi j＜ci j，则给vj标号(vi，l ( vj))。这里l (vj)=min［l (vi)，ci j-fi j］。这时点vj成为标号而未检查的点。 (2) 若在弧(vj，vi)上，fj i＞0，则给vj标号(-vi，l (vj))，这里l (vj)=min［l (vi)，fj i］。这时点vj成为标号而未检查的点。 于是vi成为标号而已检查过的点。重复上述步骤，一旦vt被标上号，表明得到一条从vs到vt的增广链μ，转入调整过程。 若所有标号都是已检查过的，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。 清华大学出版社

4.2 寻求最大流的标号法 2.调整过程 首先按vt及其他点的第一个标号，利用“反向追踪”的办法，找出增广链μ。例如设vt的第一个标号为vk(或-vk)，则弧(vk，vt)(或相应地(vt，vk))是μ上的弧。接下来检查vk的第一个标号，若为vi(或-vi)，则找出(vi，vk)(或相应地(vk，vi))。再检查vi的第一个标号，依此下去，直到vs为止。这时被找出的弧就构成了增广链μ。令调整量θ是l (vt)，即vt的第二个标号。令 去掉所有的标号，对新的可行流f′=｛fij′｝，重新进入标号过程。 清华大学出版社

4.2 寻求最大流的标号法 例14 用标号法求图10-25所示网络的最大流。弧旁的数是(cij，fij)。 解 (1) 标号过程 解 (1) 标号过程 ① 首先给vs标上(0，+∞) ② 检查vs，在弧(vs，v2)上，fs2=cs2=3，不满足标号条件。弧(vs，v1)上，fs1=1，cs1=5，fs1＜cs1，则v1的标号为(vs，l (v1))，其中 l (v1)=min［l (vs)，(cs1-fs1)］=min［+∞，5-1］=4 图10-25 清华大学出版社

4.2 寻求最大流的标号法 ③ 检查v1，在弧(v1，v3)上，f13=2，c13=2，不满足标号条件。 在弧(v2，v1)上，f21=1＞0，则给v2记下标号为(-v1，l (v2))，这里 l (v2)=min［l (v1)，f21］=min［4，1］=1 ④ 检查v2，在弧(v2，v4)上，f21=3，c24=4，f24＜c24，则给v4标号(v2，l (v4))，这里 l (v4)=min［l (v2)，(c24-f24)］=min［1，1］=1 在弧(v3，v2)上，f32=1＞0，给v3标号：(-v2，l (v3))，这里 l (v3）=min［l (v2)，f32］=min［1，1］=1 ⑤ 在v3，v4中任选一个进行检查。例如 在弧(v3，vt)上，f3t=1，c3t=2，f3t＜c3t，给vt标号为(v3，l (vt))，这里 l (vt)=min［l (v3)，(c3t-f3t)］=min［1，1］=1 因vt有了标号，故转入调整过程。 清华大学出版社

4.2 寻求最大流的标号法 (2) 调整过程 按点的第一个标号找到一条增广链，如图10-26中双箭头线表示。 易见 μ+=｛(vs，v1)，(v3，vt)｝ μ-=｛(v2，v1)，(v3，v2)｝ 按θ=1在μ上调整f。 μ+上：fs1+θ=1+1=2 f3t+θ=1+1=2 μ-上：f21−θ=1−1=0 f32−θ=1−1=0 其余的fij不变。 图10-26 清华大学出版社

4.2 寻求最大流的标号法 调整后得如图10-27所示的可行流，对这个可行流进入标号过程，寻找增广链。 开始给vs标以(0，+∞)，于是检查vs，给v1标以(vs,3)，检查v1，弧(v1,v3)上，f13＝c13，弧(v2,v1)上，f21=0，均不符号条件，标号过程无法继续下去，算法结束。 这时的可行流(图10-27)即为所求最大流。最大流量为 v(f)=fs1+fs2=f4t+f3t=5 与此同时可找到最小截集 ，其中V1为标号点集合， 为未标号点集合。弧集合 即为最小截集。 清华大学出版社

4.2 寻求最大流的标号法 上例中，V1＝｛vs,v1｝, ，于是 是 最小截集，它的容量也是5。 由上述可见，用标号法找增广链以求最大流的结果，同时得到一个最小截集。最小截集容量的大小影响总的输送量的提高。因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。 清华大学出版社

第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题 第10章 图与网络优化 第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题

第5节 最小费用最大流问题 网络D＝(V，A，C)，弧(vi,vj)∈A上，容量cij，单位流量的费用b(vi,vj)≥0(简记为bij)。 最小费用最大流问题:求一个最大流f，使流的总输送费用 取极小值。 要寻求最小费用的最大流，首先考查一下，当沿着一条关于可行流f的增广链μ，以θ＝1调整f，得到新的可行流f′时(显然v(f′)=v(f)+1),b(f′)比b(f)增加多少?不难看出 我们把称为这条增广链μ的“费用”。 清华大学出版社

第5节 最小费用最大流问题 可以证明，若f是流量为v(f)的所有可行流中费用最小者，而μ是关于f的所有增广链中费用最小的增广链，那么沿μ去调整f，得到的可行流f′，就是流量为v(f′)的所有可行流中的最小费用流。这样，当f′是最大流时，它也就是所要求的最小费用最大流了。 注意到，由于bij≥0，所以f=0必是流量为0的最小费用流。这样，总可以从f=0开始。一般地，设已知f是流量v(f)的最小费用流，余下的问题就是如何去寻求关于f的最小费用增广链。为此，可构造一个赋权有向图W(f)，它的顶点是原网络D的顶点，而把D中的每一条弧(vi,vj)变成两个相反方向的弧(vi,vj)和(vj,vi)。定义W(f)中弧的权wij为： (长度为+∞的弧可以从W(f)中略去) 清华大学出版社

第5节 最小费用最大流问题 可以证明，若f是流量为v(f)的所有可行流中费用最小者，而μ是关于f的所有增广链中费用最小的增广链，那么沿μ去调整f，得到的可行流f′，就是流量为v(f′)的所有可行流中的最小费用流。这样，当f′是最大流时，它也就是所要求的最小费用最大流了。 注意到，由于bij≥0，所以f=0必是流量为0的最小费用流。这样，总可以从f=0开始。一般地，设已知f是流量v(f)的最小费用流，余下的问题就是如何去寻求关于f的最小费用增广链。为此，可构造一个赋权有向图W(f)，它的顶点是原网络D的顶点，而把D中的每一条弧(vi,vj)变成两个相反方向的弧(vi,vj)和(vj,vi)。定义W(f)中弧的权wij为： (长度为+∞的弧可以从W(f)中略去) 清华大学出版社

第5节 最小费用最大流问题 于是在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中，寻求从vs到vt的最短路。因此有如下算法： 开始取f(0)=0，一般情况下若在第k −1步得到最小费用流f (k-1)，则构造赋权有向图W(f (k-1))，在W(f (k-1))中，寻求从vs到vt的最短路。若不存在最短路(即最短路权是+∞)，则f (k −1)就是最小费用最大流；若存在最短路，则在原网络D中得到相应的增广链μ，在增广链μ上对 f (k − 1)进行调整。调整量为： 令 得到新的可行流f (k)，再对f (k)重复上述步骤。 清华大学出版社

第5节 最小费用最大流问题 例15 以图10-28为例，求最小费用最大流。弧旁数字为(bij,cij)。 图10-28 清华大学出版社

第5节 最小费用最大流问题 例15 (续) 清华大学出版社

图10-29 清华大学出版社

第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题 第10章 图与网络优化 第1节 图的基本概念 第2节 树 第3节 最短路问题 第4节 网络最大流问题 第5节 最小费用最大流问题 第6节 中国邮递员问题

引言 在本章开始提到的邮递员问题，若把它抽象为图的语言，就是： 给定一个连通图，在每边ei上赋予一个非负的权w(ei)，要求一个圈(未必是简单的)，过每边至少一次，并使圈的总权最小。 这个问题是我国学者管梅谷在1962年首先提出的，因此在国际上通称为中国邮递员问题。 清华大学出版社

第6节 中国邮递员问题 6.1 一笔画问题 6.2 奇偶点图上作业法 清华大学出版社

6.1 一笔画问题 给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这条链为欧拉链。若存在一个简单圈，过每边一次，且仅一次，称这个圈为欧拉圈。一个图若有欧拉圈，则称为欧拉图。 显然，一个图若能一笔画出，这个图必是欧拉图(出发点与终止点重合)或含有欧拉链(出发点与终止点不同)。 清华大学出版社

6.1 一笔画问题 定理9 连通多重图G有欧拉圈，当且仅当G中无奇点。 证明 必要性是显然的，只证明充分性。不妨设G至少有三个点，对边数q(G)进行数学归纳，因G是连通图，不含奇点，故q(G)≥3。首先q(G)=3时，G显然是欧拉图。考查q(G)=n+1的情况，因G是不含奇点的连通图，并且p(G)≥3，故存在三个点u，v，ω，使［u,v］,［w,v］∈E。从G中丢去边［u,v ］,[ω,v ］，增加新边［u,ω］，得到新的多重图G′。G′有q(G)-1条边，并且仍不含奇点，G′至多有两个分图。若G′是连通的，那么根据归纳假设，G′有欧拉圈C′。把C′中的［ω,u ］这一条边换成［ω,v ］，［v,u ］，即得G中的欧拉圈。现设G′有两个分图G1，G2。设v在G1中。根据归纳假设，G1，G2分别有欧拉圈C1，C2，则把C2中的［u, ω］这条边换成［u,v ］，C1及[v,ω]，即得G的欧拉圈。 清华大学出版社

6.1 一笔画问题 推论 连通多重图G有欧拉链，当且仅当G恰有两个奇点。 证明 必要性是显然的。现设连通多重图G恰有两个奇点u,v。在G中增加一个新边［u,v ］(如果在G中，u,v之间就有边，那么这个新边是原有边上的重复边)，得连通多重图G′，易见G′中无奇点。由定理3，G′有欧拉圈C′，从C′中丢去增加的那个新边［u,v］，即得G中的一条联结u,v的欧拉链。 上述定理和推论为我们提供了识别一个图能否是一笔画的简单办法。如前面提到的七桥问题，因为图10-1(b)中有4个奇点。所以不能一笔画出。也就是说，七桥问题的回答是否定的。如图10-30。它有两个奇点v2和v5，因此可以从点v2开始，用一笔画到点v5终止。 图10-30 清华大学出版社

6.1 一笔画问题 现在的问题是：如果我们已经知道图G是可以一笔画的，怎么样把它一笔画出来呢?也就是说，怎么找出它的欧拉圈(这时G无奇点)或欧拉链(这时G恰有两个奇点)呢?下面简单地介绍由Fleury提供的方法。 为此，先介绍割边的概念。设e是连通图G的一个边，如果从G中丢去e，图就不连通了，则称e是图G的割边。例如，图10-10(b)中，［v1,v2］是割边；树中的每一个边都是割边。 清华大学出版社

6.1 一笔画问题 设G＝(V，E)是无奇点的连通图，以 记在第k步得到的简单链。记 ， ，以及 (开始k=0时，令 ，这里 是图G的任意一点，E0＝Ø；G0＝G)。进行第(k+1)步：在Gk中选的一条关联边 ，使 不是Gk的割边(除非是Gk的悬挂点，这时在Gk中的悬挂边选为 )令 清华大学出版社

6.1 一笔画问题 重复这个过程，直到选不到所要求的边为止。可以证明：这时的简单链必定终止于vi0，并且就是我们要求的图G的欧拉圈。 如果G＝(V，E)是恰有两个奇点的连通图。只需要取vi0是图G的一个奇点就可以了。最终得到的简单链就是图中联结两个奇点的欧拉链。 清华大学出版社

6.2 奇偶点图上作业法 根据上面的讨论，如果在某邮递员负责的范围内，街道图中没有奇点，那么他就可以从邮局出发，走过每条街道一次，且仅一次，最后回到邮局，所走的路程也就是最短路程。对于有奇点的街道图，就必须在某些街道上重复走一次或多次。 例如，图10-30的街道图中，若v1是邮局，邮递员可以按如下路线投递信件： v1→v2→v4→v3→v2→v4→v6→v5→v4→v6→v5→v3→v1，总权为12。 也可按另一条路线走： v1→v2→v3→v2→v4→v5→v6→v4→v3→v5→v3→v1，总权为11。 可见，按第一条路线走，在边［v2,v4］，［v4,v6］,［v6,v5］上各重复走了一次。而按第二条路线走，在边［v3,v2］,［v3,v5］上各重复走了一次。 如果在某条路线中，边［vi，vj］上重复走了几次，我们在图中vi，vj之间增加几条边，令每条边的权和原来的权相等，并把新增加的边称为重复边。于是这条路线就是相应的新图中的欧拉圈。例如在图10-30中，上面提到的两条投递路线分别是图10-31(a)和(b)中的欧拉圈。 清华大学出版社

6.2 奇偶点图上作业法 显然，两条邮递路线的总权的差必等于相应的重复边总权的差。因而，中国邮递员问题可以叙述为：在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最小。 我们把使新图不含奇点而增加的重复边，简称为可行(重复边)方案，使总权最小的可行方案称为最优方案。现在的问题是第一个可行方案如何确定，在确定一个可行方案后，怎么判断这个方案是否为最优方案?若不是最优方案，如何调整这个方案? 图10-31 清华大学出版社

6.2 奇偶点图上作业法 1.第一个可行方案的确定方法 在第1节中，我们已经证明，在任何一个图中，奇点个数必为偶数。所以如果图中有奇点，就可以把它们配成对。又因为图是连通的，故每一对奇点之间必有一条链，我们把这条链的所有边作为重复边加到图中去，可见新图中必无奇点，这就给出了第一个可行方案。 清华大学出版社

6.2 奇偶点图上作业法 清华大学出版社

6.2 奇偶点图上作业法 2w12+w23+w34+2w45+2w56+w67+w78+2w18=51 图10-33 图10-32 在图10-33中，没有奇点，对应于这个可行方案，重复边总权为： 2w12+w23+w34+2w45+2w56+w67+w78+2w18=51 清华大学出版社

6.2 奇偶点图上作业法 因而有： (1) 在最优方案中，图的每一边上最多有一条重复边。 依此，图10-33可以调整为图10-34，重复边总权下降为21。 其次，我们还可以看到，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边加上重复边，图中仍没有奇点。因而如果在某个圈上重复边的总权大于这个圈的总权的一半，像上面所说的那样作一次调整，将会得到一个总权下降的可行方案。 清华大学出版社

6.2 奇偶点图上作业法 图10-34 图10-35 清华大学出版社

6.2 奇偶点图上作业法 3.判断最优方案的标准 从上面的分析中可知，一个最优方案一定是满足(1)和(2)的可行方案，反之，可以证明一个可行方案若满足(1)和(2)，则这个可行方案一定是最优方案。根据这样的判断标准，对给定的可行方案，检查它是否满足条件(1)和(2)。若满足，所得方案即为最优方案；若不满足，则对方案进行调整，直至条件(1)和(2)均得到满足时为止。 检查图10-35中的圈(v1，v2，v9，v6，v7，v8，v1)，它的重复边总权为13，而圈的总权为24,不满足条件(2)，经调整得图10-36。重复边总权下降为15。 清华大学出版社

6.2 奇偶点图上作业法 图10-36 检查图10-36，条件(1)和(2)均满足。于是得最优方案，图10-36中的任一个欧拉圈就是邮递员的最优邮递路线。 以上所说的求最优邮递路线的方法，通常称为奇偶点图上作业法。值得注意的是，方法的主要困难在于检查条件(2)，它要求检查每一个圈。当图中点、边数较多时，圈的个数将会很多。如“日”字形图就有三个圈，而“田”字形的图就有13个圈。关于中国邮递员问题，已有比较好的算法，我们不去介绍它了。 清华大学出版社

注记 中国邮递员问题的改进算法是Edmonds给出的。其算法涉及图的对集(matching)问题。 网络优化是一类组合优化问题。网络优化中，一个有名的问题是所谓旅行推销员问题(Traveling Salesman Problem)(也称为货郎担问题)：一个推销员要到若干个城市推销产品，然后回到出发点。已知每两个城市之间的距离，他应如何选择其旅行路线，使每个城市经过一次且仅仅一次，并且总的行程最短?表面上看，这个问题与中国邮递员问题很相似，但实际上，这是一个非常困难的问题，至今没有一个求最优旅行路线的有效方法。 清华大学出版社