文档介绍：第六章图论方法
图是反映对象之间关系的一种工具。是在纸上用点和线画出的各种各样的示意图。
首先介绍涉及到的基本概念
一、树图和图的最小部分树
二、最短线路问题
三、最大流量问题
太原
石家庄
保定
灵丘
原平
天津
塘沽
通县
秦皇岛
密云
承德
北京
张家口
怀柔
甲
乙
丙
丁
戊
一、树图和图的最小部分树
树:一个无圈的连通图称为树。
最小树杈:是关于在一个网络中,从一个起点出发到所有点,找出一条或几条路线,以使在这样一些路线中所采用的全部支线的总长度是最小的,或铺设费用最少。
求图的最小树杈问题的方法有“破圈法”和“避圈法”。
树的性质
破圈法(克鲁斯喀尔法)
例:已知连接五个城市的公交线路图,在要在五个城市间架设电话线,为了便于维修要求电话线必须沿公路架设,并且电话线总长度最小。
此为最小树杈,最小线路长度为 20+15+10+9=54
v1
v2
v3
v4
v5
25
20
10
9
15
12
30
破圈法:任选一个圈,从圈中去掉杈最大的一条边。在余下的图中重复这个步骤,直到得到一连通的不含圈的图为止。
避圈法(普赖姆法)
避圈法:开始选一条杈最小的边,以后每一步中,总从未被选取的边中选一条杈尽可能小,且与已选边不构成圈的边。
v1
v2
v3
v4
v5
25
20
10
9
15
12
30
此为最小树杈,最小线路长度为 20+15+10+9=54
练习:求最小树杈
2
5
3
1
2
2
3
4
5
3
3
2
3
2
2
2
§ 最短线路问题
当通过网络的各边所需时间、距离或费用为已知时,找出从入口到出口所需的最少时间、最短距离或最少费用的路径问题,称做网络的路线问题。
本节主要介绍最短路线问题。方法以是从终点开始逐步逆向推算
100
300
9-10
6-9-10
500
4-6-9-10
650
1-4-6-9-10
150
8-10
375
7-8-10
400
5-8-10
600
2-6-9-10
600
3-5-8-10
2
8
4
5
3
6
100
400
350
275
175
250
1
7
9
150
175
225
150
100
200
300
200
275
200
10
4
1
6
9
10
最短路线为650
用EXCEL求最短路线问题
三、最大流量问题
当以物体、能量或信息等作为流量流过网络时,怎样使流过网络的流量最大,或者使流过网络的流量费用或时间最小。通常把设计为样的流量模型问题,叫做网络的流量问题。
本节主要讨论最大流量问题。即在一定条件下,要求流过网络的流量为最大。
1
2
3
4
6
5
6
5
3
4
7
5
7
3
2
在有一个起点和一个终点的网络中,最大流量问题是企图找出,在一定时期内,能在起点进入,并通过这个网络,在终点输出的最大流量。
1、确定网路最大流的标号法
(1) 网路的最大流的相关概念
s
t
5
3
4
2
(4,0)
(3,0)
(2,0)
(1,0)
(1,0)
(5,0)
(3,0)
(2,0)
(5,0)
定义网路上支路的容量为其最大通过能力,记为 cij ,支路上的实际流量记为 fij
图中规定一个发点s,一个收点t
(cij , fij )或 cij( fij )
容量限制条件:0≤fij ≤cij
平衡条件:
vi
A(vi)
B(vi)
满足上述条件的网路流称为可行流,总存在最大可行流
当支路上 fij = cij,称为饱和弧,否则称为不饱和弧
(2)标号法的基本算法
从任一个初始可行流出发。
若在当前可行流下找不到增广链,则已得到最大流
增广链是从发点到收点的一条链,该链上所有指向为s→t的前向弧,存在f<c;所有指向为t→s的后向弧,存在f>0,这样的链叫增广链。
基本算法:找一条从 s 到 t 点的增广链。
s
t
5
4
3
2
(3,0)
(5,3)
(1,1)
(5,1)
(1,1)
q
s2
=
4
q
5t
=
2
q
45
=
3
q
43
=
1
q
32
=
1
增广量
q
= min
q
ij
= min
(4,1,1,3,2)= 1
s
t
5
4
3
2
(3,1)
(5,4)
(1,0)
(5,2)
(1,0)
增广过程:前向弧 f'i