当前位置：文档之家 › 第6章 图与网络分析6.5-6.6

第6章 图与网络分析6.5-6.6

  • 格式：ppt
  • 大小：1.54 MB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

运筹学课件 第六章图与网络分析(清华大学出版社)

运筹学课件 第六章图与网络分析(清华大学出版社)
w(P ) = min w(P) 0
P
路P0的权称为从vs到vt的距离，记为：d（ vs，vt ）
OR3 12
– 最短路算法
Dijkstra算法 ：有向图 ，wij≥0 一般结论：
vs到 j的 短 v 最 路
vs ,...,vi ,...,vj ⇒ vs ,...,vi
vs到 i的 短 v 最 路
OR3 17
4 ）
标号的点，考察弧（ v 4 为刚得到 P 标号的点，考察弧（ v 4 , v 6），（ v 4 , v 7）的端点 v 6，v 7： T ( v ) = min [T ( v )， P ( v ) + l ] = min [13 , 9 + 9 ] = 13 46 6 6 4 T ( v ) = min [T ( v )， P ( v ) + l ] = min [14 , 9 + 7 ] = 14 47 7 7 4 标号， 最小， 比较所有 T 标号， T ( v ) 最小，所以令 P ( v ) = 13 。 6 6 此时 P 标号的点集 S = { ， ， , v , v , v } v1 v 2 v 3 5 4 6 。 6 7）v 为刚得到 P 标号的点，考察弧（ 标号的点，考察弧（ v 6 , v 7），（ v 6 , v 8）的端点 v 7， 8： v 6 T ( v ) = min [T ( v )， P ( v ) + l ] = min [14 ,13 + 5 ] = 14 67 7 7 6 T ( v ) = min [T ( v )， P ( v ) + l ] = min [+ ∞ ,13 + 4 ] = 17 68 8 8 6 标号， 最小， 比较所有 T 标号， T ( v ) 最小，所以令 P ( v ) = 14 。 7 7 此时 P 标号的点集 S = { ， ， , v , v , v , v } v1 v 2 v 3 5 4 6 7 。 7

运筹学(第6章 图与网络分析)

运筹学(第6章 图与网络分析)
a1 (v1) 赵
(v2)钱
a2 a3 a4 a14 a15
a8 a9
a7 (v4) 李
(v3)孙
a5 (v5) 周 a6 a10 (v6)吴
图6-3
a12 a11 a13
(v7)陈

定义: 图中的点用v表示，边用e表示。对每条边可用它
所连接的点表示，记作：e1=[v1,v1]; e2=[v1,v2];
树是图论中结构最简单但又十分重要的图。在自然和社会领 域应用极为广泛。 例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如 下图所示。
运动员 A
B C
D
E
F G
H

例6.3 某企业的组织机构图也可用树图表示。
厂长
人事科
财务科
总工 程师
生产副 厂长
经营副 厂长
开发科
技术科
生产科
设备科
供应科
动力科
e2
(v1) 赵
e1
e3
e4 孙(v3) 李(v4)
周(v5)
图6-2
e5 吴(v6) 陈(v7)
(v2)钱
如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关 系了，这是我们引入一个带箭头的联线，称为弧。图6-3就是 一个反映这七人“认识”关系的图。相互认识用两条反向的 弧表示。
端点,关联边,相邻 若有边e可表示为e=[vi,vj]，称vi和
e2 v2 e6 e1 e4 v1 e3 v3 e8
vj是边e的端点，反之称边e为点vi
或vj的关联边。若点vi、vj与同一条 边关联，称点vi和vj相邻；若边ei和
e5
e7

运筹学：第6章 图与网络分析

运筹学：第6章 图与网络分析
给图中的点和边赋以具体的含义和权值，我们称 这样的图为网络图（赋权图）
2021/4/18
6
图中的点用 v 表示，边用 e 表示，对每条边可用
它所联结的点表示，如图，则有：
e1 = [v1 , v1]， e2 = [v1 , v2]或e2= [v2 , v1]
2021/4/18
7
用点和点之间的线所构成的图，反映实际生产和 生活中的某些特定对象之间的特定关系。
第一种解法：
1. 在点集中任选一点，不妨取 S，令 V={S} 2. 找到和 S 相邻的边中，权值最小的 [S , A] 。
2021/4/18
22
3.V={S , A} 4. 重复第2，3步，找到下一个点。
2021/4/18
23
第二种做法求解过程：
2021/4/18
24
破圈法求解步骤：
1. 从图 N 中任取一回路，去掉这个回路中边 权最大的边，得到原图的一个子图 N1。
Dijkstra 算法假设：
1.设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =∞，显然 dii =0。 2. 设 Lsi 表示从 s 点到 i 点的最短距离。
2021/4/18
31
求从起始点 s 到终止点 t 的最短路径。 Dijkstra 算法步骤：
1.对起始点 s ，因 Lss =0 ，将 0 标注在 s 旁的小 方框内，表示 s 点已标号；
终点重合的链称为圈，起点和终点重合的路称为回
路，若在一个图中，每一对顶点之间至少存在一条
链，称这样的图为连通图，否则称该图为不连通的。
2021/4/18
12
2021/4/18
链

第6章 图与网络分析――基础知识PPT课件

第6章 图与网络分析――基础知识PPT课件

D
E
F
甲
√
√
√
乙
√
√
√
丙
√
√
丁
√
√
戊
√
√
√
己
√
√
√
将研究对象用点表示。对象与对象之间用边表示。依题意，找出不相邻的顺序。
B
C
ACBFED
A
D
36
F
E
类型2. 求最小部分树。避圈法和破圈法
基本定理：图中任一个点i，若j是与i相邻点 中距离最短的，则边[i，j]一定含在该图的 最小部分树内。
推论：把图的所有点分成集合V和它的补集两 个集合，则两集合之间连线的最短边一定 包含在最小部分树内。
A
7
2 2
S
5
B
5
D
5
T
1
1
4
3
7
C
E
4
39
[例2]如图6-2，SABCDET代表村镇，它们中间 连线表明各村镇间现有道路交通情况，连线旁 数字代表道路的长度。现要求沿图中道路架设 电线，使上述村镇全部通上电，应如何架设使 总的长度为最短。
A
7
2 2
S
5
B
5
D
5
T
1
1
4
3
7
C
E
4
40
[例2]如图6-2，SABCDET代表村镇，它们中间 连线表明各村镇间现有道路交通情况，连线旁 数字代表道路的长度。现要求沿图中道路架设 电线，使上述村镇全部通上电，应如何架设使 总的长度为最短。
点边交替序列，点边均不重 复。
点边交替序列，起点和终点 不重复。 点边交替序列，起点和终点 重复。

第六章图与网络分析

第六章图与网络分析

e3
v3
若链中所有的顶点也互不相同,这样的链称为路.
e4
v4
起点和终点重合的链称为圈. 起点和终点重合的路称为回路.
若图中的每一对顶点之间至少存在一条链, 称这 样的图为连通图, 否则称该图是不连通的. 第10页
完全图，偶图
任意两点之间均有边相连的简单图, 称为完全图. K n
K2
K3
K4
2 | E | Cn
第20页
6.2树图和图的最小部分树问题 Minimal tree problem 6.2.1树的概念
若图中的每一对顶点之间至少存在一条链, 称这样的图 为连通图. 树图(简称树Tree)： 无圈的连通的图，记作T(V, E)
组织机构、家谱、学科分支、因特网络、通讯网络及高压线路 网络等都能表达成一个树图 。
第13页
有向图 G ： (V,E)，记为 G=(V,E)
G 的点集合： V {v1 , v2 ,...,vn } G 的弧集合： E {eij } 且 eij 是一个有序二元组 (vi , v j ) ，记
为 eij (vi , v j ) 。下图就是一个有向图，简记 G 。 若 eij (vi , v j ) ，则称 eij 从 v i 连向 v j ，点 v i 称为 eij 的尾，v j 称为 eij 的头。 v i 称为 v j 的前继， v j 称为 v i 的后继。 基本图：去掉有向图的每条弧上的方向所得到的无向图。
有向图 G (V , E ) 的关联矩阵：一个 | V | | E | 阶矩阵
B (bik ) ，
1, 当 弧ek以 点i为 尾 其中 bik 1, 当 弧ek以 点i为 头 0, 否 则

第6章图与网络分析PPT课件

第6章图与网络分析PPT课件
有向图：图是由点和弧所构成的，
记 作 D={V ,A}(V 是 点 的 集 合 ， A 是 弧 的 集 合 ) ，
一条方向从vi指向vj的弧，记作(vi,vj)。
网络图：给图中的点和边赋予具体的含义和权数，如距离， 费用，容量等，记作N.
第8页
图的相关概念
若边eij=[vi,vj]∈E，称vi，vj是eij的端点，也称vi，vj是 相邻的。称eij是点vi（及点vj）的关联边。
若两条边有一个公共的端点，则称这两条边相邻。
点与点
相邻
vi
e
vj
vi，vj相邻
e 与vi，vj关联
边与边相邻
vi e1 vk e2
v
j
点与边关联
第9页
图的相关概念
若某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。
v1
v5 v4
e1 e2
e4
v2
e3 v3
e5
无环、无多重边的 图称为简单图。
无环、但允许有多 重边的图称为多重 图。
注：无特别声明我们今后讨论的图都是简单图
第10页
图的相关概念
图G中以点v为端点的边的数目，称为v在G中
的次(度）， 记为d（v）。
v1
v5 v4
e1 e2
e4
d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1
v2
e3 v3
e5
次为1 的点为悬挂点，悬挂点的关联边称为悬
第7章 图与网络分析
• 图的基本概念与模型 • 树图和图的最小部分树 • 最短路问题 • 网络最大流问题
第1页
概述
1
点击输入简要文字内容，文字内容需概括精炼，不用多余 的文字修饰，言简意赅的说明分项内容……

第6章 图与网络分析

第6章 图与网络分析
为了区别起见。把两点之间的不带箭头的连线称 为边，带箭头的连线称为弧。 用图来描述事物间的联系，不仅直观清晰，便于 统观全局，而且网络图的画法简便，不必拘泥于 比例和曲直。总之，这里所讲的图是反映对象之 间关系的一种工具。
29


2013-2-14
无向图

由点和边组成的图称为无向图。
无向图可表示为一个有序二元组(V，E)，记为 G＝(V，E)，其中 V ＝(v1，v2,…….vp)是 p 个点的集合，E＝{e1，e2，……eq}是 q 条边的集 合，并且 ei 是一个无序二元组，记为 ei＝[vi，vj]＝[vj,vi]， vi,vj∈V。
2013-2-14 31
环、多重边、简单图、多重图
一条边的两个端点如果相同，称此边 为环（自回路） 。如上图中的 e1。 两个点之间多于一条边的，称为多重 边。如上图中的 e4，e5。 不含环和多重边的图称为简单图，含 有多重边的图称为多重图。
2013-2-14 32
点的次
以点 v 为端点的边数叫做点 v 的次， 记作 d(v)。 如上图中， 1)=4， 2)=4。 d(v d(v 若 V＝(v1，v2,…….vp)，则称{ d(v1)，d(v2),…….d(vp)}为图 G 的次序列。 次为 1 的点称为悬挂点，连接悬挂点的边称为悬挂边。次为 0 的点称为 孤立点。 次为奇数的点称为奇点，次为偶数的点称为偶点。 定理 1 任何图 G＝(V，E)中，所有点的次数之和等于边数的 2 倍。即
运筹学 Operations Research
高 谦
烟台大学文经学院 基础教学部
2013-2-14 1
引言 图论是专门研究图的理论的一门数学 分支，属于离散数学范畴，与运筹学有 交叉，它有200多年历史，大体可划分 为三个阶段： 第一阶段是从十八世纪中叶到十九世纪 中叶，处于萌芽阶段，多数问题围绕游 戏而产生，最有代表性的工作是所谓的 Euler七桥问题，即一笔画问题。

运筹学第六章图与网络分析

运筹学第六章图与网络分析

S
2
4
7
2 A
0 5
S
5 45 B
98
14
5
13
D
T
C
E
4
4
4
7
最短路线：S AB E D T
最短距离：Lmin=13
2．求任意两点间最短距离的矩阵算法
⑴ 构造任意两点间直接到达的最短距离矩阵D（0）= dij（0）
S A B D（0）= C D E T
SABCDET 0 25 4 2 02 7 5 20 1 5 3 4 1 0 4 75 0 15 3 41 0 7 5 7 0
e1 v1
e5
v0 e2
e3
v2
e4
e6 e7
v3
v4
（4）简单图：无环、无多重边的图称为简单图。
（5）链：点和边的交替序列，其中点可重复，但边不能 重复。
（6）路：点和边的交替序列，但点和边均不能重复。
（7）圈：始点和终点重合的链。
（8）回路：始点和终点重合的路。
（9）连通图：若一个图中，任意两点之间至少存在一条 链，称这样的图为连通图。 （10）子图，部分图：设图G1=｛V1,E1｝, G2={V2,E2}, 如果有V1V2，E1E2，则称G1是G2的一个子图；若 V1=V2，E1E2，则称G1是G2的一个部分图。 （11）次：某点的关联边的个数称为该点的次，以d(vi)表示。
步骤：
1. 两两连接所有的奇点，使之均成为偶点；
2. 检查重复走的路线长度，是否不超过其所在 回路总长的一半，若超过，则调整连线，改 走另一半。
v1
4
v4
4
1
4
v2
v5
5

第6章图与网络分析

第6章图与网络分析
– 假如在网络旳发点和收点之间能找到一条链，在这条 链上全部指向为s→t旳弧（称为前向弧，记作µ+）， 存在f<c；全部指向为t → s旳弧（称为后向弧，记作 µ- ），存在f>0，这么旳链称为增广链。
s f1 c1
f2 0
f3 0
f4 c4
t
f5 c5
4. 网络最大流
❖ 最大流最小割定理
1)
}
0 5 2 7 12 6
5
0
7 2 7 4 10
2 7 0 6 5 4 10
D(1)
7
2
6
0
3
2
8
12 7 5 3 0 1 3
6 4 4 2 1 0 4
10 10 8 3 4 0
0 5 2 7 7 6 10
5
07
254
8
2 7 0 6 5 4 8
D(2)
7
26032
6
7 5 5 3 0 1 3
6 4 4 2 1 0 4
10 8 8 6 3 4 0
D(3) D(2)
【例】某人购置一台摩托车，准备在今后4年内使用。他可在第一年初 购置一台新车，连续使用4年，也可于任何一年末换一台新车。已知各 年初旳新车购置价如下表1。不同役龄车旳年使用维护费及年末处理价 如下表2。要求拟定该人使用摩托车旳最优更新策略，使4年内用于购置、 更新及使用维护旳总费用为最省。单位：万元。
d36 d46
d37 d47
2
2
0 7
7 0
6
4 2
d51
d52
d53
d54
d55
d56
d57
7
6
0

运筹学第6章 图与网络

运筹学第6章 图与网络

也就是说| V1 |必为偶数。
定理6.2有学者也称作定理6.1的推论。根据定理6.2，握手定理也可以 表述为，在任何集体聚会中，握过奇次手的人数一定是偶数个。
12 该课件的所有权属于熊义杰
另外，现实中不存在面数为奇数且每个面的边数也是奇数的多面 体，如表面为正三角形的多面体有4个面，表面为正五边形的多面体有 12个面等等，也可以用这一定理予以证明。因为在任意的一个多面体 中， 当且仅当两个面有公共边时，相应的两顶点间才会有一条边，即 任意多面体中的一个边总关联着两个面。所以，以多面体的面数为顶
v j V2
(m为G中的边数）
因式中 2m 是偶数， d (v j ) 是偶数，所以 d (vi ) 也必为偶数
v j V2
vi V1
( 两个同奇同偶数的和差必为偶数 ), 同时,由于 d (vi ) 中的每个加数 d (vi )
均为奇数,因而 d (vi ) 为偶数就表明, d (vi ) 必然是偶数个加数的和 ,
图论、算法图论、极值图论、网络图论、代数图论、随机图论、 模糊图论、超图论等等。由于现代科技尤其是大型计算机的迅 猛发展，使图论的用武之地大大拓展，无论是数学、物理、化 学、天文、地理、生物等基础科学，还是信息、交通、战争、 经济乃至社会科学的众多问题．都可以应用图论方法子以解决。
1976年，世界上发生了不少大事，其中一件是美国数学家 Appel和Haken在Koch的协作之下，用计算机证明了图论难题— —四色猜想(4CC)：任何地图，用四种颜色，可以把每国领土染 上一种颜色，并使相邻国家异色。4CC的提法和内容十分简朴， 以至于可以随便向一个人(哪怕他目不识丁)在几分钟之内讲清 楚。1852年英国的一个大学生格思里(Guthrie)向他的老师德·摩 根(De Morgan)请教这个问题，德·摩根是当时十分有名的数学家， 他不能判断这个猜想是否成立，于是这个问题很快有数学界流 传开来。1879年伦敦数学会会员Kemple声称，证明了4CC成立， 且发表了论文。10年后，Heawood指出了Kemple的证明中

第6章 网络分析

第6章 网络分析
简单链（路）:链中边 ei , ei ,..., ei 均不相同。
1 2 k
vi , vi ,..., vi 初等链：
1 2
k 1
均不相同。
简单圈（回路） ：边均不相同。 初等圈（回路） ：点均不相同。
图的连通性
点u和点v是连通的： 点u和点v之间存在链（路）。 连通图：图中任意两点连通。 连通分支：图G的极大连通子图。 图G是连通图当且仅当图G只有一个连通分支。 v8 v4 e e v ( v , v , v , v , v , v , v , v ) 5 5 例 1 2 3 4 5 3 6 7 v1 4
E 及其关联的顶点构成的子图称为由 E 导出的子图，记为 G[ E ] 。
子图的运算
设 G1 和 G2 是 G 的两个子图。 若 G1 和 G2 无公共顶点，则称它们是不相交的； 若 G1 和 G2 无公共边，则称它们是边不重的。 （1） G1 和 G2 的并（ G1 G2 ）：分别以 G1 和 G2 点集的并和边集 的并为点集和边集的子图； （2） G1 和 G2 的交（ G1 G2 ）：分别以 G1 和 G2 点集的交和边集 的交为点集和边集的子图。
子图
设 G (V , E ) 是一个图， 图 H (V 1, E1) 称为 G 的一个子 图，其中 V 1 是 V 的非空子集且 E1 是 E 的子集。 子图 支撑子图 设 G (V , E ) 是一个图，若 V V1 ，则 G 的子图 。 H (V 1, E1) 为 G 的支撑子图（或生成子图） 点导出子图 设 G (V , E ) 是图， 非空子集 S V ， 则 G 的以 S 为顶点集以两端点在 S 中的所有边构成边集的子图称为由 S 导出的 子图，记为 G[ S ] 。 边导出子图 设 G (V , E ) 是图，非空子集 E E ，则 G 的以

运筹学课件 第六章图与网络分析

运筹学课件 第六章图与网络分析

v 若 eij i , v j ，称 vi , v j 是边 eij 的端 点，反之，称边 eij 为点 v i 或 v j 的关联边。 若点 vi , v j 与同一条边关联，称点 vi v j 相邻； 若边 和 具有公共的端点，称 ei ei ej 和 相邻
e3 e13 v1, v3 v3 , v1 e31
2013-12-3
18

图中有些点和边的交替顺序 0 , e1 , v1 ,...,ek , vk v ，若其中各边 e1 , e2 ,...,ek 互不相同，且对 任意 vt 1 和 vt (2 t k ) 均相邻，称为 链。 上图中 1 v5 , e8 , v3, e3, v1, e2 , v2 , e4 , v3, e7 , v4
27
解
因要使上述村镇全部通上电，村镇之间必 须连通，又图中必不存在圈，否则从图中去掉一 条边图仍连通，就一定不是最短路线，故架设长 度最短的路线就是从上图中寻找一棵最小树。

2013-12-3
28

用避圈法时，先从图中任选一点 S , 令 S V ，其余点 V , V 与 V 间的最 短边为（ S , A) ，将该边加粗，标志它是最小 树内的边。再令 V A V ,V V A 重复上述步骤，一直到所有点连通为止。过程 如下：

如果用点表示研究的对象，用边表示这些 对象之间的联系，则图G可以定义为点与边的集 合，记作 G , E V
V v1 , v2 ,...,vn
E e1 , e2 ,..,em
式V是点的集合，E是边的集合。
2013-12-3 13

注意，上面定义的图G区别于几何学中的图。 几何学中，图中点的位置、线的长度和斜率等都 十分重要，而这里只关心图中有多少个点以及哪 些点之间有线相连。 如果给图中的点和边以具体的含义和权数 （如距离、费用、容量等）。把这样的图称为网 络图，记作N。 图和网络分析的方法已广泛应用于物理、化 学、控制论、信息论、计算机科学和经济管理等 各领域。

第6章 图与网络分析

第6章 图与网络分析
X={1,2,4}, P2=2
24
X={1,2,4}
P1=0
P2=2
2
6
1
2
3
1 P4=1 10
5
9
3
4
7
5
6
5
2
3
4
6
7
4
P6=3
8 8
min {c16,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, P6=3
25
X={1,2,4,6}
3
2
顶点的次
以顶点v为端点的边数称为点v的次。记作deg(v).
次为奇数的点称为奇点 次为偶数的点称为偶点
deg(2)＝4 deg(1)＝3 2
1
4
顶点次数的总和等于边数的二倍。
次为奇数的点必为偶数个。
3
权与网络
与点或边有关的数量指标称为“权”。
权可以代表种种意义，如距离、费用、容量等。
点或边带有某种数量指标的图称为网络（赋权图）
X={1,4}, P4=1
起点经i点到j点的最短路径长度
23
cij Pi lij
X={1,4}
P1=0
P2=2
2
6
1
2
3
1 P4=1 10
5
9
3
4
7
5
6
5
2
3
4
6
7
4
8 8
min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2

运筹学 CH6图与网络分析

运筹学 CH6图与网络分析
Chapter6 图与网络分析
( Graph Theory and Network Analysis )
本章主要内容：
图与树的基本概念
最短路问题 网络的最大流网络问ຫໍສະໝຸດ 的Excel解法教学目的与要求
【教学目的与要求】
Page 2
了解图和树的基本概念；掌握最短路问题基本理论；了解网 络最大流问题；了解Microsoft Excel求解网络问题的方法。 【教学重难点】 最短路问题
2、基本思想是采用两种标号：
从始点vs 出发，逐步探寻，给每个点标号； 标号分永久标号P(vk)和临时标号T(vk) 两种：
•永久标号P(vk) 是从点 vs → vk 的最短路权 •临时标号T(vk) 是从点 vs → vk 最短路权的上界
算法的每一步从临时标号集中选最小者变为永久标号； 经过逐次改变，就可以得到从点vs 到各点的最短路。
点：研究对象（城市、球队）。 点间连线：对象之间的特定关系。 对称关系：用不带箭头的连线表示，称为边。 非对称关系：用带箭头的连线表示，称为弧。 图是由点和连线组成。 无向图(简称图）：由点和边构成， 记作G = (V ,E)(V 是点的集合，E 是边的集合)
Page 7
连接点vi,vjV的边记作eij=[vi,vj]，或者[vj,vi]。
图—引言
Page 3
图论是应用非常广泛的运筹学分支，它已经广泛地应用 于物理学、控制论、信息论、交通运输、经济管理、电子计 算机等各项领域。 例如，各种通信线路的架设，输油管道的铺设，铁路或 公路交通网络的合理布局等问题。
图—引例1
哥尼斯堡七桥问题
Page 4
哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei 河把该城分成两部分，河中有两个小岛，十八世纪时，河两 边及小岛之间共有七座桥，当时人们提出这样的问题：有没 有办法从某处（如A）出发，经过各桥一次且仅一次最后回 到原地呢？

第6章 图与网络分析――基础知识PPT课件

第6章 图与网络分析――基础知识PPT课件

B
C
A
D
23
E
A
B
C
D
E
F
甲
√
√
√
乙
√
√
√
丙
√
√
丁
√
√
戊
√
√
√
己
√
√
√
将研究对象用点表示。对象与对象之间用边表示。
B
C
A
D
24
F
E
A
B
C
D
E
F
甲
√
√
√
乙
√
√
√
丙
√
√
丁
√
√
戊
√
√
√
己
√
√
√
将研究对象用点表示。对象与对象之间用边表示。
B
C
A
D
25
F
E
A
B
C
D
E
F
甲
√
√
√
乙
√
√
√
√
戊
√
√
√
树中任意两点之间有一条且仅有一条 惟一通路。
如果G1是G2的部分图，又是树图，
则称G1是G2的部分树（支撑树）。
树图的各条边称为树枝。一般G2有
多个树图，其中树枝总长度最小的
部分树称为最小部分树。
11
基本概念
有向图
（以前研究的都是无向图）
容量网络
发点（源点s） 中间点 收点（汇点t） 网络最大流
流
基础知识部分
第6章 图与网络分析
1.问题的提出 2.问题的模型 3.问题的求解

运筹学第6章图与网络分析

运筹学第6章图与网络分析
2020/7/14
A
C
D
B
哥尼斯堡七空桥
2020/7/14
A
C B
D
一笔画问题
哈密尔顿（Hamilton）回路是十九世纪 英国数学家哈密顿提出，给出一个正12 面体图形，共有20个顶点表示20个城市， 要求从某个城市出发沿着棱线寻找一条 经过每个城市一次而且仅一次，最后回 到原处的周游世界线路（并不要求经过 每条边）。
其链长为 n ，其中 v0 ，vn 分别称为链的起点和终点 。 若链中所含的边均不相同，则称此链为简单链；所含的点 均不相同的链称为初等链 , 也称通路。
v2
e1
v1
e2
e3
v3
e4
v4
e5 e7
e9
e8
v6
e10
e6
v5
11、图中任意两点之间均至少有一条通路，则称此图为 连通图，否则称为不连通图。
3、如果一个图是由点和弧所构成的，那么称它为有向图，记作
D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧 集合。一条方向从vi指向vj 的弧，记作(vi , vj)。
V = {v1 , v2 , v3 , v4 , v5 , v6 }，
v2
A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , v1
合
E构成{ek的} 二元组，记为G =(V，E)，其中 V 中的
元素 叫做顶点v j ，V 表示图 G 的点集合；E 中的元素
叫做边，Ee表k 示图 G 的边集合。
例
v1
V v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6
E { e 1 ， e 2 ,e 3 ,e 4 ,e 5 ,e 6 ,e 7 ,e 8 ,e 9 ,e 1 } 0e10
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
10 ( 4， )
v1
5 ( 2，)
7 (1，) 2 ( 6，)
vt
4 ( 2，)
vs
8 (1，)
v2
10 ( 3， )
v3
解：从f 0 = 0开始，构造加权网络图W ( f 0 )：
f0 = 0
1Байду номын сангаас ( 0)
W ( f0 )
vt
4
v1
7 ( 0) +5
2 ( 0)
3v1
1
4
vt
2
vs
+5
8 ( 0)
( k +1)
, 令 k := k + 1, 转
例6.5.1 求图6.5.1的最小费用最大流，弧旁的数字 为 (cij , wij ).
v2
(5, 6)
v4
(1, 2)
v1
(2,3)
(1, 2)
(3, 4)
v5
(3,1)
v3
图6.5.1
(1,3)
构造 D ( X (0) ). 解: 取 X (0) = 0, 见图6.4.7（a），
运行结果如下：
z= 2.0000 1.0000 0.0000 2.0000 0.0000 0.0000 3.0000 favl1 = 12.0000
结果说明最大流值为3，最小费用为12。 可以看出，最小费用最大流问题其实就是在最 大流问题基础上，再进行一次线性规划问题的计算 得出。
例：求图中从vs → vt的最小费用最大流。
即为最小费用最大流。 是最大流时， 注意到 cij ≥ 0, 故X=0必是流量为 0的最小费用 流。这样， 总可以从X=0开始。一般地， 若X是流量 f(X)的最小费用流， 为了寻求关于X的最小费用增 广链， 构造一个赋权有向图D(X)，它的顶点是原网 络D的顶点， 而把D中的每一条弧 (vi , v j ) 变成两个 相反方向的弧 (vi , v j ) 和 (v j , vi ), 定义D(X) 中弧的 权 wij′ : cij , 若xij < wij
0
U( 3, 5) U( 4, 5) F( 1, 2) F( 1, 3) F( 2, 3) F( 2, 4) F( 3, 4) F( 3, 5) F( 4, 5)
3.000000 4.000000 2.000000 1.000000 2.000000 0.000000 0.000000 3.000000 0.000000
C( X ) =
为可行流 的费用 可行流X的费用 可行流 的费用。
( vi , v j )∈ A
∑
cij xij
（6.5.1）
最小费用最大流问题，即要求一个最大流X，使总 运输费用
min C ( X ) =
( vi , v j )∈ A
∑
cij xij
（6.5.2）
达到最小值， 则有最小费用最大流问题的数学模型
v2
(5, 6, 0)
v4
(1, 2, 0)
v1
(2,3, 0)
(1, 2, 0)
(3, 4, 0)
v5
(3,1, 0)
v3 (1,3, 0)
图6.5.1（a） （ ）
因没有负权弧， 故可用Dijkstra算法求得最短路为
P (0) = v1v3v5 ,
见图6.5.1（b）。
v2
1 2
5
1
v4
3
1
算法步骤： 算法步骤： Step1: 确定初始可行流 X (0) = 0, 令 k := 0; Step2: 记 X ( k ) 为经过k次调整得到的最小费用流， 构造 D ( X ( k ) ); Step3: 求 D ( X ( k ) ) 中 v1 到 vn 的最短路 P ( k ) , 若 P ( k ) 不存在，则 X ( k )是最小费用最大流，算法 终止； 否则，转Step4； Step4: 在D中找对应的增广链 µ , 按式（6.4.4）调 整流量，得可行流 X Step2。
5 ( 0) +5
4 ( 0)
vs
0
1
6
2
v2
10 ( 0)
v3
1
v2
3
v3
4
f1 = f0 + 5 = 5
10 ( 0)
W ( f1 )
vt
4
+2
v1
5 ( 5)
7 ( 5)+2 2 ( 0)
v1
4
−1
1
−1
vt
2
5
vs
8 ( 5)
4 ( 0)
vs
0
1
6
−2
v2
10 ( 0)
v3
v2
1
3
v3 4
运行结果： Global optimal solution found at iteration:
Objective value: Variable Value D( 1) 3.000000 D( 2) 0.000000 D( 3) 0.000000 D( 4) 0.000000 D( 5) -3.000000 C( 1, 2) 1.000000 C( 1, 3) 3.000000 C( 2, 3) 2.000000 C( 2, 4) 5.000000 C( 3, 4) 1.000000 C( 3, 5) 1.000000 C( 4, 5) 3.000000 U( 1, 2) 2.000000 U( 1, 3) 1.000000 U( 2, 3) 3.000000 U( 2, 4) 6.000000 U( 3, 4) 2.000000 12.00000 Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
+1
v1
5 ( 5) -1
7 ( 7) 2 ( 0)
vt
4 ( 3) v
v1 4
−2
−1
6
−3
−2
7
vt
2
vs
8 ( 8)
+1
s
0
v2
10 ( 3)+1
wij′ = w′ (vi , v j ) = +∞, 若xij = wij
−cij , 若xij > 0 w ji′ = w′ (v j , vi ) = +∞, 若xij = 0 在D(X)中长度为 +∞ 的弧可以略去。
故在网络D中寻找关于 X的最小费用增广链就 等价于在赋权有向图D(X)中， 寻找从 v1 到vn 的最短 路。
f2 = f1 + 2 = 7
10 ( 2)
W ( f2 )
vt
4 ( 0) −4
v1
5 ( 5)
7 ( 7) 2 ( 0)
v1 4
4 −1
−1
6
6
vt
2
vs
8 ( 5)
+3
vs
0
1
−2
+3
v2
10 ( 0)+3
v3
v2
1
3
v3
4
f3 = f2 + 3 =10
10 ( 2)
W ( f3 )
−4 4
v1
3
v3
图6.5.1（b） （ ）
v5
增广链
µ (0) = v1v3v5
θ = min {1 − 0,3 − 0} = 1
调整后 X (1) 如图6.5.1（c）。
v2
(1, 2, 0) (5, 6, 0)
v4
(3, 4, 0)
(2,3, 0) (3,1,1)
(1, 2, 0)
v1
v3 (1,3,1)
v5
图6.5.1（c） （ ）
构造 D ( X (1) ) 得到
P (1) = v1v2 v3v5
如图6.5.1（d）。
v2
1
5
v4
1
2
−1
1
3
v5
v1
−3
v3
图6.5.1（d） （ ）
µ (1) = v1v2 v3v5
θ = min {2 − 0,3 − 0,3 − 1} = 2
调整得 X (2) , 如图6.5.1（e）。
从某个可行流出发， 从某个可行流出发， 找到关于这个可行流 的一条增广链， 的一条增广链，沿着 该增广链调整X， 该增广链调整 ，对 新的可行流试图寻求 关于它的增广链， 关于它的增广链，如 此反复直至最大流
设想： 当沿着一条关于可行流X的增广链 µ , 以
θ 调整X， 得到新的可行流 X ′, 且有
min C ( X ) =
( vi , v j )∈ A
∑
cij xij
（6.5.3）
n n ∑ X ij − ∑ X ji = 0 s.t. j =1 j =1 0 ≤ x ≤ w , (v , v ) ∈ A ij ij i j
§6.5.2 最小费用最大流问题的算法
寻求最大流的方法 最小 费用 最小费用最大流
C ( X ′) − C ( X ) =
( vi , v j )∈ A
∑
cij xij ′ −
( vi , v j )∈ A
∑
cij xij
= ∑ cij xij′ − ∑ cij xij
u
u
= ∑ cij ( xij + θ ) + ∑ cij ( xij − θ ) − ∑ cij xij