17
二、最小生成树问题的应用
解（参见教材P179）
18
第五节 最大流问题
最大流问题是一类应用极为广泛的问题。例如在交通 运输网络中有人流、车流、货物流，供水网络中有水 流，金融系统中有现金流，通信系统中有信息流，等 等。对于这些包含了流量问题的系统，往往要求求出 其系统的最大流量。
例如，某公路系统容许通过的最多车辆数、某供水系统的 最大水流量等，以便我们加深对某个系统的认识并加以改 造。
所谓最大流问题就是：给了一个带收发点的网络，其 每条弧的赋权称为容量，在不超过每条弧容量的前提 下，求出从发点到收点的最大流量。
19
一、最大流的数学模型
解（参见教材P181）
20
二、最大流问题的网络图论解法
(一)对网络上弧的容量的表示作改进
(二)求最大流的基本算法
21
第六节 最小费用最大流问题
解（参见教材P164）
例7-2 农夫、狼、羊、草过河问题。
有位农夫，携带一匹狼、一只羊和一挑草要过一条小河， 河中只有一条小船，一次摆渡农夫只能携带一样东西。当 农夫不在场时，狼要吃羊，羊要吃草。试问：农夫怎样才 能将这三样东西摆渡到对岸？至少要摆渡几次？
解（参见教材P165）
[M、W、S、G] [M、S] [M、W、S] [M、W、G] [M、S、G]
例如，在架设电话线、铺设自来水管道或 暖气管道的工程设计中会遇到如下的优化 问题：如何使通话点或者取水取暖点相互 连通，但总的线路长度最短。这类问题在 网络分析中称为最小生成树问题。
14
一、求解最小生成树问题的破圈算法和避圈算法
(一)树的概念和性质
v1 v2 v1 v4 v2 v4 v1
v8 v9
A T S R
B C D P
V1
V2
V3
V4
V5
V6
V7
[W、G]
V8
[G]
V9
[S]
V10
[W]
[ ]
6
第二节 图论中的基本概念
7
第二节 图论中的基本概念
钱 (v2 )
a1 a2
在图7-6中“相互认识”用两条反向的弧来表示。
a8 a7
(v1 ) 赵
a4
a3
孙 (v3 )
李(v 4 )
a9
a5
2
第七章 图论与网络分析
运用图论中的分析技术可以解决现实世界的许多问题， 如交通网、管道网、通信网的优化以及工程进度安排 等问题。除此之外，还有很多问题，从表面上看似乎 与网络毫无关系，但实质上也可以用网络模型来描写， 例如设备更新的优化问题，就可以表述为网络分析中 的最短路问题。
通过学习本章，应当了解图与网络的基本概念；掌握 最短路问题、最大流问题和最小费用最大流问题的图 论解法，并会对管理中的实际问题进行分析判别其是 哪一类图论问题；学会运用WinQSB来求解经济管理 中的图与网络问题。
vi
(c ji , b ji )
(c)
vj
vi
(0, b ji )
(d)
vj
(c ji , b ji )
(二)求最小费用最大流的基本算法
24
第七节 中国邮递员问题 一、哥尼斯堡七桥问题与欧拉图
定理1 无向连通图G是欧拉图，当且仅当G中 无奇点。(证明从略) 定理2 连通有向图D是欧拉图，当且仅当它 每个顶点的出次等于入次。
22
一、最小费用最大流的数学模型
解（参见教材P186）
23
二、最小费用最大流的网络图论解法
(一)对网络上弧的容量和单位流量费用的表示 作改进
(cij , bij ) (cij , bij )
(0, bij )
vi
vj
vi
vj
(a)
(b)
(cij , bij )
(cij , bij )
(0, bij )
一个邮递员，负责某一地区的信件投递。 他每天要从邮局出发，走遍该地区所有 街道再返回邮局，问：应如何安排送信 的路线使所走的总路程最短？用图论的 语言来描述：给定一个连通图G，每边 有非负权，要求一条回路过每边至少一 次，且满足总权最小。
C
A
D
B
26
三、求解中国邮递员问题的奇偶点图作业 法及其改进
A A
C
D
C
D
B
B
4
一、图的基本概念及图的模型概述
1857年英国数学家哈密顿(Hamilton)发 明了一种游戏，他用一个实心正12面体 象征地球，正12面体的20个顶点分别 表示世界上20座城市，要求游戏者从任 一城市出发，寻找一条可经由每个城市 一次且仅一次再回到原出发点的路，这 就是“环球旅行”问题。它与七桥问题 不同，前者要在图中找一条经过每边一 次且仅一次的路，通称欧拉回路，而后 者是要在图中找一条经过每个点一次且 仅一次的路，通称为哈密尔顿回路。哈 密尔顿根据这个问题的特点，给出了一 种解法，如图7-2粗箭线所示。
3
第一节 图的基本概念及图的模型
一、图的基本概念及图的模型概述
瑞士数学家欧拉(E. Euler)在1736年发表了一篇题 为“依据几何位置的解题方法”的论文，有效地解 决了哥尼斯堡七桥难题，这是有记载的第一篇图论 论文，欧拉被公认为图论的创始人。18世纪的哥尼 斯堡城中流过一条河(普列格河)。河上有七座桥连 接着河的两岸和河中的两个小岛，如图7-1(a)所示。 欧拉将此问题归结为图7-1(b) ，这是一个用图的模 型来描述和解决实际问题的第一个著名例子。
在前面讨论的最大流问题中没有涉及费用问题。 但在实际生活中，各种物质的流都是与费用有 关的。如一辆载货汽车经过不同的路线，可能 要交不同的过路费、过桥费等，这样对于司机 来说就有一个到达某一目的地走哪条路线最省 钱的问题。最小费用最大流就是这样的问题。 所谓最小费用最大流问题就是：给了一个带收 发点的网络，对于每条弧，除了给出了容量外， 还给出了这条弧的单位流量的费用，要求一个 最大流F，并使得总运送费用最小。
(一)求解中国邮递员问题的奇偶点图作业法
(1) (2)
v2
4 1 2
5
如何构造第一个可行方案。 寻找改进的可行方案。
v2
4 1 2 1
5 5
v2
4
1
5
Байду номын сангаас
v3
2
3
v3
2
3
1 2 2 2
2
v3
2
3
1
2 2
v1
3 v 4 6
2 2
v6
v1
3 v 4 6
v6
v1
3 v4 6
v6
v2
3
v5
v5
v5
v1
v3
4
3
2 4
v3 v5 v7 v8
v3 v5 v8
v2 v4
v3 v5 v7
v6
v6 v9 v7
v6
(二)生成树和最小生成树
15
一、求解最小生成树问题的破圈算法和避圈算法
(三)求解最小生成树的破圈算法和避圈算 法
1．破圈法
具体步骤如下。
(1) 在给定的赋权的连通图上任找一个圈。 (2) 在所找的圈中去掉一条权数最大的边(如 果有两条或两条以上的边都是权数最大的边，则 任意去掉其中一条)。 (3) 如果所余下的图已不含圈，则计算结束， 所余下的图即为最小生成树。否则返回步骤(1)。
a6 a10
a11
陈(v7 )
周 ( v5 )
吴(v6 )
a13
a12
8
第三节 最短路问题
9
一、求解最短路问题的狄克斯托算法
10
一、求解最短路问题的狄克斯托算法
11
二、最短路问题的应用
解（参见教材P171）
12
二、最短路问题的应用
解（参见教材P173）
13
第四节 最小生成树问题
树是图论中结构最简单但又十分重要的图， 在自然科学和社会科学的许多领域都有广 泛的应用。
(二)奇偶点图作业法的改进方法
2
3 5
v6
2 v4 4
v5
27
第八节 图论问题的WinQSB求解
下面通过例子来说 明用WinQSB软件来 求解图论的问题。
28
一、最小生成树问题
解（参见教材P195）
29
二、设备更新问题
解（参见教材P196）
30
三、最大流问题
例7-13 图7-51所示某公司的生产基地位于节点 1处，现在要将产品销往节点6处。在节点1和 节点6之间存在如图7-51所示的交通网，每条弧 线(i，j)表示从i到j的运输线，它的权数表示该 运输线的最大运输能力，单位为“吨/天”。制 定一个运输方案，使得从生产基地1到销地6的 运输能力最大。 2
解（参见教材P197）
1 12 20 10 4 25 5 10 12 3 5 25 6 24
31
四、最小费用最大流问题
解（参见教材P198）
32
习
题
参见教材P200
16
一、求解最小生成树问题的破圈算法和避圈算法 2．避圈法
初始选一条最小权的边，以后每一步中总从未被选 取的边中选一条权最小的边，并使之与已选取的边 不构成圈(每一步中，如果有两条或两条以上的边 都是权最小的边，则从中任选一条)。具体步骤如 下。
(1) 在给定的赋权的连通图上选取一条最小权的边。 (2) 从未被选取的边中选取一条权最小的边，并使之 与已选取的边不构成圈。如果有两条或两条以上的 边都是权最小的边，则从中任选一条。 (3) 重复步骤(2)。如果这样的边不存在，则计算结 束。
与七桥问题类似的还有一笔画的问题。给出 一个图形，要求判定是否可以一笔画出。一 种是经过每边一次且仅一次到另一点停止， 另一种是经过每边一次且仅一次回到原出发 点。这两种情况可分别用欧拉道路和欧拉回 路的判定条件加以解决。