当前位置:
文档之家› 韩伯棠管理运筹学(第三版)_第十一章_图与网络模型
韩伯棠管理运筹学(第三版)_第十一章_图与网络模型
25
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B 4 4 3 v6
8 D9
1 E7 ∞ v5
5 14 13 T 7
v7
由此而得两条从v 的最短路R 由此而得两条从 1到v7的最短路 7* : {v1, v2, v3, v6, v7}与{v1, v2, v3, v5, v6, v7} 与
§1 图与网络的基本概念
• 有向图:关联边有方向的图。 有向图:关联边有方向的图。 弧:有向图的边 a = ( u , v ),起点 u,终点 v; , , ; 的链,且各方向一致, 路:若有从 u 到 w 的链,且各方向一致,则称 的路; 之为从 u 到 w 的路;
u v
x
回路: 回路:起点与终点相同 的路. 的路
18
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B5 4 3 v6
∞ D
1 E ∞ v5
5 7
∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2
24
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B 4 4 3 v6
8 D9
1 E7 ∞ v5
5 14 13 T 7
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2
发点P标号, 发点P标号, 其余点T 其余点T标号 改为P标号 改为 标号 终点为P 终点为 标号
15
§2 最短路问题
如图是一个单向道路系统。 例 1 : 如图是一个单向道路系统 。 大批物资集中 在出发地S,要求用车尽快运输到目的地T。 A,B,C,D,E是中间站 是中间站。 A,B,C,D,E是中间站。图中数字为相邻两站间的路 程。
运筹学
第十一章 图与网络模型
1
第八章 图与网络模型
• 图与网最短路问络的基本概念 • 最小生成树问题 • 最大流问题 • 最小费用流问题
2
§1 图与网络的基本概念
哥尼斯堡七桥问题 哥尼斯堡(现名加里宁格勒)是欧 哥尼斯堡(现名加里宁格勒) 洲一个城市, 洲一个城市 , Pregei河把该城分成两部 河把该城分成两部 河中有两个小岛,十八世纪时, 分,河中有两个小岛,十八世纪时,河 两边及小岛之间共有七座桥, 两边及小岛之间共有七座桥,当时人们 提出这样的问题: 提出这样的问题 : 有没有办法从某处 ( 如 A)出发,经过各桥一次且仅一次 ) 出发, 最后回到原地呢? 最后回到原地呢?
20
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B 4 4 3 v6
8 D9
1 E7 ∞ v5
5 7
∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2
A 2 S 4 C 5 1 2 B 3 4 4 1 E
16
7 D 5 T
7
§2 最短路问题
v2 A ∞ 2 0 v1 S 4 C ∞ v4 5 2 1 4 7 v3 B ∞ 4 3 v6
∞ D
1 E ∞ v5
5 7
∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算:
22
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B 4 4 3 v6
8 D9
1 E7 ∞ v5
5 7
14 ∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2
8
§1 图与网络的基本概念
v2 e1 v1 e2 e3 v4
10 6 6 10 4 13 12 11 12 14
v5
9
3
v8
5
v3
v6
5 8
v10 v9
10 2
v7
•图 G(V,E): 图 ( , ): •V是顶点集合 是顶点集合,V={vi|i=1,…,n},E是边的集合 是边的集合,E={ej | j=1,…,m} 是顶点集合 , 是边的集合 的端点, 的关联边。 对于边 e3 =[v1, v4 ],v1, v4是e3的端点,e3 是v1, v4的关联边。 ,
6
A D C
B
Euler问题 Euler问题
一笔画 问题
§1 图与网络的基本概念
•图:由若干点以及点间联线构成(P229,230) 图 若干点以及点间联线构成( , ) •点:表示某一具体事物 。 点 •点间联线:表示事物之间某种特殊的关系。 点间联线:表示事物之间某种特殊的关系。 点间联线 不带箭头的点间联线。 边:不带箭头的点间联线。 有向边): 弧(有向边 :带箭头的点间联线。 有向边 带箭头的点间联线。 •无向图 无向图——由点,边构成(P229) 由点, 无向图 由点 边构成( ) •有向图 有向图——由点,弧构成。(P230) 由点, 有向图 由点 弧构成。 ) •网络(赋权图)——图中每一条边(弧)[vi ,vj], 网络( 图中每一条边 网络 赋权图) 图中每一条边( 有一常数w 与之对应, 称为边[ 上的权. 有一常数 ij与之对应,。wij称为边[vi ,vj]上的权. 常表示距离,费用,时间,容量等) (常表示距离,费用,时间,容量等)(P231) )
19
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B 4 4 3 v6
∞ D9
1 E ∞ v5
5 7
∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2
14
§2 最短路问题 Dijkstra算法
•求解的过程实际上是一种给点标号的过程。 求解的过程实际上是一种给点标号的过程。 求解的过程实际上是一种给点标号的过程 标号( 是给点记的一个数) 标号(数,是给点记的一个数) •临时标号(T标号)——从发点到本节点的 临时标号( 临时标号 标号) 从发点到本节点的 最短距离的上界; 最短距离的上界; •固定标号(P标号)——从发点到本节点的 固定标号( 固定标号 标号) 从发点到本节点的 最短距离。 最短距离。 某点T标号 某点 标号
3
A C ? D
只经过各桥一 次最后能回到 原地吗? 原地吗?
B
A C
只经过各桥一 次最后能回到 原地吗? 原地吗?
D ? B
§1 图与网络的基本概念
最 后 , 数 学 家 Euler ( 欧 拉 ) 1736年巧妙地给出了这个问题的 在 1736 年巧妙地给出了这个问题的 答案, 并因此奠定了图论的基础, 答案 , 并因此奠定了图论的基础 , Euler把 Euler 把 A 、 B 、 C 、 D 四块陆地分别 收缩成四个顶点, 收缩成四个顶点 , 把桥表示成连接 对应顶点之间的边, 对应顶点之间的边 , 问题转化为从 任意一点出发, 任意一点出发 , 能不能经过各边一 次且仅一次, 最后返回该点。 次且仅一次 , 最后返回该点 。 这就 是著名的Euler问题。 Euler问题 是著名的Euler问题。
9
§1 图与网络的基本概念
设 G1 = [ V1 , E1 ] , G2 = [ V2 , E2 ] 的子图; 子图: 子图:如果 V2 ⊆ V1 , E2 ⊆ E1 称 G2 是 G1 的子图; 真子图: 的真子图; 真子图:如果 V2 ⊂ V1 , E2 ⊂ E1 称 G2 是 G1 的真子图 生成图: 生成图:如果 V2 = V1 , E2 ⊂ E1 称 G2 是 G1 的生成图 部分图) (部分图)。
21
§2 最短路问题
v2 A2 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B 4 4 3 v6
8 D9
1 E7 ∞ v5
5 7
∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2
17
§2 最短路问题
v2 A2 ∞ 2 0 v1 S 4 C 4 ∞ v4 5 2 1 4 7 v3 B5 4 ∞ 3 v6
∞ D
1 E ∞ v5
5 7
∞ T
v7
Step1:令始点P(v1)=0, 其它点 j) = ∞ :令始点 其它点T(v Step2: 计算:T(vj) = min{T(vj) , P(vi)+wij} 计算: Step3: 令:P(vj) = min{T(vj)},返回 ,返回Step2