当前位置：文档之家 › 运筹学第八章图与网络分析PPT课件

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

  • 格式：ppt
  • 大小：640.00 KB
  • 文档页数：68

下载文档原格式

  / 68

合集下载

8图和网络分析.ppt

8图和网络分析.ppt

v4 v6
(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) }
v3
v5
图2
4、一条边的两个端点是相同的,那么称为这条边是环。
5、如果两个端点之间有两条以上的边，那么称为它们 为多重边。
6、一个无环，无多重边的图称为简单图，一个无环， 有多重边的图称为多重图。
（二）、 图的矩阵表示
对于网络（赋权图）G=（V，E），其中边 (vi , v j )
有权
w
i
，构造矩阵
j
A，(ai其j)n中n ：
aij 0wij
(vi ,vj)E (vi ,vj)E
称矩阵A为网络G的权矩阵。
设图G=（V，E）中顶点的个数为n，构造一个
矩阵 A(ai，j)n其n 中：
aij 01
其余的点称为中间点。对每一条弧
，(v对i ,v应j)一A个
数 ，称为弧w i 上j 的“权”。通常把这种赋权的图称为
网络。
10、由两两相邻的点及其相关联的边构成的点边序列称 为链。
如:v0 ，e1，v1，e2，v2，e3 ， v3 ,…,vn-1 , en ， vn， 记作（ v0 ， v1 ， v2， v3 , …, vn-1 ， vn ），
e1{v1,v2} e2{v1,v2}
v6
e3 {v2,v3} e4 {v3,v4}
e9
e5 {v1,v3} e6 {v3,v5}
e7 {v3,v5} e8 {v5,v6}
e9 {v6,v6} e10{v1,v6}
e1
e2
v2
e5 e3 e4 v4
e8
e6

运筹学胡运权第五版课件

运筹学胡运权第五版课件

V5 12 7
5
4
3
2
0
1 3
1
0 4
3
4 0
v7 ∞ 10 10 8
⑶ 构造任意两点间最多可经过3个中间点到达 的最短距离矩阵 D（2）= dij（2） 其中 dij（2）= min { dir（1）+ drj（1）}
r
i
dir
（1）
r
drj（1）
j
v1 v2 v3 v4 v5 v6 v7
• • •
悬挂边 孤立点 偶点 奇点
悬挂点的关联边，如 e8 次为0的点 次为偶数的点，如 v2 次为奇数的点, 如 v5
5、链：图中保持关联关系的点和边的交替序列，其 中点可重复，但边不能重复。 路：点不能重复的链。 圈：起点和终点重合的链。 回路：起点和终点重合的路。 连通图：任意两点之间至少存在一条链的图。 完全图：任意两点之间都有边相连的简单图。 n(n 1) 2 n阶完全图用Kn表示，边数= C n
狄克斯屈拉算法
既可以求两点之间的最短 距离，又可以确定最短路
求某两点之间的最短距离
（0）= V2 D
5
2
∞ ∞ ∞ ∞
5
0
∞ 2
7 0 2 7
7
6
∞ ∞
∞ ∞ 2
V3 2
∞ 0
∞ 4
V4 ∞ 2
V5 ∞ 7
∞ 6
0
1
1
0 6
3
6 0
V6 ∞ ∞ 4
v7 ∞ ∞ ∞ ∞ 3
注意：D(0)是一个对称矩阵，且对角线上的元素全是0.
⑵ 构造任意两点间直接到达、或者最多经过1 个中间点到达的最短距离矩阵D（1）= dij（1） 其中

管理运筹学 图与网络分析PPT教案

管理运筹学 图与网络分析PPT教案

v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
第27页/共83页
支撑树的权：如果T=(V,E)是G的一个支撑树，则称E中所 有边的权之和为支撑树T的权，记为w(T)。即
w(T )
wij
[vi ,v j ]T
v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
上例中支撑树的权为 3+7+5+2+2+3+4=26
第34页/共83页
v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
第35页/共83页
课堂练习：1.分别用三种方法求下图的最小支撑树
v2
7
v5
5
2
3
4
v1
4
5
v4 3
1
1
v7
7
4
v3
v6
第36页/共83页
2. 某农场的水稻田用堤埂分割成很多小块。为了 用水灌溉，需要挖开一些堤埂。问最少挖开多少条 堤埂，才能使水浇灌到每小块稻田？
水源
第37页/共83页
作业 P221： 第3题
第38页/共83页
§3 最短路问题
1. 问题的提出 2. 最短路问题的Dijkstra算法 3. 求任意两点之间最短距离的矩阵算法

运筹学图与网络分析PPT.

运筹学图与网络分析PPT.
第八章 图与网络分析
图与网络的基本概念 树 最短路问题 最大流问题 最小费用最大流问题
1
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题
哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题
2021/12/24
2
第一节 图与网络的基本概念
图是由点和边构成，可以反映一些对象之间的关系。
12
连通图：若任何两个不同的点之间，至少存在一条链，则 G为连通图。
赋权图：对一个图的每一条边（弧）(vi,vj)，相应地有一 个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 网络：赋权连通图 ➢无向图：开链即开路，闭链即回路 ➢有向图：弧的方向与链的方向一致。
2021/12/24
例如：在一个人群中，对相互认识这个关系我们可以用图 来表示，图8.1就是一个表示这种关系的图。
(赵v1)
e2
(v3)孙
e1
e3
(v2)钱 (v5) 周
e4 (v4) 李
e5 (v6)吴
(v7)陈
图8.1
3
描述对象之间关系， 研究特定关系之间的内在规律， 图中点的相对位置如何、点与点之间联线的长短曲直，对于
v1
v2
v8
v3
v4
v9
v5
v7
v6
(c)
图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是 树， (c)因为不连通所以也不是树。
15
树的基本性质 1. 任意两点间有且仅有一条链 2. 不相邻两点间添加一条边，有且仅有一个圈 3. 任意去掉一条边，得不连通图. 4. 存在悬挂点 5. m=n-1
反映对象之间的关系并不是重要的。

运筹学-第八章-图与网络

运筹学-第八章-图与网络

河北工业大学管理学院 孔造杰 制作
Page 16 of 46
2003年9月13日12时46分
§8-2 最小树问题 Minimum Spanning Tree Problem
加边法：去掉G中所有边，得到n个孤立点；然后加边； 加边的原则：从最短边开始添加，加边的过程中不能形成圈， 直到连通（n－1条边）。
§8-1 图的基本概念Basic Concepts of Graph
子图、支撑子图
图G1={V1、E1}和图G2={V2，E2}如果 V1 ⊆ V2和E1 ⊆ E2 称G1是G2的一个子图。若 有 V1＝V2，E1 ⊆ E2 则称 G1是G2的一个支撑 子图（部分图），图8-2（a）是图 8-1的一 个子图，图8-2（b）是图 8-1的支撑子图， e1 注意支撑子图也是子图,子图不一定是支撑 子图。 v2 e6 v4
e2 v2 e6 v4
e1 v1 e3 e4 e5 e7
e2 v3 e8 v5 v2
v1 e3 v3 v2
e2
v1 v3
e6 v5 v4
e7
图6－3(b)
e8 v5
图8 －1
图6－3(a)
河北工业大学管理学院 孔造杰 制作
Page 12 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
河北工业大学管理学院 孔造杰 制作
C
B
Page 2 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
图Ｇ可 定义为点和边的集合，记作
其中V ≠ φ
G ={ V , E}

运筹学图与讲义网络分析

运筹学图与讲义网络分析

v2 2
v4
3
v1
1
4
2
2
v6
5 v3 4
2 v5
解：（1）首先给v1以P标号，给其余所有点T标号。
P(v1)0 T ( v i) ( i 2 ,3 , ,6 )
（2）T ( v 2 ) m T ( v 2 ) , P i ( v 1 n ) l 1 ] [ 2 m ,0 i 3 ] n 3[
（二）、 图的矩阵表示
对于网络（赋权图）G=（V，E），其中边 (vi , v j )
有权
w
i
，构造矩阵
j
A，(ai其j)n中n ：
aij 0wij
(vi ,vj)E (vi ,vj)E
称矩阵A为网络G的权矩阵。
设图G=（V，E）中顶点的个数为n，构造一个
矩阵 A(ai，j)n其n 中：
aij 01
v4
A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , v1
v6
(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) }
v3
v5
图2
4、一条边的两个端点是相同的,那么称这条边是环。
5、如果两个端点之间有两条以上的边，那么称它们为 多重边。
v4
e11 e4
v6
e5
v5
(a)
v2
e1
e8
v1
e7
e6
v7
v6 e5
v5
(b)
子图
v2
v3
e1
e9
v1
e7
e10
e6
v7 e11

运筹学8图与网络分析

运筹学8图与网络分析
（8）考察V8点，只有一个T标号，T(V8)=15，令P(V8)=15)，记录路 径（V7，V8），计算结束。
反推得最V1至V8的最短路为V1→V2 →V5 →V7 →V8,路长15。
8.2 最短路问题
一、Dijkstra算法：求无负权网络最短路问题。
计算步骤：
（1）给Vs以P标号，P（Vs）=0，其余各点给T标号， T（Vi）=+∞；
且仅得一个圈。
4）图中边数为：p-1（p为顶点数）
8.1 图与网络基本知识
例8-4：一个班级的学生共计选修A、B、C、D、 E、F六门课程，其中一部分人同时选修D、C、A， 一部分人同时选修B、C、F，一部分人同时选修 B、E，还有一部分人同时选修A、B，期终考试 要求每天考一门课，六天内考完，为了减轻学生 负担，要求每人都不会连续参加考试，试设计一 个考试日程表。
（2）若Vi点为刚得到P标号的点，考虑点Vj: (Vi,Vj) 属于E，且Vj为T标号。则修改T(Vj)
T(Vj)=min[T(Vj),P(Vi)+lij]；
（3）比较所有T标号的点，把最小者改为P标号，即： P（Vi）=min[T(Vi)] 当存在两个以上最小者时，可同时改为P标号。
8.2 最短路问题
8.1 图与网络基本知识
三、有向图的有关概念:
有向图：
由点和弧组成。表示为：D=（V，A）
V--点集合 A--弧集合
始点和终点： 对弧a=(u，v)， u为a的始点，v为a的
终点。
链（道路）：
点弧交错序列。
圈（回路）：
如一条链中起点和终点重合。
初等链（道路）： 链中无重复的点和弧。
（3） 考察V5V6和V5V7两边： T(V6)=min[T(V6),P(V5)+l56]=min[+∞,8+5] =13 T(V7)=min[T(V7),P(V5)+l57]=min[+∞,8+6] =14

运筹学：chap8_图与网络分析

运筹学：chap8_图与网络分析

X={1}
P1=0
T2=2
2
6
1
2
3
1
10
5
9
3 T4=1 4
7
5
6
5
2
3
4
6
7
4
T6=3
min {T2, T4, T6}=min {2,1,3}=1
X={1,4}, P4=1
8 8
X={1,4}
P1=0
T2=2
2
6
1
2
3
1
10
P4=1
5
9
3
4
7
5
6
5
2
3
4
6
7
8
4
8
T6=3
T7=3
min {T2,T6, T7}=min {2,3,3}=2
■悬挂点： d(v)=1 对应的边为悬挂边
■孤立点： d(v) =0
e1
v5
v4
■奇点： d(v)为奇数 ■偶点： d(v)为偶数
v2
有向图：
e2
v1
e4
e3
e6
e5
v3
■出次 d+(v)：以v为始点的边数 d (v) d (v)
■入次 d-(v)：以v为终点的边数 vV
vV
次的定理1
定理1：任何图中，顶点次数的总和为边数的2倍。 证明思路：每条边必与两个顶点关联
d(v) 2m
vV
次的定理2
定理2：任何图中，奇点必为偶数个
证明思路：
d(v) d(v) 2m
vV1
vV2
Euler图的充要条件
定理3：无向连通图G是Euler图的充要条件是： G中无奇点

精选运筹学课件第八章图与网络分析资料

精选运筹学课件第八章图与网络分析资料

运筹学教程
v2
v6
e3
v3 e7
v5
运筹学教程
V= （ v1， v2，…... v6） E= （ e1， e2，…... e8） （e1）= （v1， v2） （e2）= （v1， v2） （e7）= （v3， v5） （e8）= （v4， v4） (e8)= (v4， v4),称为自回路(环)； v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为 4，顶点v4的次为4。
2l23+ 2l36+ l69+ l98+ l23+ 2l87+ 2l74+ l41+ l12=51
运筹学教程
第二步：调整可行方案，使重复边最多为一次
重复边 的总长：
v3
l69+ l98+ l41+ l12=21
5
v2
第三步：检查每个初等圈是否 5
v1
定理条件2，如果不满足，进行
2 v6 4 v9
例：求解网络的中国邮路问题
运筹学教程
v3
5
v2
5
v1
2 v6 4 v9
3
3
6 v5 4 v8
4
4
9
v4 4 v7
v3
5
v2
5
v1
2 v6 4 v9
3
3
6
v5 4 v8
4
4
9
v4 4 v7
第一步：确定初始可行方案
先检查图中是否有奇点，如果无奇点，为欧拉图；如果
有奇点，图中的奇点的个数比为偶数个，所以可以两两 配对，构造二重边。图中有4个奇点，v2,v4,v6,v8,配对 v2-v4,v6-v8，构造二重边。重复边 的总长：

运筹学图与网络分析

运筹学图与网络分析
v6
07
含有奇点的连通图中不含欧拉圈，此时，最优的邮递路线是什么呢？
08
求解中国邮路问题的奇偶点图上作业法
奇偶点表上作业法
奇偶点表上作业法 (1)找出奇点(一定为偶数个)，在每两个奇点之间找一条链，在这些链经过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是不一定是路线最短的，所以需要检验和调整。 (2)检验增加的边的权值是否是最小的。 定理3 假设M是使得图G中不含奇点的所有增加边，则M是权值总和为最小的增加边的充分必要条件是： 1)图G中每条边上最多增加一条边； 2)在图G的每个圈上，增加的边的总权值不超过该圈总权值的一半。 如果上述两个条件都满足则已经找到权值最小的欧拉圈 否则转入3) 3)调整增加边。如果1)不满足，则从该条边的增加边中去掉偶数条； 如果2)不满足，则将这个圈上的增加边去掉，将该圈的其余边上添加增 加边，转入(2)
v1
v2
v3
v4
v5
v1
v2
v3
v4
v5
图2
图3
如果在比赛中： A胜E， B胜C， A胜D， C胜A， E胜D， A胜B，
v1
v2
v3
v4
v5
注：本章所研究的图与平面几何中的图不 同，这里我们只关心图有几个点，点与点 之间有无连线，两条线有无公共顶点，点 与线是否有关联，至于连线的方式是直线 还是曲线，点与点的相对位置如何都是无 关紧要的。
求从v1到v8的最短路
(0)
(1,1)
(1,3)
(3,5)
(2,6)
(5,10)
(5,9)
(5,12)
注：在给顶点编号时，如果在多个为标号点均取得最小值Llk则对这多个点同时标号，这些点的第二个标号相同，但是第一个标号不一定相同。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
34
定理1 在一个图中，所有顶点次的和等于边的两倍。 定理2 在任意一个图中，次为奇数的顶点必为偶数 个。 定义6：有向图中，以vi为始点的边数称为点vi的出 次，d+(vi); 以vi为终点的边数称为点vi的入次，d-(vi); 所有顶点的入次之和=所有顶点的出次之和；
35
3、子图 定义：设G=（V，E）和G1=（V1，E1）。
如果V1 V， E1 E则称G1为G的子图； 如果G1 =（ V1，E1 ）是G=（V，E）子图， 并且V1 = V，则称G1为G的生成子图；
36
v1 e1
e5 e3
e4
e7 v4
e8
v2
v3
e2
e6
v5
37
（a）
v1
v2
的子图
e1
e5 e3
v4
v5
38
（a）的生 v1 成子图
e5
v2
v3
e2
e6
v4
v5
e8
39
二、连通图
定义8:如果图中的某些点、边可以排列成点和边的交错序列 (v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,…,vn-1 , en ， vn ） ，ei=(vi-1,vi)，则称 此为一条链。 由两两相邻的点及其相关联边构成的点边序列。 初等链：链中无重复的点和边； 定义9：无向图中，如一条链中起点和终点重合，则称此链为 圈。 初等圈：圈中无重复的点和边； 有向图中，当链（圈）上的边方向相同时，为道路（回路）。
个城市，Pregei河把该城分成两部分，河中 有两个小岛，十八世纪时，河两边及小岛之 间共有七座桥，当时人们提出这样的问题： 有没有办法从某处（如A）出发，经过各桥 一次且仅一次最后回到原地呢？
5
A C
B
D
6
最后，数学家Euler在1736年巧妙地给出 了这个问题的答案，并因此奠定了图论的基 础，Euler把A、B、C、D四块陆地分别收缩 成四个顶点，把桥表示成连接对应顶点之间 的边，问题转化为从任意一点出发，能不能 经过各边一次且仅一次，最后返回该点。这 就是著名的Euler问题。
32
e1
v1
e2
e5
e6
v4 e4
e8
v2 e3
v3 e7
v6
v5
33
V= （ v1， v2，…... v6） E= （ e1， e2，…... e8） （e1）= （v1， v2） （e2）= （v1， v2） （e7）= （v3， v5） （e8）= （v4， v4） (e8)= (v4， v4),称为自回路(环)； v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为 4，顶点v4的次为4。
7
A D
C
B
8
例：哈密顿（Hamilton）回路是十九世 纪英国数学家哈密顿提出，给出一个正 12面体图形，共有20个顶点表示20个城 市，要求从某个城市出发沿着棱线寻找 一条经过每个城市一次而且仅一次，最 后回到原处的周游世界线路（并不要求 经过每条边）。
9
10
11
12
13
14
15
29
环（自回路）：一条边的两个端点如果相同。 两个点之间多于一条边的，多重边。 定义2：不含环和多重边的图，简单图。
含有多重边的图，多重图。 有向图中的两点之间有不同方向的两条边，不是多重边。
简单图
30
定义3：每一对顶点间都有边相连的无向简单图，完全图。
有向完全图：指每一对顶点间有且仅有一条有向边的简单 图。
点击此处输入
相关文本内容
概述二
点击此处输入
相关文本内容
概述三
点击此处输入
相关文本内容
2
第二阶段是从十九世纪中叶到二十世纪 中叶，这时，图论问题大量出现，如 Hamilton问题，地图染色的四色问题以 及可平面性问题等，这时，也出现用图 解 决 实 际 问 题 ， 如 Cayley 把 树 应 用 于 化 学领域，Kirchhoff用树去研究电网络等.
3
第三阶段是二十世纪中叶以后，由生产管理、 军事、交通、运输、计算机网络等方面提出 实际问题，以及大型计算机使大规模问题的 求解成为可能，特别是以Ford和Fulkerson 建立的网络流理论，与线性规划、动态规划 等优化理论和方法相互渗透，促进了图论对 实际问题的应用。
4
例：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一
定义4:图G=(V,E)的点集V可以分为2个非空子集X,Y，使得 E中每条边的两个端点必有一个端点属于X，另一个端点属 于Y，G为二部图（偶图），有时记为： G=(X,Y,E)
X
YV1V3V2V4312、顶点的次 定义5：以点v为端点的边的个数称为点v的次，记作d(v), 如次为零的点称为弧立点； 次为1的点称为悬挂点。悬挂点的边称为悬挂边。 次为奇数的点称为奇点，次为偶数的点称为偶点。 偶点：d(v)=偶数； 奇点：d(v)=奇数；
16
17
18
19
20
21
22
23
24
25
26
图的基本概念
图论是专门研究图的理论的一 门数学分支，主要研究点和线之间的 几何关系。
27
第一节 图与网络的基本知识
一、图与网络的基本概念
1、图及其分类 定义1：（图）一个图由点集V和V中的元素无序对的一个 集合，记为 G=（V，E） 其中：V= （ v1， v2，…... vm）是m个顶点集合；
第八章 图与网络分析
引言 图论是专门研究图的理论的一门数学分
支，属于离散数学范畴，与运筹学有交叉， 它有200多年历史，大体可划分为三个阶段： 第一阶段是从十八世纪中叶到十九世纪中叶， 处于萌芽阶段，多数问题围游戏而产生，最 有代表性的工作是所谓的Euler七桥问题，即 一笔画问题。
1
整体概述
概述一
E= （ e1， e2，…... en） 是n条边集合。 当V和E为有限集合时，G为有限图。 2个点u,v属于V，如果边(u,v)属于E， u,v相邻； u,v为边(u,v)的端点。
28
具有公共端点u的两条边，称为点u的关联边。
如果任一边(u,v)属于E且端点无序，无向边；图G为无向图。 如果任一边(u,v)属于E且端点有序，有向边；图G为有向图 m(G)= E ，表示图G的边数； n(G)= V ，表示图G的点数；
40
链、初等链、初等圈
道路、回路
Q 1v1e1v2e7v5e8v2e5v4 链
道路
Q 2v1e1v2e2v3e4v4 初等链 道路
Q 3v1e1v2e5v4e6v5e9v1 初等圈 回路