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

图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷CnH2n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）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。

例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))。其中（vertex set）或节点集（node set）， V(G)V(G){v1,v2,,vn}称为图G的顶点集

中的每一个元素vi(i1,2,,n)称为该图的一个顶点（vertex）或节点（node）；，E(G)中的每一个元素ek(即E(G){e1,e2,,em}称为图G的边集（edge set）

V(G)中某两个元素vi,vj的无序对) 记为ek(vi,vj)或ekvivjvjvi (k1,2,,m)，被称为该图的一条从vi到vj的边（edge）。

当边ekvivj时，称vi,vj为边ek的端点，并称vj与vi相邻（adjacent）；边ek称为与顶点vi,vj关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在图G中相邻。

边上赋权的无向图称为赋权无向图或无向网络（undirected network）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。

一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号|V|或(G)表示，边数用|E|或(G)表示。

当讨论的图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母G，例如，分别用V,E,和代替V(G),E(G),(G)和(G)。

端点重合为一点的边称为环(loop)。

一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。

2.2 有向图

G是由一个非空有限集合V和V定义 一个有向图（directed graph或 digraph）中某些元素的有序对集合A构成的二元组，记为G(V,A)。其中

V{v1,v2,,vn}称为图G的顶点集或节点集， V中的每一个元素vi(i1,2,,n)称为该图的一个顶点或节点；A{a1,a2,,am}称为图G的弧集

（arc set），A中的每一个元素ak(即V中某两个元素vi,vj的有序对) 记为。 ak(vi,vj)或akvivj(k1,2,,n)，被称为该图的一条从vi到vj的弧（arc）

当弧akvivj时，称vi为ak的尾（tail），vj为ak的头（head），并称弧ak为vi的出弧（outgoing arc），为vj的入弧（incoming arc）。

对应于每个有向图D，可以在相同顶点集上作一个图G，使得对于D的每条

弧，G有一条有相同端点的边与之相对应。这个图称为D的基础图。反之，给定任意图G，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为G的一个定向图。

以下若未指明“有向图”三字，“图”字皆指无向图。 2.3 完全图、二分图

每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点的完全图记为Kn。

若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称为H的母图。

G的支撑子图（spanning subgraph，又成生成子图）是指满足V(H)V(G)的

子图H。

2.5 顶点的度

设vV(G)，G中与v关联的边数（每个环算作两条边）称为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中的弧用自然数1,2,,m表示或编

号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。

（i）邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图G(V,A)的邻接矩阵是如下定义的：C是一个nn的01矩阵，即

C(cij)nn{0,1} cijnn，

1,(i,j)A,

0,(i,j)A.也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有n个元素中，只有m个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。

例7 对于右图所示的图，可以用邻接矩阵表示为

200000110000101000

01010110同样，对于网络中的权，也可以用类似邻接矩阵的nn矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。

（ii）关联矩阵表示法

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

B(bik)nm{1,0,1}nm，

1,jV,k(i,j)A, bik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)，则关联矩阵表示为

100000011011000011010 0100010110100001110同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。

（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，则弧表表示如下： 起点 终点 权

为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储的。

（iv）邻接表表示法

邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例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

这是一个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 3 3 4 4 6 5 7 6 9 记录弧信息的数组 弧编号 起点 终点 权 在数组point中，其元素个数比图的节点数多1（即n1），且一定有

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 point(1)1，point(n1)m1。对于节点i，其对应的出弧存放在弧信息数

组的位置区间为

[point(i),point(i1)1]，

如果point(i)point(i1)，则节点i没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（point）记录每个节点出发的弧的起始编号。

前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点n的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例7所示的图，可以用反向星形表示法表示为如下形式：

节点对应的入弧的起始地址编号数组（记为rpoint）

节点号i 起始地址rpoint(i) 记录弧信息的数组 弧编号 终点 起点 权 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧，则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，

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 1 1 2 1 3 3 4 6 5 8 6 9 可以在采用前向星形表示法的基础上，加上上面介绍的rpoint数组和如下的trace数组即可。这相当于一种紧凑的双向星形表示法如下所示：

两种表示法中的弧的对应关系（记为trace） 反向法中弧编号j 1 2 3 4 5 正向法中弧编号trace(j)

对于网络图的表示法，我们作如下说明：

① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如C语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费O(m)的计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。

② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。

③ 上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0和1，而不含有1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。

2.7 轨与连通

4 1 2 5 7 6 8 7 3 8 6 Wv0e1v1e2ekvk，其中eiE(G)，1ik，vjV(G)，0jk，ei与vi1,vi关联，称W是图G的一条道路(walk)，k为路长，顶点v0和vk分别称

为W的起点和终点，而v1,v2,,vk1称为它的内部顶点。

若道路W的边互不相同，则W称为迹(trail)。若道路W的顶点互不相同，则W称为轨(path)。

称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。

若图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)—直通铁路的长度，称为e的权，得到

赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u0,v0间的具最小权的轨。这条轨叫做u0,v0间的最短路，它的权叫做u0,v0间的距离，亦记作d(u0,v0)。

求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0从近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至v0（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。

(i) 令l(u0)0，对vu0，令l(v)，S0{u0}，i0。 (ii) 对每个vSi（SiV\\Si），用

min{l(v),l(u)w(uv)}

uSi代替l(v)。计算min{l(v)}，把达到这个最小值的一个顶点记为ui1，令

vSiSi1Si{ui1}。

(iii). 若i|V|1，停止；若i|V|1，用i1代替i，转(ii)。

算法结束时，从u0到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入Si之前的标号l(v)叫T标号，v进入Si时的标号l(v)叫P标号。算法就是不断

修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，u0至各项点的最短路也在图上标示出来了。

例9 某公司在六个城市c1,c2,,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的(i,j)位置上。（表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。

05040251040251001520251501020

2010010252010055252555050用矩阵ann（n为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、

index2、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的

值。其中分量

1当第i顶点已标号； pb(i)0当第i顶点未标号index2(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)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(index1)==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提出的算法，称之为Floyd算法。

假设图G权的邻接矩阵为A0，

3a11aA021an1a12a22an2a1na2n

ann来存放各边长度，其中：

aii0 i1,2,,n；

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

aijwij wij是i,j之间边的长度，i,j1,2,,n。

对于无向图，A0是对称矩阵，aijaji。

Floyd算法的基本思想是：递推产生一个矩阵序列A0,A1,,Ak,,An，其中

Ak(i,j)表示从顶点vi到顶点vj的路径上所经过的顶点序号不大于k的最短路径长

度。

计算时用迭代公式：

Ak(i,j)min(Ak1(i,j),Ak1(i,k)Ak1(k,j))

k是迭代次数，i,j,k1,2,,n。

最后，当kn时，An即是各顶点之间的最短通路值。

例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)(Kn)nn2。 公式 (G)(Ge)(Ge)。

其中Ge表示从G上删除边e，Ge表示把e的长度收缩为零得到的图。 树有下面常用的五个充要条件。

定理1 （i）G是树当且仅当G中任二顶点之间有且仅有一条轨道。 （ii）G是树当且仅当G无圈，且1。 （iii）G是树当且仅当G连通，且1。

（iv）G是树当且仅当G连通，且eE(G)，Ge不连通。 （v）G是树当且仅当G无圈，eE(G)，Ge恰有一个圈。 4.2 应用—连线问题

欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij，设计一个线路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。

下面介绍构造最小生成树的两种常用算法。 4.2.1 prim算法构造最小生成树

设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点，集合Q存放

G的最小生成树中的边。令集合P的初值为P{v1}（假设构造最小生成树时，从

顶点v1出发），集合Q的初值为Q。prim算法的思想是，从所有pP，

vVP的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加

入集合Q中，如此不断重复，直到PV时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。

prim算法如下：

（i）P{v1}，Q； （ii）while P~V

pvminw(pv,pP,vVP} PP{v} QQ{pv}

end

例11 用prim算法求右图的最小生成树。

我们用result3n的第一、二、三行分别表示生成树边的起点、终点、权集合。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;

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)选e1E(G)，使得w(e1)min。

(ii)若e1,e2,,ei已选好，则从E(G){e1,e2,,ei}中选取ei1，使得 ① G[{e1,e2,,ei,ei1}]中无圈，且 ② w(ei1)min。 (iii)直到选得e1为止。

例12 用Kruskal算法构造例3的最小生成树。

我们用index2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)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)，ei,ejM，ei与ej无公共端点（ij），则称M为图G的一个对集；M中的一条边的两个端点叫做在对集M中相配；M中的端点称为被M许配；G中每个顶点皆被M许配时，M称为完美对集；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|，其中N(S)是S中顶点的邻集。

由上述定理可以得出：

推论1：若G是k（k0)正则2分图，则G有完美对集。 所谓k正则图，即每顶点皆k度的图。

由此推论得出下面的婚配定理：

定理4 每个姑娘都结识k(k1)位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。

人员分派问题等实际问题可以化成对集来解决。

人员分派问题：工作人员x1,x2,,xn去做n件工作y1,y2,,yn，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有

适合的工作？

这个问题的数学模型是：G是二分图，顶点集划分为V(G)XY，

X1{x1,,xn}，Y1{y1,,yn}，当且仅当xi适合做工作yi时，xiyiE(G)，

求G中的最大对集。

解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。 匈牙利算法：

（i）从G中任意取定一个初始对集M。

（ii）若M把X中的顶点皆许配，停止，M即完美对集；否则取X中未被M许配的一顶点u，记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(xiyj)0，表示xi干yj工作的效益，求加权图G上的权最大的完美对集。

解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入可行顶点标号与相等子图的概念。

定义 若映射l:V(G)R，满足xX,yY， l(x)l(y)w(x,y)， 则称l是二分图G的可行顶点标号。令

El{xy|xyE(G),l(x)l(y)w(xy)}，

称以El为边集的G的生成子图为相等子图，记作Gl。

可行顶点标号是存在的。例如 l(x)maxw(xy),yYxX;

l(y)0, yY。

定理5 Gl的完美对集即为G的权最大的完美对集。 Kuhn-Munkres算法

（i）选定初始可行顶点标号l，确定Gl，在Gl中选取一个对集M。 （ii）若X中顶点皆被M许配，停止，M即G的权最大的完美对集；否则，取Gl中未被M许配的顶点u，令S{u}， T。

(iii)若NGl(S)T，转（iv）；若NGl(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 ，GlGl。

（iv）选NGl(S)T中一顶点y，若y已被M许配，且yxM，则

SS{z}，TT{y}，转（iii）；否则，取Gl中一个M可增广轨P(u,y)，

令

M(ME(P))(E(P)M)，

转（ii）。

其中NGl(S)是Gl中S的相邻顶点集。

例 已知利用5种不同产品作5种不同用途的效益矩阵为

x13x22Cx34x48x57y1601435520615，

23644256y2y3y4y5求最佳匹配使总的效益最高。

用x1,x2,x3,x4,x5表示5种产品，y1,y2,y3,y4,y5表示5种用途，可得

一个完全二部图K5,5。利用标号法求最佳匹配的步骤如下：

（

1

）

给

予

初

始

标

号

：

l(x1)6,l(x2)5,l(x3)6,l(x4)8,l(x5)7,l(y1)l(y2)l(y3)l(y4)l(y5)0。

（2）在给定的标号下求得的等性子集

Elx1y2,x2y3,x2y4,x3y3,x4y1,x5y1。构造G(El)，如图4-2-6.4所示。

（3）在G(El)中求得最大匹配Mx1y2,x2y4,x3y3,x4y1。 （4）x5未饱和，Sx5,T,N(S)y1；选y1，因为x4y1M，重新构造Sx4,x5,Ty1，这时N(S)T，必须修改原标号。

（5）求得l(x1)6,l(x2)5,i4,5;2j5minl(x)l(yij)w(xiyj)1，新的标号是

l(x3)6,l(x4)7,l(x5)6,l(y1)1,l(y2)l(y3)l(y4)l(y5)0。

（6）在新标号下求得等性子集

Ejx1y2,x2y3,x2y4,x3y3,x4y1,x5y1,x5y5，并构造G(El)，如图4-2-6.5

所示。

（7）求得G(El)的一个最大匹配Mx1y2,x2y4,x3y3,x4y1,x5y5，它使X部的所有结点都饱和，因此是最佳匹配。由这个最佳匹配得到的总效益为

W（M）=6+5+6+8+6=31。

x1 x2 x3 x4

y4

x5

图4-2-6.4

y1 y2 y3

x4 x5

图4-2-6.5

y4 y5

x1 x2 x3

y1 y2 y3

§6 Euler图和Hamilton图

6.1 基本概念

定义 经过G的每条边的迹叫做G的Euler迹；闭的Euler迹叫做Euler回路或E回路；含Euler回路的图叫做Euler图。

直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。

定理7 （i）G是Euler图的充分必要条件是G连通且每顶点皆偶次。

（ii）G是Euler图的充分必要条件是G连通且GCi1di，Ci是圈，

E(Ci)E(Cj)(ij)。

（iii）G中有Euler迹的充要条件是G连通且至多有两个奇次点。

定义 包含G的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或H圈；含Hamilton圈的图叫做Hamilton图。

直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。

6.2 Euler回路的Fleury算法

1921年，Fleury给出下面的求Euler回路的算法。 Fleury算法：

1o. v0V(G)，令W0v0。

2o. 假设迹Wiv0e1v1eivi已经选定，那么按下述方法从E{e1,,ei}中选取边ei1：

（i）ei1和vi相关联；

（ii）除非没有别的边可选择，否则ei1不是GiG{e1,,ei}的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。

3o. 当第2步不能再执行时，算法停止。 6.3 应用

6.3.1 邮递员问题

中国邮递员问题

一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。

上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。

显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。

对于非Euler图，1973年，Edmonds和Johnson给出下面的解法： 设G是连通赋权图。

（i）求V0{v|vV(G),d(v)1(mod2)}。

（ii）对每对顶点u,vV0，求d(u,v)（d(u,v)是u与v的距离，可用Floyd算法求得）。

（iii）构造完全赋权图K|V0|，以V0为顶点集，以d(u,v)为边uv的权。 （iv）求K|V0|中权之和最小的完美对集M。

（v）求M中边的端点之间的在G中的最短轨。

（vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。

（vii）在（vi）中得的图G'上求Euler回路即为中国邮递员问题的解。 多邮递员问题：

邮局有k(k2)位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。

kPP的数学模型如下：

G(V,E)是连通图，v0V(G)，求G的回路C1,,Ck，使得

（i）v0V(Ci)，i1,2,,k， （ii）max1ikkeE(Ci)w(e)min，

i（iii）

E(C)E(G)

i16.3.2 旅行商（TSP）问题

一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这

个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

一个可行的办法是首先求一个Hamilton圈C，然后适当修改C以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈Cv1v2vnv1。

（i）对于1i1jn，构造新的Hamilton圈: Cijv1v2vivjvj1vj2vi1vj1vj2vnv1,

它是由C中删去边vivi1和vjvj1，添加边vivj和vi1vj1而得到的。若则以Cij代替C，Cij叫做C的改良w(vivj)w(vi1vj1)w(vivi1)w(vjvj1)，

圈。

（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 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 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 sum1circle,sum

§7 最大流问题

7.1 最大流问题的数学描述

7.1.1 网络中的流

定义 在以V为节点集，A为弧集的有向图G(V,A)上定义如下的权函数：

（i）L:AR为孤上的权函数，弧(i,j)A对应的权L(i,j)记为lij，称为孤(i,j)的容量下界（lower bound）；

（ii）U:AR为弧上的权函数，弧(i,j)A对应的权U(i,j)记为uij，称为孤(i,j)的容量上界，或直接称为容量（capacity）；

（iii）D:VR为顶点上的权函数，节点iV对应的权D(i)记为di，称为顶点i的供需量（supply／demand）；

此时所构成的网络称为流网络，可以记为

N(V,A,L,U,D)。

由于我们只讨论V,A为有限集合的情况，所以对于弧上的权函数L,U和顶点上的权函数D，可以直接用所有孤上对应的权组成的有限维向量表示，因此L,U,D有时直接称为权向量，或简称权。由于给定有向图G(V,A)后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。 在流网络中，弧(i,j)的容量下界lij和容量上界uij表示的物理意义分别是：通

过该弧发送某种“物质”时，必须发送的最小数量为lij，而发送的最大数量为uij。顶点iV对应的供需量di则表示该顶点从网络外部获得的“物质”数量（di0时），或从该顶点发送到网络外部的“物质”数量（di0时）。下面我们给出严格定义。

定义 对于流网络N(V,A,L,U,D)，其上的一个流（flow）f是指从N的弧集A到R的一个函数，即对每条弧(i,j)赋予一个实数fij（称为弧(i,j)的流量）。如果流f满足

ijj:(i,j)Afj:(j,i)Afjidi,iV,

（1）

lijfijuij,(i,j)A（2）

，

则称f为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络（feasible network）．约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。

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

diVi0

（3）

也就是说，所有节点上的供需量之和为0是网络中存在可行流的必要条件。 一般来说，我们总是可以把L0的流网络转化为L0的流网络进行研究。所以，除非特别说明，以后我们总是假设L0（即所有孤(i,j)的容量下界lij0），

并将L0时的流网络简记为N(V,A,U,D)。此时，相应的容量约束（2）为 0xijuij,(i,j)A。

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

则称f为零流，否则为非零流。如果某条弧(i,j)上的流量等于其容量（fijuij），则称该弧为饱和弧（saturated arc）；如果某条弧(i,j)上的流量小于其容量（fijuij），则称该弧为非饱和弧；如果某条弧(i,j)上的流量为 0（fij0），则称该弧为空弧（void arc）。

7.1.2 最大流问题

考虑如下流网络N(V,A,U,D)：节点s为网络中唯一的源点，t为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f，此时称流f的流量（或流值，flow value）为ds（根据（3），它自然也等于dt），通常记为v或v(f)，即

vv(f)dsdt。

对这种单源单汇的网络，如果我们并不给定ds和dt（即流量不给定），则网络一般记为N(s,t,V,A,U)。最大流问题（maximum flow problem）就是在

N(s,t,V,A,U)中找到流值最大的可行流（即最大流）。我们将会看到，最大流

问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。

因此，用线性规划的方法，最大流问题可以形式地描述如下：

maxv

s.t.

v,isxxv,itijjij:(i,j)Aj:(j,i)A0,is,t ，

（4）

0xijuij,(i,j)A.

（5）

定义 如果一个矩阵A的任何子方阵的行列式的值都等于0，1或1，则称A是全幺模的(totally unimodular TU，又译为全单位模的)，或称A是全幺模矩阵。

定理8（整流定理） 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。

最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。

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是G中的流，则由

若a是G的弧f(a),f'(a)f(v)f(v),若a(x,v)

f(v)f(v),若a(v,y)所定义的函数f'是G'中使得v(f')v(f)的流。反之，G'中的流在G的弧集上的限制就是G中具有相同值的流。

7.2 最大流和最小割关系

设N(s,t,V,A,U)，SV，sS，tVS，则称(S,S)为网络的一个割，其中SVS，(S,S)为尾在S，头在S的弧集，称

C(S,S)(i,j)AiS,jSuij

为割(S,S)的容量。

定理9 f是最大流，(S,S)是容量最小的割的充要条件是

v(f)C(S,S)。

在网络N(s,t,V,A,U)中，对于轨(s,v2,,vn1,t)（此轨为无向的），若vivi1A，则称它为前向弧；若vi1viA，则称它为后向弧。

在网络N中，从s到t的轨P上，若对所有的前向弧(i,j)都有fijuij，对所有的后向弧(i,j)恒有fij0，则称这条轨P为从s到t的关于f的可增广轨。 令

uijfij,当（i,j)为前向弧ij，

f,当（i,j)为后向弧ijmin{ij}

则在这条可增广轨上每条前向弧的流都可以增加一个量，而相应的后向

弧的流可减少，这样就可使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中f可增广轨的存在是有意义的，因为这意味着f不是最大流。 7.3 最大流的一种算法—标号法

标号法是由Ford和Fulkerson在1957年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。

即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。

这种方法分为以下两个过程：

A.标号过程：通过标号过程寻找一条可增广轨。 B.增流过程：沿着可增广轨增加网络的流量。 这两个过程的步骤分述如下。 （A）标号过程：

（i）给发点标号为(s,)。

（ii）若顶点x已经标号，则对x的所有未标号的邻接顶点y按以下规则标号： ① 若(x,y)A，且fxyuxy时，令ymin{uxyfxy,x}，

则给顶点y标号为(x,y)，若fxyuxy，则不给顶点y标号。

② (y,x)A，且fyx0，令ymin{fyx,x}，则给y标号为(x,y)，若fyx0，则不给y标号。

（iii）不断地重复步骤（ii）直到收点t被标号，或不再有顶点可以标号为止。当t被标号时，表明存在一条从s到t的可增广轨，则转向增流过程（B）。如若t点不能被标号，且不存在其它可以标号的顶点时，表明不存在从s到t的可增广轨，算法结束，此时所获得的流就是最大流。

（B）增流过程 （i）令ut。

（ii）若u的标号为(v,t），则fvufvut；若u的标号为(v,t)，则

fuvfuv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标号，即令maxf(t)=任意正值（如1）。

STEP1 若maxf(j)0，继续下一步；否则停止，已经得到最大流，结束。 STEP2 取消所有节点jV的标号，即令maxf(j)0，

pred(j)0；令LIST={s}，对节点s标号，即令maxf(s)充分大的正值。

STEP3 如果LIST且maxf(t)0，继续下一步；否则：（3a）如果t已经有标号（即maxf(t)0），则找到了一条增广路，沿该增广路对流x进行增广（增

广的流量为maxf(t)，增广路可以根据pred回溯方便地得到），转STEP1。 （3b）如果t没有标号（即LIST=且maxf(t)0），转STEP1。

STEP4 从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧：（4a）对非饱和前向弧(i,j)，若节点j没有标号（即pred(j)0），对j进行标号，即令

maxf(j)min{maxf(i),uijxij}，pred(j)i，

并将j加入LIST中。

（4b）对非空后向弧(j,i)，若节点j没有标号（即pred(j)0），对j进行标号，即令

maxf(j)min{maxf(i),xij}，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)中，设cij是定义在A上的非负函数，它表示通过弧(i,j)单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已知量为v(f)的总流量。

最小费用流问题可以用如下的线性规划问题描述：

min(i,j)Acijijf

v(f),isfjiv(f),it ，

0,is,ts.t.

ijj:(i,j)Afj:(j,i)A 0fijuij,(i,j)A.

显然，如果v(f)最大流v(fmax)，则本问题就是最小费用最大流问题。如果

v(f)v(fmax)，则本问题无解。

8.2 求最小费用流的一种方法—迭代法

这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由Busacker和Gowan在1961年提出的。其主要步骤如下：

(i)求出从发点到收点的最小费用通路(s,t)。 (ii)对该通路(s,t)分配最大可能的流量：

fmin{uij}

(i,j)(s,t)并让通路上的所有边的容量相应减少f。这时，对于通路上的饱和边，其单位流费用相应改为。

(iii)作该通路(s,t)上所有边(i,j)的反向边(j,i)。令

ujif，cjicij

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

§4-2-4 欧拉图及其应用

欧拉在1763年解决著名的Konigsberg七桥难题中，建立了欧拉图类存在性的完整理论。图论的研究方法也随之进入了数学的广大领域。

Konigsberg是18世纪时东普鲁士的一个城市，Pregel河流经该市，并把该市陆地分成了4个部分：两岸及两个河心岛。陆地间共有七座桥相通，如图4-2-4.1（a）所示。长期以来人们一直在议论一个话题：能否从任何一块陆地出发，通过每座桥一次且仅一次，最后又返回出发点？尽管人们做了许多试验，但没有一人成功。欧拉把这个实际问题转化为图4-2-4.1(b)所示的一个图论问题，他用结点A，B，C，D分别表示对应的陆地，用边来表示连接陆地的桥。这样，七桥问题等价于在图4-2-4.1(b)中找寻一条包括每条边一次的回路，或者说，从图中任一点出发，一笔把图画出来（每边只能经过一次）。欧拉证明，七桥问题具有否定的答案，从而解决了这一难题。下面介绍解决这一问题的基本思想。

A A B C B C

D

(a)

D 图4-2-4.1

(b)

定义 4-2-4.1 设G是一个无向图，包含G每条边的简单道路称为欧拉道路；包含G每条边的简单回路称为欧拉回路；具有欧拉回路的图称

为欧拉图。

显然，每个欧拉图必然是连通图。

定理 4-2-4.1 连通图G是欧拉图当且仅当G不含奇数度结点。 证明： 设G是欧拉图，则必然存在一条包含每条边的回路C，当沿着回路C朝一个方向前进时，必定沿一条边进入某结点后再沿另一条边由这个结点出去，即每个结点都和偶数条边关联，因此G的结点都是偶数度结点。

反过来，设连通图G的结点都是偶数度结点，则G含有回路。设C是一条包含G中最多边的回路。若C包含了G的全部边，则G是欧拉图的结论成立。如果C不能包含G的全部边，则删边子图G-E（C）仍无奇数度结点。由于G是连通的的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C（如图4-2-4.2所示）。这样，就可以由C和C构造出GC 的一条包含边数C多的回路，与C的最大性假设矛盾。因此，G中包含边数最多的回路必是欧拉回路，即是说，不含奇数度结点的连通图是欧拉图。

推论 4-2-4.1.1 非平凡连通图G含有欧拉道路当且仅当G最多有两个奇数度结点。

证明： 设连通图G含有一条欧拉道路L，则在L中除起点与终点外，其余每个结点都与偶数条边相关联，因此，G中最多有两个奇数度的结点。

反过来，若G没有奇数度结点，显然有一条欧拉道路；若G有两个奇数度结点u和v，则G+uv是欧拉图，从而存在欧拉回路C。从C中去掉边vu，则得到一条简单道路L，其起点是u，终点是v，并且包含了G的全部边，即L是G的一条欧拉道路。

由定理4-2-4.1 及其推论知道，因为图4-2-4.1(b)中没有偶数度结点，不存在欧拉回路，甚至也不存在欧拉道路，所以Koningsberg七桥问题有

图4-2-4.2

C/

否定的结论。

无向图的欧拉道路问题及其有关结果很容易推广到有向图中去，这时，我们考虑的是有向欧拉道路和有向欧拉回路。

定理 4-2-4.2 连通有向图G含有有向欧拉回路当且仅当G中每个结点的入度等于出度 ，连通有向图G含有有向欧拉道路当且仅当除两个结点外，其余每个结点的入度等于其出度，而这两个结点中一个结点的入度比其出度多1，另一结点的入度比其出度少1。

这个定理的证明与定理4-2-4.1及其推论的证明类似。显然，一条有向欧拉回路进入任何一个结点的次数和离开这个结点的次数应该一样，因此有向欧拉图的顶点度数也是偶数。同样，含有向欧拉道路的图最多有两个奇数度结点。

对于一个已知的欧拉图G=（V，E），可以按下述方式构成一条欧拉回路。设置两个变量s和e，分别表示当前位于的结点和要经历的边。

由欧拉图G=（V，E）构造欧拉回路算法：

1．从G中任选一点v0和与v0关联的边e0，置sv0,ee0

2．记录s和e，并在G中标记e。设与e关联的另一结点为u0，置su0。 3．设从G中删去已标记过的全部k条边后得到的子图为Gk，则 3.1 当Gk为零图时，算法结束。

3.2 若在Gk中与s关联的边都不是割边，则任选其中一边e，置

ee，转2。

3.3 若在Gk中与s关联的边有割边e且s是Gk中的一度点，则令

ee，转2；否则在Gk中任选一条与s关联的非割边e//，令ee，转2。

这种构造欧拉回路的方法对于有向欧拉图和无向欧拉图同样适用，下面将用例子说明。欧拉图的一个应用例子就是所谓模数转换问题。

e0=0000 000 e1=0001 001 e8=1000 e9=1001 100 e2=0010 a b c d

e3=0011 e5=0101 101 010 e4=0100 e10=1010 e13=1101 110 e12=1100 e11=1011 011 e6=0110 e7=0111 111 e14=1110 e15=1111 图4-2-4.3

图4-2-4.4

例 设一个旋转鼓的表面分成了16个扇形段（图4-2-4.3），每个扇段用导体材料或者绝缘材料构成，分别表示0和1两种状态。现在要用四位的二进制数abcd给出a对应段的位置，要怎样安排或设置0和1两种状态的扇段，才能使16个扇段的位置号码各不相同？也就是说，如何把16个0或1排成一个循环，使得按同一方向由4个依次相连的0或1能够组成0000~1111中的每一个二进码？

这个问题可以这样来考虑：如图4-2-4.4，用8个结点分别表示000~111的八个二进码，若结点u的二进码为a1a2a3，结点v的二进码为a2a3a4，则（u，v）是有向图的一条边，这条边对应于四位的二进码a1a2a3a4。通过这种办法可以构造出一个有8个结点16条边的有向图，这16条边分别对应于0000~1111的16个二进码，且边（u,v）的二进码的后三位与边（v,w）的二进码的前三位相同。因此，上述找由16个0或1组成的循环，正好

对应于在图4-2-4.4中找一条有向欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。

现在按前面找欧拉回路的算法列表如下：

顺序 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 当前所在结点s 000 000 001 010 101 011 110 100 001 011 111 111 110 101 010 100 当前标记边e e0 e1 e2 e5 e11 e6 e12 e9 e3 e7 e15 e14 e13 e10 e4 e8 由图中得到一条欧拉回路C，其边序列为 e0,e1,e2,e5,e11,e6,e12,e9,e3,e7,e15,e14, e13,e10,e4,e8，由此得到对应的16个0或1的排列方式0000101100111101。

另一个与欧拉图有密切关系的应用问题是由管梅谷先生1962年提出的所谓“中国邮递员问题”。考虑的是一个邮递员从邮局出发，在其分管的投递区域内走遍所有的街道把邮件送到每个收件人手中，最后又回到邮局，要走怎样的路线使全程最短？这个问题可以用图来表示：以街道为图的边，以街道交叉口为图的结点，问题就是要从这样一个图中找出一条至少包含每个边一次的总长最短的闭道路。显然当这个图是欧拉图时，任何一条欧拉回路都符合要求；但是，当这个图不是欧拉时，所求闭道路必然

要重复通过某些边。对此，管梅谷曾证明若图的边数为m，则所求闭道路的长度最少是m，最多不超过2m，并且每条边在其中最多出现两次。中国邮递员问题还可以进一步推广到带权的连通图上，即在带权图中找一个包括全部边且权最小的闭道路。

一般意义下的中国邮递员问题是运筹学中一个典型的优化问题，这个问题有着有效的解决办法，其中最直观的方法之一是把图中的某些边复制成两条边，然后在所得图中找一个欧拉回路，这个回路即是原来问题的解。下面仅对无向介绍算法的基本思想：

求解无向图的中国邮递员问题算法。

（1）若G不含奇数度结点，则按本节前面介绍的方法所构造的欧拉回路，就是问题的解。

（2）若G含有2k(k0)个奇数度结点，则先求出其中任何两个结点之间的最短道路，然后再在这些道路之中找出k条道路p1,p2,pk，使得①任何pi和pj(ij)没有相同的起点和终点，②在所有满足①的k条道路的集合中，p1,p2,pk的长度总和最短。

（3）根据（2）中求出的k条最短道路p1,p2,pk在原图G中复制所有出现在这k条道路上的边，设所得之图为G。

（4）构造G的欧拉回路，即得到中国邮递员问题的解。 例 图4-2-4.5中G含有4个奇数度结点；

d(v1)3,d(v2)5,d(v3)3,d(v5)5。求得距离

d(v1,v2)3,d(v1,v3)5,d(v1,v5)4,d(v2,v3)2,d(v2,v5)3,d(v3,v5)4。从中选出两条长度总和最小的道路p1v1v7v5和p2v2v3，构造图G，

则中国邮递员问题的一个解便是回路Cv1v7v3v2v4v5v6v2v7v5v3v2v1v7v5v1。

求中国邮递员问题的算法中，包含了两个基本的优化算法：求任意两点的距离及求最佳匹配，它们都有对应的有效算法。

v2 v1 3 3 1 7 v6 2 v5 G

2 v3

v1

3 6 3 v7 1 5 1 3 3 1 3 7 v2 6 2 3 3 v3

v4 v6 2 1 v7 5 1 v4

图4-2-4.5

v5 G/

4-2-4习题

1．构造（n,m）－欧拉图使满足条件：（1）m和n有相同奇偶性；（2）m和n的奇偶性相反。

2．设G=（V，E）是一个具有2k(k0)个奇数度结点的连通图，证明G中必存在k条边不相重的简单道路p1,p2,,pk， 使得EE(p1)E(p2)E(pk)。

3．设G=（V，E）是不含奇数度结点的非平凡图，证明G中必有k个边不相交的回路c1,c2,,ck，使得EE(c1)E(c2)E(ck)。

4．设计一个由9个a，9个b，9个c组成的环形排列，使得由{a,b,c}组成的字长为3的27字中的每一个在排列中恰好出现一次。

5．在图4-2-4.6中求中国邮递员问题的解。

2 3 3 6 4 1 2 1 5 3 5 1 1 4 2 图4-2-4.6

1

6．证明G是平面欧拉图当且仅当其对偶图是平面二部图。 7．设G是无割边的平面连通图，证明G的面可以2着色当且仅当G

是欧拉图。

8．证明：若G是欧拉图，则线图L（G）也是欧拉图，反过来不成立。

9．设G是有两个奇度点的连通图，设计一个构造G的欧拉道路的算法。

习 题 五 1. 一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去，但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去？

2. 北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表：

L M N Pa Pe T L 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 61 13 由上述交通网络的数据确定最小生成树。

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

j 第一年 第二年 第三年 第四年 年初购置价 使用了j年的机器处理价 2.5 2.0 2.6 1.6 2.8 1.3 3.1 1.1 4. 某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从i仓库至j市场的路径的运输能力如下表所示（表中数字0代表无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？ 仓库i 市场j 1 2 3 0 4 40 可供量 20 A 30 10 B C 需求量 0 20 20 0 10 20 10 40 60 50 5 20 20 100

5. 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？

6. 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题，画出网络图并求数值解。 产量 销地 1 20 30 4 2 24 22 5 3 5 20 6 产量 8 7 A B 销量 7. 求下图所示网络的最小费用最大流，弧旁数字为(cij,uij)。

第五章 图与网络模型及方法 ................................................................................. 1

§1 概论 ............................................................................................................... 1 §2 图与网络的基本概念 ................................................................................... 3 §3 应用—最短路问题 ..................................................................................... 11 §4 树 ............................................................................................................... 15 §5 匹配问题 ................................................................................................... 18 §6 Euler图和Hamilton图 ............................................................................ 22 §7 最大流问题 ............................................................................................... 26 §8 最小费用流及其求法 ................................................................................. 34 §4-2-4 欧拉图及其应用 .............................................................................. 35