qq网名个性网-配衣服

可编辑
第五章 图与网络模型及方法

§1 概论
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼
斯堡的七座桥”。 1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857
年，凯莱在计数烷
C
n
H
2n2
的同分异构物时，也发现了“树”。哈密尔顿于1859年提
出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年
来，由于 计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和
方法已经渗透到物理、化学 、通讯科学、建筑学、生物遗传学、心理学、经济学、社会
学等学科中。
图论中所谓的“图” 是指某类具体事物和这些事物之间的联系。如果我们用点表示
这些具体事物，用连接两点的线段（直的或 曲的）表示两个事物的特定的联系，就得到
了描述这个“图”的几何形象。图论为任何一个包含了一种二 元关系的离散系统提供了
一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡 七桥问
题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结
起 来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当

然可以通 过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决
这个问题，采用了建立数学 模型的方法。他将每一块陆地用一个点来代替，将每一座桥
用连接相应两点的一条线来代替，从而得到一 个有四个“点”，七条“线”的“图”。问
题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了 一般一笔画的结构特点，
给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联， 将这个
判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，
而 且开创了图论研究的先河。
图与网络是运筹学（Operations Research）中的一个 经典和重要的分支，所研
究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与 网络技
术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题
等 都是图与网络的基本问题。
我们首先通过一些例子来了解网络优化问题。
例1 最短路问题（SPP－shortest path problem）
一名货柜车司机奉命在最短的 时间内将一车货物从甲地运往乙地。从甲地到乙地的
公路网纵横交错，因此有多种行车路线，这名司机应 选择哪条线路呢？假设货柜车的运
精品文档

可编辑
行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。
例2 公路连接问题
某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其
中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
个城市之间修建 高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总
成本最小？
例3 指派问题（assignment problem）
一家公司经理准备安排
N
名员 工去完成
N
项任务，每人一项。由于各员工的特点
不同，不同的员工去完成同一项任务 时所获得的回报是不同的。如何分配工作方案可以
使总回报最大？
例4 中国邮递员问题（CPP－chinese postman problem）
一名邮递员负责投递 某个街区的邮件。如何为他（她）设计一条最短的投递路线（从
邮局出发，经过投递区内每条街道至少一 次，最后返回邮局）？由于这一问题是我国管
梅谷教授1960年首先提出的，所以国际上称之为中国邮 递员问题。
例5 旅行商问题（TSP－traveling salesman problem）
一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线< br>（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠
久，通常称 之为旅行商问题。
例6 运输问题（transportation problem）
某种原材料有
M
个产地，现在需要将原材料从产地运往
N
个使用这些原材料的 工
厂。假定
M
个产地的产量和
N
家工厂的需要量已知，单位产品从任 一产地到任一工厂
的运费已知，那么如何安排运输方案可以使总运输成本最低？
上述问题有两 个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求
某种意义下的最优安排或方案，数学 上把这种问题称为最优化或优化（optimization）
问题；二是它们都易于用图形的形式直观 地描述和表达，数学上把这种与图相关的结构
称为网络（network）。与图和网络相关的最优化问 题就是网络最优化或称网络优化
（netwok optimization）问题。所以上面例子中 介绍的问题都是网络优化问题。由于
多数网络优化问题是以网络上的流（flow）为研究的对象，因此 网络优化又常常被称为
网络流（network flows）或网络流规划等。
下面首先简要介绍图与网络的一些基本概念。

§2 图与网络的基本概念
2.1 无向图
一个无向图(undirected graph)
G
是由 一个非空有限集合
V(G)
和
V(G)
中某些
元素的无序对集合E(G)
构成的二元组，记为
G(V(G),E(G))
。其中
V(G ){v
1
,v
2
,,v
n
}
称为图
G
的顶点集（vertex set）或节点集（node set），
V(G)
中的 每一个元素
v
i
(i

1,2,

,n)
称为该图的一个顶点（vertex）或节点（node）；
E(G){e
1
,e< br>2
,,e
m
}
称为图
G
的边集（edge set），
E(G)
中的每一个元素
e
k
(即
精品文档

可编辑
V(G)
中某两个元素
v
i
,v
j
的无序对) 记 为
e
k
(v
i
,v
j
)
或
e< br>k
v
i
v
j
v
j
v
i

。
(k1,2,,m)
，被称为该图的一条从
v
i
到
v
j
的边（edge）
当边
e
k
v
i< br>v
j
时，称
v
i
,v
j
为边
ek
的端点，并称
v
j
与
v
i
相邻（adjac ent）；边
e
k
称
为与顶点
v
i
,v
j
关联（incident）。如果某两条边至少有一个公共端点，则称这两条边
在图
G
中相邻。
边上赋权的无向图称为赋权无向图或无向网络（undirected network）。我们对
图和网络不作严格区分，因为任何图总是可以赋权的。
一个图称为 有限图，如果它的顶点集和边集都有限。图
G
的顶点数用符号
|V|
或

(G)
表示，边数用
|E|
或

(G)
表示。
当讨论的图只有一个时，总是用
G
来表示这个图。从而在图论符号中我们常略去
字母
G
，例如，分别用
V,E,

和

代替V(G),E(G),

(G)
和

(G)
。
端点重合为一点的边称为环(loop)。
一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶
点。
2.2 有向图
定义 一个有向图（directed graph或 digraph）
G
是由一 个非空有限集合
V
和
V
中某些元素的有序对集合
A
构成的二 元组，记为
G(V,A)
。其中
V{v
1
,v
2
,,v
n
}
称为图
G
的顶点集或节点集，
V
中的每一个元素
v
i
(i

1,2,

,n)称为该图的一个顶点或节点；
A
{
a
1
,
a
2
,

,
a
m
}
称为图
G
的弧集 （arc set），
A
中的
每一个元素
a
k
(即
V
中某两个元素
v
i
,v
j
的有序对) 记为
a< br>k
(v
i
,v
j
)
或
a
k

v
i
v
j
(k

1,2,

,n)
，被称为该图的一条从
v
i
到
v
j
的弧（a rc）。
当弧
a
k
v
i
v
j
时，称< br>v
i
为
a
k
的尾（tail），
v
j
为
a
k
的头（head），并称弧
a
k
为
vi
的出弧（outgoing arc），为
v
j
的入弧（incoming arc）。
对应于每个有向 图
D
，可以在相同顶点集上作一个图
G
，使得对于
D
的每条 弧，
这个图称为
D
的基础图。反之，给定任意图
G
，
G有一条有相同端点的边与之相对应。
对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由 此得到一个有向图，这
样的有向图称为
G
的一个定向图。
以下若未指明“有向图”三字，“图”字皆指无向图。
2.3 完全图、二分图
每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。
n
个
顶点的完全图记为
K
n
。
若
V(G)XY
，
XY
，
|X||Y|0
（这里
|X|
表示集合
X
中的元素个
数），
X
中无相邻顶 点对，
Y
中亦然，则称
G
为二分图(bipartite graph)；特 别地，
若
xX,yY
，则
xyE(G)
，则称
G
为完全二分图，记成
K
|X|,|Y|
。
2.4 子图
图
H
叫做图
G
的子图（subgraph），记作
HG
，如果
V(H)V(G)
，
精品文档

可编辑
E (H)E(G)
。若
H
是
G
的子图，则
G
称为< br>H
的母图。
（spanning subgraph，又成生成子图）是指满足
V(H)V(G)
的
G
的支撑子图
子图
H
。
2.5 顶点的度
设
vV(G)
，
G
中与
v< br>关联的边数（每个环算作两条边）称为
v
的度(degree)，
记作
d(v)
。若
d(v)
是奇数，称
v
是奇顶点(odd point)；
d(v)
是偶数，称
v
是偶顶点
(even point)。关于顶点的度，我们有如下结果：
(i)

d(v)2


vV
(ii) 任意一个图的奇顶点的个数是偶数。
2.6 图与网络的数据结构
网络优化研究的是网络上 的各种优化模型与算法．为了在计算机上实现网络优化的
算法，首先我们必须有一种方法（即数据结构） 在计算机上来描述图与网络。一般来说，
算法的好坏与网络的具体表示方法，以及中间结果的操作方案是 有关系的。这里我们介
绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表 示
法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假
设G(V,A)
是一个简单有向图，
|V|n,|A|m
，并假设
V
中的顶点用自然数
1,2,,n
表示或编号，
A
中的弧用自然数< br>1,2,,m
表示或编号。对于有多重边或无向
网络的情况，我们只是在讨论完简单有 向图的表示方法之后，给出一些说明。
（i）邻接矩阵表示法
邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图
G(V,A)
的邻接矩阵是如下定义的：
C
是一个
nn< br>的
01
矩阵，即

C(c
ij
)
nn
{0,1}

c
ij


nn
，

1,(i,j)A,

0,(i,j)A.

2< br>也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。
可以看出，这种 表示法非常简单、直接。但是，在邻接矩阵的所有
n
个元素中，只有
m
个为非 零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络
中查找弧的时间。
例7 对于右图所示的图，可以用邻接矩阵表示为
同样，对于网络中的权，也可以用类似邻 接矩阵的
nn
矩阵表示。只是此时一条
弧所对应的元素不再是1，而是相应的权而已 。如果网络中每条弧赋有多种权，则可以
精品文档

0

0


0


0


0
1100

0010


1000



0101

0110



可编辑
用多个矩阵表示这些权。
（ii）关联矩阵表示法
关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机
中．图
G(V,A)
的关联矩阵
B
是如下定义的：
B
是一 个
nm
的矩阵，即
nm

B(b
ik
)
nm
{1,0,1}
，

1,jV,k(i,j)A,


b
ik


1, jV,k(j,i)A,

0,
其它
.


也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如
果一个节点是一条弧 的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的
终点，则关联矩阵中对应的元素为1
；如果一个节点与一条弧不关联，则关联矩阵中
对应的元素为0。对于简单图，关联矩 阵每列只含有两个非零元（一个
1
，一个
1
）。
可以看出，这种 表示法也非常简单、直接。但是，在关联矩阵的所有
nm
个元素中，只
有
2m
个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于
关联矩阵有许多 特别重要的理论性质，因此它在网络优化中是非常重要的概念。
例8 对于例7所示的图，如果关联 矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，
(3,2)，(4,3)，(4,5 )，(5,3)和(5,4)，则关联矩阵表示为

11000000


10110000



01011010



00101101



00000 111


同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如 果网络中
每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的
行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条
弧所对应的权存储 在增加的行中。
（iii）弧表示法
弧表表示法将图以弧表（arc list）的形式存 储在计算机中。所谓图的弧表，也就
是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和 终点，共需
2m
个
存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每 条弧上的权，也要
对应地用额外的存储单元表示。例如，例7所示的图，假设弧(1,2)，(1,3) ，(2,4)，(3,2)，
(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9， 6，4，0，3，6和7，则弧表表示如
下：
起点
终点
权

精品文档
1
2
8
1
3
9
2
4
6
3
2
4
4
3
0
4
5
3
5
3
6
5
4
7

可编辑
为了便于检索，一般按照起点、终点的字典序顺序存储弧 表，如上面的弧表就是按
照这样的顺序存储的。
（iv）邻接表表示法
邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的
所有出弧。邻 接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所
有弧，链表中每个单元对应于一 条出弧。为了记录弧上的权，链表中每个单元除列出弧
的另一个端点外，还可以包含弧上的权等作为数据 域。图的整个邻接表可以用一个指针
数组表示。例如，例7所示的图，邻接表表示为

这是一个5维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻
接表，如第1行对应于 第1个节点的邻接表（即第1个节点的所有出弧）。每个指针单
元的第1个数据域表示弧的另一个端点（ 弧的头），后面的数据域表示对应弧上的权。
如第1行中的“2”表示弧的另一个端点为2（即弧为（1 ,2）），“8”表示对应弧(1,2)
上的权为8；“3”表示弧的另一个端点为3（即弧为(1,3 )），“9”表示对应弧（1，3）
上的权为9。又如，第5行说明节点5出发的弧有(5,3)、(5 ,4)，他们对应的权分别为
6和7。
对于有向图
G(V,A)
，一般用
A(i)
表示节点
i
的邻接表，即节点
i
的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子，
A(1){2 ,3}
，
A(5){3,4}
等。这种记法我们在本书后面将会经常用到。
（v）星形表示法
星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。 对每个节点，
它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2
出发的所有孤， 依此类推，最后存放从节点
n
出发的所有孤。对每条弧，要依次存放其
起点、终点、权 的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，
只是从同一节点出发的弧的顺序可 以任意排列。此外，为了能够快速检索从每个节点出
发的所有弧，我们一般还用一个数组记录每个节点出 发的弧的起始地址（即弧的编号）。
在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形 表示法称为前向星
形（forward star）表示法。
例如，在例7所示的图中，仍然 假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），
（5,3）和（ 5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前
向星形表示法表示如下 ：
精品文档

可编辑
节点对应的出弧的起始地址编号数组（记为
point
）
节点号
i

起始地址
point(i)


记录弧信息的数组
弧编号
起点
终点
权

1
1
2
8
2
1
3
9
3
2
4
6
4
3
2
4
5
4
3
0
6
4
5
3
7
5
3
6
8
5
4
7
1
1
2
3
3
4
4
6
5
7
6
9
在数组
point
中，其元素个 数比图的节点数多1（即
n1
），且一定有
point(1)1
，
point(n1)m1
。对于节点
i
，其对应的出弧存放在弧信息数组的位 置区间为
[point(i),point(i1)1]
，
如果
po int(i)point(i1)
，则节点
i
没有出弧。这种表示法与弧表表示法 也非常相
似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（
point
）记录每个节点出发的弧的起始编号。
前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的
所有入弧。为 了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）
表示法：首先存 放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类
推，最后存放进入节点
n< br>的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值
等有关信息。同样，为了能够快速检 索从每个节点的所有入弧，我们一般还用一个数组
记录每个节点的入孤的起始地址（即弧的编号）。例如 ，例7所示的图，可以用反向星
形表示法表示为如下形式：
节点对应的入弧的起始地址编号数组（记为
rpoint
）
节点号
i

起始地址
rpoint(i)


记录弧信息的数组
弧编号
终点
起点
权

如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧，
则可以综合采用前向和 反向星形表示法。当然，将孤信息存放两次是没有必要的，可以
只用一个数组（trace）记录一条弧 在两种表示法中的对应关系即可。例如，可以在采
用前向星形表示法的基础上，加上上面介绍的
rpoint
数组和如下的
trace
数组即可。这
相当于一种紧凑的双向星 形表示法如下所示：
两种表示法中的弧的对应关系（记为
trace
）
精品文档
1
1
2
1
3
3
4
6
5
8
6
9
1
2
3
4
2
2
1
8
3
3
1
9
4
3
4
0
5
3
5
6
6
4
5
7
7
4
2
6
8
5
4
3

可编辑
反向法中弧编号
j
1 2 3 4 5 6 7 8
正向法中弧编号
trace(j)
4 1 2 5 7 8 3 6

对于网络图的表示法，我们作如下说明：
① 星形表示法和邻接表表示法在实际算法实现中都 是经常采用的。星形表示法的
优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FO RTRAN语言
等）也容易实现。邻接表表示法对那些提供指针类型的语言（如C语言等）是方便的，< br>且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工
作量较大（ 需要花费
O(m)
的计算时间）。有关“计算时间”的观念是网络优化中需要
考虑的一 个关键因素。
② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示
法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。
③ 上述方法可以很方便 地推广到可以处理无向图的情形，但由于无向图中边没有
方向，因此可能需要做一些自然的修改。例如， 可以在计算机中只存储邻接矩阵的一半
信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的 关联矩阵只含有元素
0和
1
，而不含有
1
，因为此时不区分边的 起点和终点。又如，在邻接表和星形表
示法中，每条边会被存储两次，而且反向星形表示显然是没有必要 的，等等。
2.7 轨与连通
Wv
0
e
1
v
1
e
2
e
k
v
k
，其中
e
i
E(G)
，
1ik
，
v
j
V(G)
，
0jk
，
e
i
与
v
i1
,v< br>i
关联，称
W
是图
G
的一条道路(walk)，
k< br>为路长，顶点
v
0
和
v
k
分别称为
W
的
起点和终点，而
v
1
,v
2
,,v
k1< br>称为它的内部顶点。
若道路
W
的边互不相同，则
W
称为迹( trail)。若道路
W
的顶点互不相同，则
W
称
为轨(path) 。
称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做
圈(cy cle)。
若图
G
的两个顶点
u,v
间存在道路，则称
u
和
v
连通(connected)。
u,v
间的最短
轨的长 叫做
u,v
间的距离。记作
d(u,v)
。若图
G
的任二顶 点均连通，则称
G
是连通图。
显然有：
(i) 图
P
是 一条轨的充要条件是
P
是连通的，且有两个一度的顶点，其余顶点的度
为2；
(ii) 图
C
是一个圈的充要条件是
C
是各顶点的度均为2的连通图。

§3 应用—最短路问题
3.1 两个指定顶点之间的最短路径
问题如下：给出了 一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，
找一条最短铁路线。
以各城 镇为图
G
的顶点，两城镇间的直通铁路为图
G
相应两顶点间的边，得图
G
。
对
G
的每一边
e
，赋以一个实数
w(e)< br>—直通铁路的长度，称为
e
的权，得到赋权图
G
。
精品文档

可编辑
G
的子图的权是指子图的各边的权和。问题就是求赋权图G
中指定的两个顶点
u
0
,v
0
间的具最小权的轨。这 条轨叫做
u
0
,v
0
间的最短路，它的权叫做
u
0
,v
0
间的距离，亦记
作
d
(
u
0
,
v
0
)
。
求最短路已有成熟的算法：迪克斯特拉（Dijks tra）算法，其基本思想是按距
u
0
从
近到远为顺序，依次求得
u
0
到
G
的各顶点的最短路和距离，直至
v
0
（或直 至
G
的所有
顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法 。下面是该
算法。
(i) 令
l
(
u
0
)

0
，对
vu
0
，令
l(v)
，
S
0
{u
0
}
，
i0
。
(ii) 对每个
vS
i
（
S
i
VS
i
），用
min{l(v),l(u)w(uv)}

uS
i
代替
l(v)
。计算
min{l(v)}
，把达到这个最小值的一个顶点记为
u
i1
，令
vS
i
S
i1
S
i{u
i1
}
。
(iii). 若
i|V|1
，停止；若
i|V|1
，用
i1
代替
i
，转(ii) 。
算法结束时，从
u
0
到各顶点
v
的距离由
v< br>的最后一次的标号
l(v)
给出。在
v
进入
S
i之前的标号
l(v)
叫T标号，
v
进入
S
i
时 的标号
l(v)
叫P标号。算法就是不断修改各项
点的T标号，直至获得P标号。若在 算法运行过程中，将每一顶点获得P标号所由来
的边在图上标明，则算法结束时，
u
0
至各项点的最短路也在图上标示出来了。
例9 某公司在六个城市
c
1< br>,c
2
,,c
6
中有分公司，从
c
i
到< br>c
j
的直接航程票价记在
下述矩阵的
(i,j)
位置上。（< br>
表示无直接航路），请帮助该公司设计一张城市
c
1
到其它
城市间的票价最便宜的路线图。

050402510


50 0152025



1501020



4


252010055


102525550

index
1
、
index
2
、
用矩阵
a
nn
（
n
为顶点个数）存 放各边权的邻接矩阵，行向量
pb
、
d
分别用来存放
P
标号 信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分
量

1
当第
i
顶点已标号
；
pb(i)

0
当第
i
顶点未标号

index
2
( i)
存放始点到第
i
点最短通路中第
i
顶点前一顶点的序号；
d(i)
存放由始点到第
i
点最短通路的值。
求第一个城市到其它城市的最短路径的Matlab程序如下：
精品文档

可编辑
clear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';
pb(1:length(a))=0;pb(1)=1;index1=1 ;index2=ones(1,length(a));
d(1:length(a))=M;d(1)=0;temp=1;
while sum(pb) tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb));
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp];
index=index1(find(d(i ndex1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index;
end
d, index1, index2

3.2 每对顶点之间的最短路径
计算赋权 图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：
每次以不同的顶点作为 起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，
反复执行
n
次这 样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的
时间复杂度为
O
(
n
)
。第二种解决这一问题的方法是由Floyd R W提出的算法，称之
3
为Floyd算法。
假设图
G
权的邻接矩阵为
A
0
，

a< br>11

a
A
0


21




a
n1
a
12
a
22
< br>a
n2

a
1n


a
2n







a
nn

精品文档

可编辑
来存放各边长度，其中：
a
ii
0

i1,2,,n
；
a
ij


i,j
之间没有边，在程序中以各边都不可能达到的充分大的数代替；
a
ij
w
ij

w
ij
是
i ,j
之间边的长度，
i,j1,2,,n
。
对于无向图，
A< br>0
是对称矩阵，
a
ij
a
ji
。
Flo yd算法的基本思想是：递推产生一个矩阵序列
A
0
,A
1
,

,A
k
,

,A
n
，其中
A
k
(i,j)
表示从顶点
v
i
到顶点
v
j
的路径上所经过的顶点序号不大于
k
的最短路径长
度。
计算时用迭代公式：
A
k
(i,j)min(A
k1
(i,j),A
k1
(i,k)A
k1
(k,j))

k
是迭代次数，
i,j,k1,2,,n
。
最后，当
kn
时，
A
n
即是各顶点之间的最短通路值。
例10 用Floyd算法求解例1。
矩阵path用来存放每对顶点之间最短路径上所经过 的顶点的序号。Floyd算法的
Matlab程序如下：
clear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
for k=1:6
for i=1:6
for j=1:6
if b(i,j)>b(i,k)+b(k,j)
b(i,j)=b(i,k)+b(k,j);
path(i,j)=k;
end
end
end
end
b, path

精品文档

可编辑
§4 树
4.1 基本概念
连通的无圈图叫做树，记之为
T
。若图
G
满足
V(G)V(T)
，
E(T)E(G)
，
则称
T
是
G
的生成树。图
G
连通的充分必要条件为
G
有生 成树。一个连通图的生成树
的个数很多，用

(G)
表示
G
的生成树的个数，则有公式
公式 (Caylay)

(K
n
)n
n2
。
公式

(G)

(Ge)

(Ge)
。 其中
Ge
表示从
G
上删除边
e
，
Ge表示把
e
的长度收缩为零得到的图。
树有下面常用的五个充要条件。
定理1 （i）
G
是树当且仅当
G
中任二顶点之间有且仅有一条轨道。
（i i）
G
是树当且仅当
G
无圈，且



 1
。
（iii）
G
是树当且仅当
G
连通，且
< br>

1
。
（iv）
G
是树当且仅当
G< br>连通，且
eE(G)
，
Ge
不连通。
（v）
G
是树当且仅当
G
无圈，
eE(G)
，
Ge
恰有一个圈。
4.2 应用—连线问题
欲修筑连接
n
个城市的铁路，已知
i
城与
j
城之间的铁路造价为
C
ij
，设计一个线
路图，使总造价最低。
连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具 有最小权的
生成树叫做最小生成树。
下面介绍构造最小生成树的两种常用算法。
4.2.1 prim算法构造最小生成树
设置两个集合
P
和
Q< br>,其中
P
用于存放
G
的最小生成树中的顶点，集合
Q
存放
G
的最小生成树中的边。令集合
P
的初值为
P
{v
1
}
（假设构造最小生成树时，从顶点
v
1
出发）， 集合
Q
的初值为
Q
。prim算法的思想是，从所有
pP，
vVP
的边
中，选取具有最小权值的边
pv
，将顶点v
加入集合
P
中，将边
pv
加入集合
Q
中，如
此不断重复，直到
PV
时，最小生成树构造完毕，这时集合
Q
中包 含了最小生成树
的所有边。
prim算法如下：
（i）
P
{
v
1
}
，
Q
；
（ii）while
P~V


PP{v}


QQ{pv}

end

例11 用prim算法求右图的最小生成树。
我们用
resu lt
3n
的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab
精品文档

pv

min(w
pv
,p

P,v

V

P}

可编辑
程序如下：
clc;clear;
M=1000;
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=[a;zeros(2,7)];
a=a+a';a(find(a==0))=M;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));k=tb(kb(1));
result=[result,[j;k ;d]];p=[p,k];tb(find(tb==k))=[];
end
result

4.2.1 Kruskal算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法如下:
(i)选e
1
E
(
G
)
，使得
w(e
1)min
。
(ii)若
e
1
,e
2
,
,e
i
已选好，则从
E
(
G
)
< br>{
e
1
,
e
2
,

,
e< br>i
}
中选取
e
i1
，使得
①
G
[{
e
1
,
e
2
,

,
ei
,
e
i1
}]
中无圈，且
②
w
(
e
i1
)

min
。
(iii)直到选得
e

1
为止。

例12 用Kruskal算法构造例3的最小生成树。
我们用
index
2n
存 放各边端点的信息，当选中某一边之后，就将此边对应的顶点序
号中较大序号
u
改记为 此边的另一序号
v
，同时把后面边中所有序号为
u
的改记为
v
。
此方法的几何意义是：将序号
u
的这个顶点收缩到
v
顶点，u
顶点不复存在。后面继续
寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失 去了被选取的资格。
Matlab程序如下：
clc;clear;
M=1000;
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
精品文档

可编辑
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
[i,j]=find((a~=0)&(a~=M));
b=a(find((a~=0)&(a~=M)));
data=[i';j';b'];index=data(1:2,:);
loop=max(size(a))-1;
result=[];
while length(result) temp=min(data(3,:));
flag=find(data(3,:)==temp);
flag=flag(1);
v1=data(1,flag);v2=data(2,flag);
if index(1,flag)~=index(2,flag)
result=[result,data(:,flag)];
end
if v1>v2
index(find(index==v1))=v2;
else
index(find(index==v2))=v1;
end
data(:,flag)=[];
index(:,flag)=[];
end
result

§5 匹配问题
定义 若
ME(G)
，

e
i
,< br>e
j

M
，
e
i
与
e
j< br>无公共端点（
ij
），则称
M
为图
G
的一个对集；
M
中的一条边的两个端点叫做在对集
M
中相配；
M
中的端点 称为被
M
许配；
G
中每个顶点皆被
M
许配时，
M< br>称为完美对集；
G
中已无使
|M'||M|
的
对集
M'
，则
M
称为最大对集；若
G
中有一轨，其边交替地在对集
M
内外出现，则称
此轨为
M
的交错轨，交错轨的起止顶点都未被许配时，此 交错轨称为可增广轨。
若把可增广轨上在
M
外的边纳入对集，把
M
内的边从对集中删除，则被许配的
顶点数增加2，对集中的“对儿”增加一个。
1957年，贝尔热(Berge)得到最大对集的充要条件：
定理2
M
是图
G
中的最大对集当且仅当
G
中无
M
可增广轨。
1935年，霍尔(Hall)得到下面的许配定理：
定理3
G
为二分 图，
X
与
Y
是顶点集的划分，
G
中存在把
X
中顶点皆许配的
对集的充要条件是，
SX
，则
|N(S)||S|< br>，其中
N(S)
是
S
中顶点的邻集。
精品文档

可编辑
由上述定理可以得出：
推论1：若
G
是< br>k
（
k0)
正则2分图，则
G
有完美对集。
所谓
k
正则图，即每顶点皆
k
度的图。
由此推论得出下面的婚配定理：
定理4 每个姑娘都结识
k(k1)
位 小伙子，每个小伙子都结识
k
位姑娘，则每位
姑娘都能和她认识的一个小伙子结婚，并 且每位小伙子也能和他认识的一个姑娘结婚。
人员分派问题等实际问题可以化成对集来解决。
人员分派问题：工作人员
x
1
,x
2
,

,x< br>n
去做
n
件工作
y
1
,y
2
,
,y
n
，每人适合做其
中一件或几件，问能否每人都有一份适合的工作 ？如果不能，最多几人可以有适合的工
作？
这个问题的数学模型是：
G
是二 分图，顶点集划分为
V(G)XY
，
X
1
{x
1,,x
n
}
，
Y
1
{y
1
,, y
n
}
，当且仅当
x
i
适合做工作
y
i< br>时，
x
i
y
i
E(G)
，求
G
中 的最大对集。
解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。
匈牙利算法：
（i）从
G
中任意取定一个初始对集
M
。
（ii）若
M
把
X
中的顶点皆许配，停止，
M
即完 美对集；否则取
X
中未被
M
许
配的一顶点
u
，记< br>S{u}
，
T
。
（iii）若
N(S)T
，停止，无完美对集；否则取
yN(S)T
。
（iv）若
y
是 被
M
许配的，设
yzM
，
SS{z}
，
T T{y}
，转（iii）；
否则，取可增广轨
P(u,y)
，令
M (ME(P))(E(P)M)
，转（ii）。
把以上算法稍加修改就能够用来求二分图的最大对集。
最优分派问题：在人员分派问题中，工 作人员适合做的各项工作当中，效益未必一
致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图
G
的每边加了权
w(xi
y
j
)0
，表示
x
i
干
y
j
工作的效益，求加权图
G
上的权最大的完美对集。
解决这个问题可以用库恩—曼克莱斯（Kuhn- Munkres）算法。为此，我们要引
入可行顶点标号与相等子图的概念。
定义 若映射
l:V(G)R
，满足
xX,yY
，

l(x)l(y)w(x,y)
，
则称
l
是二分图
G
的可行顶点标号。令
E
l
{xy|xyE(G),l(x)l(y)w(xy)}
， < br>称以
E
l
为边集的
G
的生成子图为相等子图，记作
G
l
。
可行顶点标号是存在的。例如

l(x)< br>
maxw(xy),
yY
x

X;

yY
。
精品文档

l(y)0,
定理5
G
l
的完美对集即为
G
的权最大的完美对集。

可编辑
Kuhn-Munkres算法
（i）选定初始可行顶点标 号
l
，确定
G
l
，在
G
l
中选取一个对集
M
。
（ii）若
X
中顶点皆被
M
许配，停止，< br>M
即
G
的权最大的完美对集；否则，取
G
l
中未被< br>M
许配的顶点
u
，令
S{u}
，
T
。
(iii)若
N
G
l
(
S)
T
，转（iv）；若
N
G
l
(S)T
， 取


l

min{
l
(
x
)
l
(
y
)
w
(
xy
)}
，
xS,yT

l(v)

l
,vS

l(v)

l(v)

l
,vT
，

l(v),
其它


ll
，
G
l
G
l
。
（iv）选
N
G
l
(
S
)
T
中一顶点
y
，若
y
已被
M
许配，且
yxM
，则
SS{z}
，
；否则，取
G
l
中一个
M
可增广轨
P(u,y)
， 令
TT{y}
，转（iii）
M(ME(P))(E(P)M)
，
转（ii）。
其中
N
G
l
(S)
是
G< br>l
中
S
的相邻顶点集。

§6 Euler图和Hamilton图
6.1 基本概念
定义 经过
G
的每条边的迹叫做
G
的Euler迹；闭的Euler迹叫做Euler回路或
E回路；含Euler回路的图叫做Euler图。
直观地讲，Euler图就是从一顶点出发每边 恰通过一次能回到出发点的那种图，即
不重复地行遍所有的边再回到出发点。
定理7 （i）
G
是Euler图的充分必要条件是
G
连通且每顶点皆偶次。
（ii）
G
是Euler图的充分必要条件是
G
连通且
G

C
i1
d
i
，
C
i
是圈，
E(C
i
)E(C
j
)(ij)
。
（iii）< br>G
中有Euler迹的充要条件是
G
连通且至多有两个奇次点。
定义 包含
G
的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或
H
圈；含Hamilton圈的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种
图，即不重 复地行遍所有的顶点再回到出发点。
6.2 Euler回路的Fleury算法
1921年，Fleury给出下面的求Euler回路的算法。
Fleury算法：
1
o
.
v
0
V
(
G
)，令
W
0
v
0
。
2
o
. 假设迹
W
i
v
0
e
1
v
1
e
i
v
i
已经选定，那么按下述方法从
E{e
1
,,e
i
}
中选取
精品文档

可编辑
边
e
i1
：
（i）
e
i1
和
v
i
相关联；
（ii ）除非没有别的边可选择，否则
e
i1
不是
G
i
G{ e
1
,,e
i
}
的割边(cut edge)。
(所谓割边是一条删除后使连通图不再连通的边)。
3
o
. 当第2步不能再执行时，算法停止。
6.3 应用
6.3.1 邮递员问题
中国邮递员问题
一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投 递的
每条街道至少一次，为他设计一条投递路线，使得他行程最短。
上述中国邮递员问题的数 学模型是：在一个赋权连通图上求一个含所有边的回路，
且使此回路的权最小。
显然，若此连 通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即
为所求。
对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：
设
G
是连通赋权图。
（i）求
V
0

{
v
|
vV
(
G
),
d
(
v)

1(mod2)}
。
（ii）对每对顶点
u,vV0
，求
d(u,v)
（
d(u,v)
是
u
与< br>v
的距离，可用Floyd算
法求得）。
（iii）构造完全赋权图
K
|V
0
|
，以
V
0
为顶点集，以
d(u ,v)
为边
uv
的权。
（iv）求
K
|V
0|
中权之和最小的完美对集
M
。
（v）求
M
中边的端点之间的在
G
中的最短轨。
（vi） 在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端
点共权的边）。
（vii）在（vi）中得的图
G'
上求Euler回路即为中国邮递员问题的解。
多邮递员问题：
邮局有
k(k2)
位投递员，同时投递信件，全城街道都 要投递，完成任务返回邮
局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成k PP。
kPP的数学模型如下：
G(V,E)
是连通图，
v
0< br>V(G)
，求
G
的回路
C
1
,

,C
k
，使得
（i）
v
0
V
(
Ci
)
，
i1,2,,k
，
（ii）
max
1ik
k
eE(C
i
)

w
(
e
)

min
，
i
（iii）

E(C)E(G)

i1
6.3.2 旅行商（TSP）问题
一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条
精品文档

可编辑
最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地 ）？这个问题称
为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的
Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅
行商问题 的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。
一个可行的办法是首先求一个 Hamilton圈
C
，然后适当修改
C
以得到具有较小
权的另一个 Hamilton圈。修改的方法叫做改良圈算法。设初始圈
C

v
1
v
2

v
n
v
1
。
（i）对于
1i1jn
，构造新的Hamilton圈:
< br>C
ij
v
1
v
2

v
i
v
j
v
j1
v
j2

v
i1
v
j1
v
j2

v
n
v
1
,
它是由
C
中删去边
v
i
v
i1
和< br>v
j
v
j1
，添加边
v
i
v
j< br>和
v
i1
v
j1
而得到的。若
w(v
i
v
j
)w(v
i1
v
j1
)w(v
i
v
i1
)w(v
j
v
j1
)
， 则以
C
ij
代替
C
，
C
ij
叫做
C
的改良圈。
（ii）转（i），直至无法改进，停止。
用改良圈算法得到的结果 几乎可以肯定不是最优的。为了得到更高的精确度，可以
选择不同的初始圈，重复进行几次算法，以求得 较精确的结果。
这个算法的优劣程度有时能用Kruskal算法加以说明。假设
C
是
G
中的最优圈。
则对于任何顶点
v
，
Cv
是在
Gv
中的Hamilton轨，因而也是
Gv
的生成树。
由此推 知：若
T
是
Gv
中的最优树，同时
e
和
f
是和
v
关联的两条边，并使得
w(e)w(f)
尽可能小，则
w (T)w(e)w(f)
将是
w(C)
的一个下界。
这里介绍的方法已 被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条
边更为有效；然而，有点奇怪的是，进一 步推广这一想法，就不利了。
例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城( M)、伦敦(L)、巴黎(Pa)
五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程 最短？各城市之
间的航线距离如下表：

L M N Pa Pe T
L
M
N
Pa
Pe
T

56
35
21
51
60
56

21
57
78
70
35
21

36
68
68
21
57
36

51
61
51
78
68
51

13
60
70
68
61
13

解：编写程序如下：
clc,clear
a(1,2)=56;a(1,3)=35;a(1,4)=21;a( 1,5)=51;a(1,6)=60;
a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;
a(3,4)=36;a(3,5)=68;a(3,6)=68;
a(4,5)=51;a(4,6)=61;
a(5,6)=13;
a(6,:)=0;
a=a+a';
精品文档

可编辑
c1=[5 1:4 6];
L=length(c1);
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if
a(c1(m),c1(n))+a(c1(m+1),c1(n+1)) flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
sum1=0;
for i=1:L-1
sum1=sum1+a(c1(i),c1(i+1));
end
circle=c1;
sum=sum1;
c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
sum1=0;
for i=1:L-1
sum1=sum1+a(c1(i),c1(i+1));
end
精品文档

可编辑
if sum1 sum=sum1;
circle=c1;
end
circle,sum

§7 最大流问题
7.1 最大流问题的数学描述
7.1.1 网络中的流
定义 在以
V
为节点集，
A
为弧集的有向图
G (V,A)
上定义如下的权函数：
（i）
L:AR
为孤上的权函数，弧< br>(i,j)A
对应的权
L(i,j)
记为
l
ij
， 称为孤
；
(i,j)
的容量下界（lower bound）
（ii）U:AR
为弧上的权函数，弧
(i,j)A
对应的权
U(i,j)< br>记为
u
ij
，称为孤
；
(i,j)
的容量上界，或 直接称为容量（capacity）
（iii）
D:VR
为顶点上的权函数，节点< br>iV
对应的权
D(i)
记为
d
i
，称为顶
点
i
的供需量（supply／demand）；
此时所构成的网络称为流网络，可以记为
N(V,A,L,U,D)
。
由于我们只讨论
V,A
为有限集合的情况，所以对于弧上的权函数
L,U
和顶 点上的
权函数
D
，可以直接用所有孤上对应的权组成的有限维向量表示，因此
L,U,D
有时直
接称为权向量，或简称权。由于给定有向图
G(V,A)
后，我们总是可以在它的弧集
合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。
在流网络中，弧
(i,j)
的容量下界
l
ij
和容 量上界
u
ij
表示的物理意义分别是：通过该
弧发送某种“物质”时，必须发 送的最小数量为
l
ij
，而发送的最大数量为
u
ij
。顶点
iV
对应的供需量
d
i
则表示该顶点从网络外部获得的“物质”数 量（
d
i
0
时），或从该顶
点发送到网络外部的“物质”数量（< br>d
i
0
时）。下面我们给出严格定义。
定义 对于流网 络
N(V,A,L,U,D)
，其上的一个流（flow）
f
是指从
N
的弧
集
A
到
R
的一个函数，即对每条弧
(i, j)
赋予一个实数
f
ij
（称为弧
(i,j)
的流量）。如
果流
f
满足
ij
j:(i,j)A

fj:(j,i)A

f
ji
d
i
,iV,
（1）
l
ij
f
ij
u
ij
,(i,j)A
， （2）
则称
f
为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络
（feasible network）．约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）
称为容量约束。
可见，当
d
i
0
时，表示有
d
i
个单位的流量从该项点流出，因此顶点
i
称为供应点
精品文档

可编辑
（supply node）或源（source），有时也形象地称 为起始点或发点等；当
d
i
0
时，
表示有
|
d< br>i
|
个单位的流量流入该点（或说被该顶点吸收），因此顶点
i
称为需 求点
（demand node）或汇（sink），有时也形象地称为终止点或收点等；当
d
i
0
时，
顶点
i
称为转运点（transshipmen t node）或平衡点、中间点等。此外，根据（1）
可知，对于可行网络，必有


d
iV
i
0
（3）
也就是说，所有节点上的供需量之和为0是网络中存在可行流的必要条件。
一般来说，我们总是可以把
L0
的流网络转化为
L0
的流网络进行研究。 所以，
除非特别说明，以后我们总是假设
L0
（即所有孤
(i,j)
的容量下界
l
ij
0
），并将
L0
时的流网络简记为
N(V,A,U,D)
。此时，相应的容量约束（2）为

0
x
ij

u
ij
,(
i
,
j
)
A
。
定义 在流网络
N(V,A,U,D)
中，对于流
f
，如果

f
ij
0,(
i
,
j
)
A
，
则称
f
为零流，否则为非零流。如果某条弧
(i,j)
上的流量 等于其容量（
f
ij
u
ij
），则
称该弧为饱和弧（sa turated arc）；如果某条弧
(i,j)
上的流量小于其容量（
f
ij
u
ij
），
则称该弧为非饱和弧；如果某条弧
(i,j)上的流量为 0（
f
ij
0
），则称该弧为空弧（void
arc）。
7.1.2 最大流问题
考虑如下流网络
N(V,A,U, D)
：节点
s
为网络中唯一的源点，
t
为唯一的汇点，
而其 它节点为转运点。如果网络中存在可行流
f
，此时称流
f
的流量（或流值，f low
value）为
d
s
（根据（3），它自然也等于
dt
），通常记为
v
或
v(f)
，即

vv(f)d
s
d
t
。
对这种单源单汇的网络， 如果我们并不给定
d
s
和
d
t
（即流量不给定），则网络一
般记为
N(s,t,V,A,U)
。最大流问题（maximum flow pr oblem）就是在
。我们将会看到，最大流问题
N(s,t,V,A,U)
中找到 流值最大的可行流（即最大流）
的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我 们解决了最大
流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。
因此，用线性规划的方法，最大流问题可以形式地描述如下：
maxv

s.t.
（4）

0
x
ij
u
ij
,

v,is

x
ij< br>

x
ji


v,it

j :(i,j)Aj:(j,i)A

0,is,t

，
(
i
,
j
)
A
. （5）
精品文档
定义 如果一个矩阵
A
的任何子方阵的行列式的值都等 于
0
，
1
或
1
，则称
A
是

可编辑
全幺模的(totally unimodular TU，又译为全单位模的)，或称
A
是全幺模矩阵。
定理8（整流定理） 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量
均为正整数，则问题的最优解为整数解。 < br>最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问
题的方法较之线 性规划的一般方法要方便、直观得多。
7.1.3 单源和单汇运输网络
实际问题往往是多 源多汇网络，为了计算的规格化，可将多源多汇网络
G
化成单
源单汇网络
G'
。设
X
是
G
的源，
Y
是
G
的汇， 具体转化方法如下：
（i）在原图
G
中增加两个新的顶点
x
和y
，令其分别为新图
G'
中之单源和单汇，
则
G
中所有 顶点
V
成为
G'
之中间顶点集。
（ii）用一条容量为的弧把
x
连接到
X
中的每个顶点。
（iii）用一条容量为的弧把
Y
中的每个顶点连接到
y
。


G
和
G'
中的流以一个简单的方式相互对应。若
f< br>是
G
中的流，则由
若
a
是
G
的弧

f(a),

f'(a)

f

(v)f< br>
(v),
若
a(x,v)


f
(v)f

(v),
若
a(v,y)

所定义的函 数
f'
是
G'
中使得
v(f')v(f)
的流。反之，< br>G'
中的流在
G
的弧集
上的限制就是
G
中具有相同值 的流。
7.2 最大流和最小割关系
设
N(s,t,V,A,U)
，< br>SV
，
sS
，
tVS
，则称
(S,S)为网络的一
个割，其中SVS，
(S,S)
为尾在
S
，头在
S
的弧集，称

C(S,S)

u
ij

(i,j)A
iS,jS
为割
(S,S)
的容量。
定理9
f
是最大流，
(S,S)
是容量最小的割的充要条件是
v(f)C(S,S)
。
在网络
N(s,t,V,A,U)
中 ，对于轨
(
s
,
v
2
,

,
v< br>n1
,
t
)
（此轨为无向的），若
v
i
v
i1
A
，则称它为前向弧；若
v
i1
v
i< br>
A
，则称它为后向弧。
在网络
N
中，从
s
到
t
的轨
P
上，若对所有的前向弧
(i,j)
都有
f
ij
u
ij
，
对所有的后向弧
(i,j)
恒 有
f
ij
0
，则称这条轨
P
为从
s
到< br>t
的关于
f
的可增广
轨。
令

u
ij
f
ij
,
当
（i,j)
为前向弧

ij


，
f,
当
（i,j)
为后向弧

ij
精品文档

可编辑

min{

ij
}

则在这条可增广轨上每条前向弧的流都可以增加一个量

，而相应的后向弧
的 流可减少

，这样就可使得网络的流量获得增加，同时可以使每条弧的流
量不超过它的 容量，而且保持为正，也不影响其它弧的流量。总之，网络中
f
可增广轨的存在是有意义的，因 为这意味着
f
不是最大流。
7.3 最大流的一种算法—标号法
标号法是 由Ford和Fulkerson在1957年提出的。用标号法寻求网络
中最大流的基本思想是寻找可 增广轨，使网络的流量得到增加，直到最大为
止。

即首先给出一个初始流，这样的 流是存在的，例如零流。如果存在关于它的可增广轨，
那么调整该轨上每条弧上的流量，就可以得到新的 流。对于新的流，如果仍存在可增广
轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存 在关于新得到流的
可增广轨为止，则该流就是所求的最大流。
这种方法分为以下两个过程：
A.标号过程：通过标号过程寻找一条可增广轨。
B.增流过程：沿着可增广轨增加网络的流量。
这两个过程的步骤分述如下。
（A）标号过程：
（i）给发点标号为
(
s
,)
。 < br>
（ii）若顶点
x
已经标号，则对
x
的所有未标号的邻接顶 点
y
按以下规则标号：
① 若
(x,y)A
，且
fxy
u
xy
时，令

y
min{u
xy< br>f
xy
,

x
}
，

则给顶点
y
标号为
(
x
,

y
)
，若f
xy
u
xy
，则不给顶点
y
标号。

②
(y,x)A
，且
f
yx
0
， 令

y
min{f
yx
,

x
}
，则给
y
标号为
(x,

y
)
，若
f< br>yx
0
，则不给
y
标号。
（iii）不断地重复步骤（i i）直到收点
t
被标号，或不再有顶点可以标号为止。当
t
被标号时，表明存 在一条从
s
到
t
的可增广轨，则转向增流过程（B）。如若
t
点不能被
标号，且不存在其它可以标号的顶点时，表明不存在从
s
到
t的可增广轨，算法结束，
此时所获得的流就是最大流。
（B）增流过程
（i）令
ut
。

（ii）若
u
的标号为< br>(v,

t
），则
f
vu
f
vu


t
；若
u
的标号为
(v,

t
)
，则
f
uv
f
uv


t
。
（iii）若
us
，把全部标号去掉，并回到标号过程（A）。否则，令
uv
，并回
到增流过程（ii）。
求网络
N(s,t,V,A,U)
中的最大流
x
的算法的程序设计具体步骤如下：
精品文档

可编辑
对每个节点
j
，其标号包括两部分信息
(pred(j),maxf(j))

该节点在可能的增广路中的前一个节点
pred(j)
，以及沿该可能的增广路到该节点为止
可以增广的最大流量
maxf (j)
。
STEP0 置初始可行流
x
（如零流）；对节点
t< br>标号，即令
maxf(t)
=任意正值（如
1）。
STEP1 若
maxf(j)0
，继续下一步；否则停止，已经得到最大流，结束。
STEP2 取消所有节点
jV
的标号，即令
maxf(j)0
，
pred (j)0
；令LIST={
s
}，对节点
s
标号，即令
m axf(s)
充分大的正值。
STEP3 如果LIST

且
maxf(t)0
，继续下一步；否则：（3a）如果
t
已经
有标号（即
maxf(t)0
），则找到了一条增广路，沿该增广路对流
x
进行增广（ 增广
的流量为
maxf(t)
，增广路可以根据pred回溯方便地得到），转STE P1。
（3b）如果
t
没有标号（即LIST=

且
ma xf(t)0
），转STEP1。
STEP4 从LIST中移走一个节点
i< br>；寻找从节点
i
出发的所有可能的增广弧：（4a）
对非饱和前向弧
( i,j)
，若节点
j
没有标号（即
pred(j)0
），对
j
进行标号，即令
maxf(j)min{maxf(i),u
ij
 x
ij
}
，
pred(j)i
，
并将
j
加入LIST中。
（4b）对非空后向弧
(j,i)
，若节点
j
没有标号（即
pred(j)0
），对
j
进 行标号，
即令
maxf(j)min{maxf(i),x
ij
}
，
pred(j)i
，
并将
j
加入LIST中。
例14 用Ford- Fulkerson算法计算如下网络中的最大流，每条弧上的两个数字
分别表示容量和当前流量。
解 编写程序如下：
clc,clear,M=1000;
u(1,2)=1;u(1,3)=1;u(1,4)=2;
u(2,3)=1;u(2,5)=2;
u(3,5)=1;
u(4,3)=3;u(4,5)=3;
f(1,2)=1;f(1,3)=0;f(1,4)=1;
f(2,3)=0;f(2,5)=1;

精品文档

可编辑
f(3,5)=1;
f(4,3)=1;f(4,5)=0;
n=length(u);
list=[];
maxf=zeros(1:n);maxf(n)=1;
while maxf(n)>0
maxf=zeros(1,n);pred=zeros(1,n);
list=1;record=list;maxf(1)=M;
while (~isempty(list))&(maxf(n)==0)
flag=list(1);list(1)=[];
index1=(find(u(flag,:)~=0));
label1=index1(find(u(flag,index1)...
-f(flag,index1)~=0));
label1=setdiff(label1,record);
list=union(list,label1);
pred(label1(find(pred(label1)==0)))=flag;
maxf(label1)=min(maxf(flag),u(flag,label1)...
-f(flag,label1));
record=union(record,label1);
label2=find(f(:,flag)~=0);
label2=label2';
label2=setdiff(label2,record);
list=union(list,label2);
pred(label2(find(pred(label2)==0)))=-flag;
maxf(label2)=min(maxf(flag),f(label2,flag));
record=union(record,label2);
end
if maxf(n)>0
v2=n;
v1=pred(v2);
while v2~=1
if v1>0
f(v1,v2)=f(v1,v2)+maxf(n);
else
v1=abs(v1);
f(v2,v1)=f(v2,v1)-maxf(n);
end
v2=v1;
v1=pred(v2);
精品文档

可编辑
end
end
end
f

§8 最小费用流及其求法
8.1 最小费用流
上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流
的费用问题，在许多实 际问题中，费用的因素很重要。例如，在运输问题中，人们总是
希望在完成运输任务的同时，寻求一个使 总的运输费用最小的运输方案。这就是下面要
介绍的最小费用流问题。
在运输网络
N (s,t,V,A,U)
中，设
c
ij
是定义在
A
上的非 负函数，它表示通过弧
(i,j)
单位流的费用。所谓最小费用流问题就是从发点到收点怎样以 最小费用输送一已
知量为
v(f)
的总流量。
最小费用流问题可以用如下的线性规划问题描述：
min
(i,j)A

c
ijij
f


v(f),is

s.t.

f
ij


f
ji


v(f),it
，
j:(i,j)Aj:(j,i)A

0,is,t


0
f
ij

u
ij
,(
i
,
j
)
A
.
显然，如果
v(f)
最大流
v
(
f
max
)
，则本问题就是最小费用最大流问题。如果
v(f)v(f
max
)
，则本问题无解。
8.2 求最小费用流的一种方法—迭代法
这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由Bus acker和
Gowan在1961年提出的。其主要步骤如下：
(i)求出从发点到收点的最小费用通路

(s,t)
。
(ii)对该通路

(s,t)
分配最大可能的流量：
fmin{u
ij
}

(i,j)

(s,t )
并让通路上的所有边的容量相应减少
f
。这时，对于通路上的饱和边，其单位流费用
相应改为

。
(iii)作该通路

(s,t)
上所有边
(i,j)
的反向边
(j,i)
。令
u
ji
f
，
c
ji
c
ij

(iv)在这样构成的新网络中，重复上述步骤(i)，(ii)，(iii)，直到从发点到收点的全 部
流量等于
v(f)
为止（或者再也找不到从
s
到
t
的最小费用道路）。

习 题 五
精品文档

可编辑
1. 一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去，
但由于船小 ，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，
都不能在无人监视的情况下 留在一起。问摆渡人应怎样把它们运过河去？
2. 北京（Pe）、东京(T)、纽约(N)、墨西哥 城(M)、伦敦(L)、巴黎(Pa)各城市之间
的航线距离如下表：

L M N Pa Pe T
L
M
N
Pa
Pe
T

56
35
21
51
60
56

21
57
78
70
35
21

36
68
68
21
57
36

51
61
51
78
68
51

13
60
70
68
61
13

由上述交通网络的数据确定最小生成树。
3. 某台机器可连续工作4年，也可于每年末卖 掉，换一台新的。已知于各年初
购置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新 机器第一年运
行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8，1. 5，
2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费
用 为最省。
j

第一年 第二年 第三年 第四年
年初购置价
2.5 2.6 2.8 3.1
使用了
j
年的机器处理价
2.0 1.6 1.3 1.1

4. 某产品从仓库运往市场销售。已知各仓库 的可供量、各市场需求量及从
i
仓库
至
j
市场的路径的运输能力如下 表所示（表中数字0代表无路可通），试求从仓库可运
往市场的最大流量，各市场需求能否满足？
仓库
i
市场
j

1
30
0
20
20
2
10
0
10
20
3
0
10
40
60
4
40
50
5
20
可供量
20
20
100

A

B

C

需求量

5. 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄
文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5
个人是否都 能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？
6. 下表给出某运输问题的产 销平衡表与单位运价表。将此问题转化为最小费用最
大流问题，画出网络图并求数值解。
产量 销地
A

B

精品文档
1
20
30
2
24
22
3
5
20
产量
8
7

可编辑
销量

4 5 6

7. 求下图所示网络的最小费用最大流，弧旁数字为
(c
ij
,
u
ij
)
。



精品文档