OR10图与网络模型.pptx

1
§ 基本概念 P229-231
无向图:可以描述相互认识的关系
有向图:可以描述被认识的关系
优点:简单明了
名词:
点,vi
边,ei,无向
弧,ai,有向
无向图:点、边构成,
记,G=(V,E)
V,图G的点的集合
E,图G的边的集合
e2
V1
V2
V3
V4
V5
V6
e1
e3
e4
e5
V1
a1
V2
有向图:点、弧构成,
记,D=(V,A)
V,图D的点的集合
A,图D的弧的集合
2
链:点、边交错的序列
圈:起点也是终点的链
连通图:任意两点间有链
权:边上对应的数字,wij
赋权图:每条边都有权wij
路:点、弧交错的序列,同向
回路:起点也是终点的路

权:弧上对应的数字,cij
网络:每条弧都有权(容量cij), 指定一个发点、一个收点 其它为中间点。
e2
V1
V2
V3
V4
e1
e3
e4
V1
a1
V2
a2
V3
V4
a3
a4
V5
e5
发点
收点
3
§ 最短路问题
动态规划中解决的是阶段明显的最短路问题
1. Dijkstra 算法( 双标号法,适用条件:cij ≥ 0 )
每个点 vj 标号Lj :起点vs到本点的最短路长
两标号( Lj, kj ) 标号kj:此最短路上前一个点的下标
例1,最短路从V1 到V6
第1步,起点标号(0,s),
——起点之前没有别的点,用s 标示
第2步,找出所有已标号的点的集合,I = { v1 } ,
与I直接相连的未标号的点的集合J = { v2,v3,v4 }
所有I、J间的弧的集合,{ (v1,v2),(v1,v3),(v1,v4) }
(0,s)
v1
v2
v3
v4
v5
v6
3
2
5
2
7
1
5
3
5
1
第3步,计算每个J经过直接相连的I到起点的距离,
s12 = L1+ c12 = 0 + 3 = 3
s13 = L1+ c13 = 0 + 2 = 2
s14 = L1+ c14 = 0 + 5 = 5
第4步,确定最小的sij对应的未标号点,对其标号。
Min { s12、s13、s14 } = 2 , 对应v3,标号( 2, 1 )
到起点最短路长2,此最短路上的前点是v1
注意,如果Min对应2两个s,就加2个“(双标号)”
第5步,继续,直到在v6 上标号
(2,1)
(3,1)
(3,3)
(8,4)
4
应用举例:例2 电信公司准备在甲、乙两地沿路架设一条光缆线,问如何架设使其光缆线路最短?下图给出了甲乙两地间的交通图。权数表示两地间公路的长度(单位:公里)。
V1
(甲地)
15
17
6
2
4
4
3
10
6
5
v2
V7 (乙地)
v3
v4
v5
v6
5
v1
v2
v3
v4
v5
v6
v7
15
10
3
6
17
5
2
6
4
4
2. 最短路问题的应用
分析:无向图,边-可以看作两条方向相反的弧
也可以直接使用“双标号法”。
(0,s)
(10,1)
(13,3)
(14,3)
(16,5)
(18,5)
(22,6)
6
§ 最小树问题

树:无圈的连通图
1. 破圈法:找1个圈,去最大边,重复,直到无圈
2. 避圈法:连最小边,不要成圈,直到连上所有点
例4,P239
破圈法,
总长19
v1
v2
v3
v4
v5
v6
2
10
3
3
1
5
3
4
4
7
8
v7
7
例5:某大学准备对其所属的7个学院办公室计算机联网,这个网络的可能联通的途径如下图,图中v1,…,v7 表示7个学院办公室,请设计一个网络能联通7个学院办公室,并使总的线路长度为最短。
v1
3
3
1
7
2
8
5
4
10
3
4
v7
v6
v5
v4
v2
v3
图11-14
8
避圈法,
总长19
v1
v2
v3
v4
v5
v6
2
3
3
1
3
7
v7
9
§4. 最大流问题
定义,给定一个带有收点、发点的网络,求出
不超过每条弧容量前提下的网络最大流量。
:例6,石油公司铺管道,求最大流量P242 设,弧(vi,vj)中的实际流量fij
Max Z = f12 + f14
f12 = f23 + f25
f14 = f43+f46+f47
f23+f43 = f35+f36
f25+f35=f57
f36+f46=f67