当前位置：文档之家 › 运筹学-第八章-图与网络

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

  • 格式：pdf
  • 大小：1.57 MB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

运筹学8图与网络分析

运筹学8图与网络分析


e3 。在剩下的图中，再取一个圈
定理8.7充分性的证明，提供了一个 寻找连通图支撑树的方法叫做“破圈法”。 就是从图中任取一个圈，去掉一条边。再 对剩下的图重复以上步骤，直到不含圈时 为止，这样就得到一个支撑树。
例8.4 用破圈法求出图8-11的一个支
撑树。
v2
e1
e7 e4
v1
e3 v4
e8
v5
e2
e5
v3
e6
图8-11
取一个圈(v1,v2,v3,v1)，在一个圈中去掉边
3
4
初等链：链中所含的 点均不相同, 也称通 路；
5
6
为闭链或回路或圈；
简单圈：如果在一个圈中所含的边均不相同 初等圈：除起点和终点外链中所含的点 均
不相同的圈；
连通图：图中任意两点之间均
至少有一条通路，否则 v1
v4 v5 v8
称为不连通图。
v2
初等链: (v1 , v2 , v3 , v6 ,
图的连通性：
简单链：链中所含的 边均不相同；
圈：若 v0 ≠ vn 则称该链为开链，否 则称
1
2
链：由两两相邻的点及其相 关联的边构成的点边序列。 如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,…,vn1 , en ， vn ; v0 ，vn 分别为链的起点和终点 。记 作（ v0 ,v1 , v2， ,v3 , …, vn-1 , vn ）
v5
v7
(v5
,v1v6),(v6
(v4 ,v6),(v5 ,v7)}
,v3),(v5
v6
,v4),
v2
v4
图8.5
下面介绍一些常用的名词：
运筹学 图与网络分析PPT学习教案

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


ij
min{ V1到Vj中间最多经过t-2个点 P1j（t-1）=
P1j（t-2）
+wij}
终止原则：
1）当P1j（k）= P1j（k+1）可停止，最短路P1j*= P1j（k） 2）当P1j（t-1）= P1j（t-2）时，第1再9页多/共迭59页代一次P1j（t） ，若P1j（t） =
P1j（t-1） ，则原问题无解，存在负回路。
图与网络模型Graph Theory
最短路问题
v1，u1 =（M，W，G，H）； v2，u2 =（M，W，G）；
v3，u3 =（M，W，H）；
v4，u4 =（M，G，H）；
v5，u5 =（M，G）。
此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
v1
v2
v3
v4
v5
u5
u4
例： 求下图所示有向图中从v1到各点 的最短路。
2 v1
v2
4
5 -2 v3 6
-3 4
v4
7
v6 -3 2
v5
3
4
v8
-1
v7
第20页/共59页
wij
d(t)(v1,vj)
v1 v2 v3 v4 v5 v6 v7 v8 t=1 t=2 t=3 t=4 t=5 t=6
v1 0 2 5 -3
0 0 0 00 0
参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加
此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此
问题。很快，各办事处将其已订购机票的情况传到了总社。根据此
资料，总社要作出计划，最多能将多少游客从成都送往北京以及如
何取道转机。下面是各办事处已订购机票的详细情况表：
运筹学 第八章 图论 - 全

运筹学 第八章 图论 - 全


(a)明显为二部图，(b)也是二部图，但不明显，改画为(c) 时即可看出。
2017/7/13 11
图与网络的基本知识
次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为 点vi的次（也叫做度），记作d(vi)。 右图中d(v1)＝４,d(v3)=5,d(v5)=1。次 为奇数的点称作奇点，次为偶数的
2017/7/13
18
图与网络的基本知识
有向图 无向图
道路
回路
链
圈
道路(边的方向一致)
2017/7/13 19
图与网络的基本知识
连通图
定义10 一个图中任意两点间至少有一条链相连，则称此图为 连通图。任何一个不连通图总可以分为若干个连通子图，每 一个称为原图的一个分图（连通分支）。
连通图
2017/7/13
边，对余下的图重复这个步骤，直至无圈为止。
２、避圈法：每次增加一条边，且与已有边不构成圈，直至恰 有n-1条边为止。
2017/7/13
24
树
例１、下图是某建筑物的平面图，要求在其内部从每一房间都能走到 别的所有的房间，问至少要在墙上开多少门？ 试给出一个开门的方案。
三
七
Байду номын сангаас
三 八 一 四 二 五
七 八 九 六
无向图
2017/7/13
有向图
8
图与网络的基本知识
环, 多重边, 简单图 如果边e的两个端点相重，称该边为 环。如右图中边e1为环。如果两个点 之间边多于一条，称为多重边，如右
v2 e5
多重边
e2
e1 v1
环
e3 v3
e4
图中的e4和e5，对无环、无多重边的
运筹学第八章--图与网络分析-胡运权

运筹学第八章--图与网络分析-胡运权

运筹学
赵明霞山西大学经济与管理学院
2
第八章 图与网络分析
图与网络的基本概念 树 最短路问题 最大流问题 最小费用最大流问题
3
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题
例8-9
28
基本步骤标号T(j)→P(j)

29
2017/10/26
30
最长路问题例8-10（7-9）设某台新设备的年效益及年均维修费、更新净费用如表。试确定今后5年内的更新策略，使总收益最大。
役龄项目
0
1
2
3
4
5
效益vk(t)
5
4.5
4
3.75
3
2.5
14
15
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题 充要条件：无向图中无奇点，有向图每个顶点出次等于入次
16
第二节 树
树是图论中的重要概念，所谓树就是一个无圈的连通图。
图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。
7
G=(V,E)关联边(m)：ei端（顶）点(n)：vi, vj点相邻(同一条边)： v1, v3边相邻(同一个端点)：e2, e3环：e1多重边： e4, e5
8
简单图：无环无多重边
多重图：多重边
9
完全图：每一对顶点间都有边（弧）相连的简单图
10
次（d）：结点的关联边数目d(v3)=4，偶点d(v2)=3，奇点d(v1)=4d(v4)=1，悬挂点e6, 悬挂边d(v5)=0，孤立点
（一）线性(整数)规划法
运筹学资料：8图与网络模型

运筹学资料：8图与网络模型


V2
3
2
5 V4
7 V6 5
2 1 31
5
V3
V5
12、有向图中还有“路”、“回路”的概念；
13、在一个赋权有向图中，若指定了一个发点(VS)和一
2021/1/1个1 收点（Vt），其余点为天道中酬勤间点，并把弧上的权值
4
称为对应弧的容量，这样的赋权有向图称为网络.
第二节 最 短 路 问 题 V2
5、若Vt 已标号，则说明Vs到Vt存在最短路，若Vt 未标号， 则说明不存在Vs到Vt最短路。 注意： 1、双标号法适用范围:权值非负的有向图
也适用于权值非负的无向图。
2、在选择Sij最小值时，若出现多个相等最小值且这些弧 (边)的终点为同一点，则此点应有多个标号，以便在最终 确定具体路径时可以找到多条最短路线。
最 短
3、计算2中所有弧对应的Sij值；Sij=Li+Cij，
路 。
S12=L1+C12 ＝0+3＝3 S14=L1+C14 ＝0+5＝5 S13=L1+C13 ＝0+2＝2 min(S12 , S13, S14)= S13 =2
则可知：L3 ＝2
给弧(V1,V3)中的未标号点V3标号（2,1）
7 V6
{(Vi,Vj )所有弧对应的Sij值；
Sij=Li+Cij，Li为从起点到Vi点的最短距离，
2021/1/11
Cij为弧(Vi,V天j)道的酬勤权；
9
第二节 最 短 路 问 题
4、选出各弧中Sij值最小者，对该弧上未标号点进行标号， 重复，直到2中弧的集合变为空集为止。
(8,4)
7 V6
(0,S)
运筹学图与网络分析-最短路

运筹学图与网络分析-最短路


(P0
)
min P
(P)
路P0的权称为从vs到vt的距离，记为d(vs,vt)。
求网络上的一点到其它点 的最短路
Dinkstra标号法
这是解决网络中某一点到其它点的最 短路问题时目前认为的最好方法。
适用于有向图权值非负的情况
有向图权值非负---- Dijkstra算法
Dijkstra算法的基本步骤（权值非负） 1、给顶点v1标号（0），v1称为已标号点，记标号点集为
(1,2)
2
2
0
1
2
5
7
(2,4)
3 5 55
7
3
1 (4,4) 3 1
4
6
7
(1,3)
5
④重复上述步骤，直至全部的
点都标完。
(1,2)
2
2
0
1
2
5
7
(2,4)
3 5 55
7
1
3
3
1
4
6
7
(1,3)
5
7
(1,2)
2
2
0
2
7
1
5
(2,4)
35
55
7
1
3
3
1
4
6
7
(1,3)
5
(3,7)
(1,2)
2
2
0
2
7
1
5 3 5 55 7
3
1
3 1
34 5 6
7
④重复上述步骤，直至全部的
(1,2)
点都标完。
2
2
0
2
7
1
5 3 5 55 7
运筹学-第八章-图与网络

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


河北工业大学管理学院 孔造杰 制作
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}
运筹学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
R820-运筹学-第8章 网络计划

R820-运筹学-第8章 网络计划

• 从起始节点开始沿箭线方向自左往右，通过一系列 箭线和节点，到达终点节点的通路，称为线路。
2. 紧前工作和紧后工作
• 紧前工作是指紧排在本工作之前的工作；且开始或完 成后，才能开始本工作。紧后工作是指紧排在本工作 之后的工作；本工作开始或结束后，才能开始或结束 的工作。如图11-3中，只有工作A 完成后工作B,C,D,E 才能开始，工作A 是B,C,D,E 的紧前工作；而工作 B,C,D,E 则是工作A 的紧后工作。
2
2.2 计算关系式 这些时间参数的关系可以用下图11-6表示工作的关 系状态。
TF i-j=LFi-j-EFi-j ESi-j 工作持续时间 D i-j i 工作 A 工作a的总时差 EFi-j 工作 A LFi-j 工作 A 的紧后工作 B ESj-k LSi-k EFj-k LFj-k 最早开始 最迟开始
⑦ 10 15 ⑧ 7 16
13
③
17
⑥
7
12
(d)
第2节 网络计划图的时间参数计算。
• 网络计划的时间参数计算有几种类型：双代号网络 计划有工作计算法和节点计算法；单代号网络计划 有节点计算法。以下仅介绍工作计算法。 网络图中工作的时间参数。它们是： • 工作持续时间(D)； • 工作最早开始时间（ES）； • 工作最早完成时间（EF）； • 工作最迟开始时间（LS）； • 工作最迟完成时间（LF）； • 工作总时差（TF）； • 工作自由时差（FF）。
表11-1
序号
1 2 3 4 5 6 7 8 9 10
工作名称
产品设计和工艺设计 外购配套件 锻件准备 工装制造1 铸件 机械加工1 工装制造2 机械加工2 机械加工3 装配与调试
工作代号
A B C D E F G H K L
运筹学：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中无奇点
运筹学 八章 图与网络分析

运筹学 八章 图与网络分析

向图。记之为G(D)。
链：设(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一个点弧交错序列，如果这个序
列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的 一条链。 1，均有ait=(vit,vit+1)，称之为从vi1到vik的一条路。
路：如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一条链，并且对t=1,2,…,k回路：若路的第一个点和最后一点相同，则称之为回路。
3)E中任意两条线之间除端点之外无公共点.
则由V、E构成的二元组合G=(V， E)就是图。 子图：已知图G1（V1，E1）若V1 ﹤V， E1 ﹤ E ; 图G=(V， E)的子图 则称图G1（V1，E1）是
若在图G中，某个边的两个端点相同，则称e是环。 多重边：图中某两点之间有多余一条的边，称之为多重边。 多重图：含有多重边的图。 简单图：无环、无多重边的图。
步骤 v1
例9：（图8－31）
v2 v3 v4 v5 v6 v7
v8
最短 前向 路 结点
1
2 3
0*
∞
4*
∞
6 6*
∞
∞ 9 9 9*
∞
∞ 8 8*
∞
∞ ∞ ∞ 13 13 *
∞
∞ ∞ ∞ 14 14 14*
∞
∞ ∞ ∞ ∞ ∞ 17
0
4 6 8 9 13 14 15 v1 v1 v2 v2 v5 v5
V7 6 4 V8 2 V9 4
6
V4 4 2 V5 3 V2
2
V6 4 V3
4
V1
一、最短路算法
1、情况一： wij≥0(Dijkstra算法) 原理：Bellman最优性定理 方法：图上作业法（标号法）；双标号法（表的形式） 标号：对于点V,若已求出V1到Vi的最短值，标号（αi,βi) αi ：表示V1到Vi的最短路值 βi:表示最短路中最后经过的点

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


运筹学教程
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，构造二重边。重复边 的总长：

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第8章 图与网络分析


（a）
（b）
（c）
图 8-9 图、子图、支撑子图
（4）图的同构 设 G1 与 G2 是两个同阶图，若顶点集合 V1 和 V2 以及边集 E1 和 E2 之间在保持关联性
质条件下的一一对应，则称图 G1 和图 G2 同构。 例如：图 8-10（a）和图 8-10（b）就为同构。
（a）
(b)
图 8-10 同构图
（10）定理 8.1 对于图 G=(V ,E) ，其中 V = n , E = m ,则有：
∑d (v) = 2m
（8-2）
v∈V
证明：每条边都有两个端点，在计算顶点的次时，每个端点都要计算对应边次，故共有
2m 次。
通俗地讲，就是线有两头，共有 2m 个线头的意思。
（11）定理 8.2 奇次顶的总数是偶数。
第八章 图与网络分析
8.1 图与网络的基本知识
8.1.1 图与网络的基本概念 8.1.1.1 图的定义 自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来描述。例如： 图 8-4 所示的我国北京、上海等十个城市间的交通图反映了这十个城市间铁路
分布情况。这里用点代表城市，用点和点之间的连线代表这两个城市之间有直通铁路。
图 8-7 一个无向图
G = (V, E) V= {v1, v2 ,v3 , v4} E={e1, e2 ,e3 , e4 ,e5 , e6 , e7}
其中
e1 = [v1 ,v2 ] , e2 = [v1 ,v2 ] , e3 = [v2 ,v3 ] , e4 = [v3 ,v4 ] ,
图 8-8 是一个有向图。该图可以表示为：
图 8-4 十个城市间铁路分布图
又如某单位储存五种化学药品，其中，某些药品是不能放在同一库房里的，为了反映这 种情况，可以用点 v1 、 v2 、 v3 、 v4 、 v5 分别代表这五种药品，若药品 vi 和药品 v j 是不能存 放在同一库房的，则在 vi 和 v j 之间连一条线，如图 8-5 所示。如果问题归结为寻求存放这种 化学药品的最少库房个数，则该问题就是染色问题。事实上，至少需要三个库房来存放这些 药品，即 v1 和 v5 、 v2 和 v4 、 v3 各存放在一个库房里。

运筹学_图与网络分析

1 3 4 5 2
2
3
6
7
2
1
课堂练习：
P224 2.a）

问题定义：在一个赋权图上求一个圈，经过图中每一条
边至少一次，使圈中各边权值的总和为最小。
中
v2 v5
国
邮 路
v3 v1 v6
v4
问
题
比如圈：v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5
欧拉链与欧拉圈 经过且仅经过图中每一条边一次的链称为欧拉链，经过 且仅经过图中每一条边一次的圈称为欧拉圈
若点与点之间的连线没有方向，称为边， 由此构成的图为无向图。记为: G=（V， E ）其中 V 是 G 的点的集合， E 为 G 的边的
v1
e2 v5 e5 e6 e9 e7 e4 e2 v5 e5 e7 e4
v2 e8 e3 e10
e1
集合，连接 Vi ， Vj 的边记为 [Vi ， Vj] 或 [Vj
，Vi] v3 v1 若点与点之间的连线有方向，称为弧，由 此构成的图为有向图。记为: D=（V， e1
v6
v4 v2 e6
e8 e3
A），其中 V是 G的点的集合，A为G的弧 的集合，一条方向为从 Vi指向Vj的弧记为 (Vi，Vj)
v6
v3
v4
相邻点：两点之间的边属于E
相邻边：如果两条边有一个公共端点
求从v1到v8的最短路
(3,5) V2 1
V5 (2,6)
10
4
3
V1 (0)
2
6
4
10
2
V6 (5,10)
V8
V4 (1,1)
V7 (5,9)
注：在给顶点编号时，如果在多个为标号点均取得 最小值Llk则对这多个点同时标号，这些点的第二个 标号相同，但是第一个标号不一定相同。

运筹学—第八章 图与网络分析


v5 1 v6 7 1 v7 －5 －3
e1 {v1 , v2 }
e3 {v2 , v3 }
e2 {v1 , v2 }
e4 {v3 , v4 } e6 {v3 , v5 } e8 {v5 , v6 } e10 {v1 , v6 }
e5 {v1 , v3 }
e7 {v3 , v5 } e9 {v6 , v6 }
v1
第二节 树 一、 树的概念和性质 例8.3 已知有六个城市，它们之间 要架设电话线，要求 任意两个城市均可以互相通话，并且电话线的总长度最短。
v1 v6 v5 v2
v3
v4
定义9 一个连通的无圈的无向图叫做树。
作为树T的定义，下列定义是等价的： （1）T是一个树。（设其顶点数为n ，边数为 m ） （2）T无圈，且m=n-1。 （3）T连通，且m=n-1 。 （4）T无圈，但在树中不相邻的两个点之间加上一条边， 那么恰好得到一个圈。 （5）T中任意两个顶点之间有且仅有一条链。 （6）T连通，但去掉T的任一条边，T就不连通。
( vi , v j )
一、 狄克斯屈拉(Dijkstra)算法 适用于wij≥0，给出了从vs到任意一个点vj的最短路。
算法步骤： 1.给始点vs以P标号 P(vs ) 0 ，这表示从vs到 vs的最短距离 T 为0，其余节点均给T标号， (vi ) (i 2 , 3,, n) 。 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 (vi , v j ) E ，且vj为T标号。对vj的T标号进行如下修改：
e1 v1
e2 e5
e8 v5
v2
d(v1)= 4，d(v6)= 4
e10 v6 e9
e3 e v4 4 e6 e7 v3

《运筹学》 第八章图与网络分析习题及 答案

《运筹学》第八章图与网络分析习题1.思考题(１)解释下列名词，并说明相互之间的区别与联系：①顶点，相邻，关联边；②环，多重边，简单图；③链，初等链；④圈，初等圈，简单拳；⑤ 回 路，初等路；⑥节点的次，悬挂点，孤立点；⑦）连通图，连同分图， 支 撑子图；⑧有向图，基础图，赋权图。

⑨子图，部分图，真子图．(２)通常用记号Ｇ＝（Ｖ，Ｅ）表示一个图，解释Ｖ及Ｅ的涵义及这个表达式 的涵义．(３)通常用记号Ｄ＝（Ｖ，Ａ）表示一个有向图，解释Ｖ及Ａ的涵义及这个表 达式的涵义．(４) 图论中的图与一般几何图形的主要区别是什么？ (５) 试述树与图的区别与联系．(６) 试述 求最短路问题的Ｄijkstra 算法的基本思想及其计算步骤． (７) 试述寻求最大流的标号法的步骤与方法．(８) 简述最小费用最大流的概念及其求解的基本思想和方法．(９) 通常用记号Ｎ＝（Ｖ，Ａ，Ｃ）表示一个网络，试解释这个表达式的涵义． (10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？ (11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。

2.判断下列说法是否正确(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。

(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。

(3) 如果一个图G 从V 1到各点的最短路是唯一的，则连接V 1到各点的最短路，再去掉重复边，得到的图即为最小支撑树。

(4 )图G 的最小支撑树中从V 1到V n 的通路一定是图G 从V 1到V n 的最短路。

(5) {f ij =0}总是最大流问题的一个可行流。

(6 )无孤立点的图一定是连通图。

(7) 图中任意两点之间都有一条简单链，则该图是一棵树。

(8) 求网络最大流的问题总可以归结为求解一个线性规划问题。

(9)在图中求一点Ｖ１到另一点Ｖn 的最短路问题总可以归结为一个整数规划问题 (10) 图G 中的一个点V 1总可以看成是G 的一个子图。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

② 9 ① 20 ③ 10
7
15 ④ 19 25 14 6 ⑥ 30 ⑤ 11 ⑦
起点为v1终点为v7的一个网络图
河北工业大学管理学院 孔造杰 制作 Page 11 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
树、支撑树： 无圈的连通图称为树； 若G1是G2的一个支撑子图并且是一 棵树，则称G1是G2的一棵支撑树。 图8－2(a)、8－2(b)都不是树。想一想，为什么？ 图8－3(a)是一棵树，图8－3(b)是图8－1的一棵支撑树。
【性质1】任何树中必存在次为1的点。 【性质2 】具有n个顶点的树的边数恰好为（n－1）条 【性质3 】任何具有n个点、(n－1)条边的连通图是树图。
最小树问题
河北工业大学管理学院 孔造杰 制作
Exit
Page 13 of 46
2003年9月13日12时46分
§8-2 最小树问题 Minimum Spanning Tree Problem
制作与教学 河北工业大学管理学院 孔造杰 kongzj@
Exit
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
引例：哥尼斯堡七桥问题
您能从A、B、C或D任意一点出 发走遍7座桥并且每座桥只走一 次最后回到原出发点吗？
D
A A D C C B
环，多重边，简单图 e2 e 如果边e的两个端点相重，称该边为环。 4 如图６－１中边 e1 为环。如果两个点之间 v2 e5 多于一条，称为多重边，如图６－１中的 e4和e5，对无环、无多重边的图称作简单图。 e6 次，奇点，偶点，孤立点 与某一个点 vi 相关联的边的数目称为点 vi 的次（也叫做度），记作 d(vi)。图６－１ 中 d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点 称作奇点，次为偶数的点称作偶点，次为0 的点称作孤立点。 图的次 一个图的次等于各点的次之和。
v1
8 4 3 8
v3 5 2
7
v5 1
5 v2 v1
v4 v3 4 2
6
v6 v5
5 1 Min C(T)=15 v6
Page 17 of 46
2 河北工业大学管理学院 孔造杰 制作
v
3
v4
2003年9月13日12时46分
§8-2 最小树问题 Minimum Spanning Tree Problem
② 9 ① 20 ③ 10
7
15 ④ 19 25 14 6 ⑥ ⑤
赋权图
河北工业大学管理学院 孔造杰 制作 Page 10 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
网络图 在一个有向赋权图G 中规定了一个起点（发点）和一个 终点（收点），其余是中间点，这样的图称为网络。
§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
作业：P283 10.4 10.5
最短路问题
河北工业大学管理学院 孔造杰 制作
Exit
Page 18 of 46
2003年9月13日12时46分
§8-3 最短路问题 Shortest Path Problem
最短路问题
最短路问题，就是从给定的网络图中找出一点到各点或任意两 点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某 些整数规划和动态规划的问题，也可以归结为求最短路的问题。 因此这类问题在生产实际中得到广泛应用。 求最短路有两种算法，一是求从某一点至其它各点之间最短离的 狄克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短 的矩阵算法。
v2 e6 v4
e2 e 4 e5 e7
e1 v1 e3 v3 e8 v5
图8－1
v2和v4是边e6的端点，反之边e6是点v2、v4的关联 边。点v2、v4相邻；边e6与e5、 e4j相邻。
河北工业大学管理学院 孔造杰 制作 Page 4 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
有向图 混合图
如果图的每条边都有一个方向则称为有向图 如何图G中部分边有方向则称为混合图
② ⑤ ① ③ 有向图 ④ ⑥
河北工业大学管理学院 孔造杰 制作
Page 9 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
赋权图 设图G＝（V，E），对G的每一条边(vi,vj)相应的有一条数w (vi,vj) (或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为赋权图。 这里的权数可以是时间、费用、距离等，视不同背景代表不同的 含义。
是一条回路并且是简单回路。
v2 e6 v4
e2 e 4 e5 e7
e1 v1 e3 v3 e8 v5
连通图
若在一个图中，如果每一对顶点之间至少存在一条链，称这样 的图为连通图，否则称该图是不连通的。图6－1是连通图。
河北工业大学管理学院 孔造杰 制作
Page 7 of 46
2003年9月13日12时46分
河北工业大学管理学院 孔造杰 制作 Page 6 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
µ 2＝{v5 , e8 , v3 , e7 , v4 }
是一条链也是一条路。
μ3={v4,e7,v3,e3,v1,e2,v2,e6,v4}
河北工业大学管理学院 孔造杰 制作
C
B
Page 2 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
图Ｇ可 定义为点和边的集合，记作
其中V ≠ φ
G ={ V , E}
式中 Ｖ 是点的集合， Ｅ 是边的集合。注意上面定义的 图Ｇ区别于几何学中的图。在几何学中，图中点的位置、线 的长度和斜率等都十分重要，而这里只关心图中有多少点以 及哪些点之间有线相连，如果给图中的点和边赋以具体的含 义和权数，如距离、费用、容量等，把这样的图称为网络图， 记作Ｎ。图和网络分析的方法已广泛应用于物理、化学、控 制论、信息论、计算机科学和经济管理等各个领域。
河北工业大学管理学院 孔造杰 制作 Page 3 of 46
2003年9月13日12时46分
§8-1 图的基本概念Basic Concepts of Graph
例如图8－1：
V = {v1 , v2 , L, v5 }, E = {e1 , e2 ,L, e8 }
e2可记作： e2 = [v1 , v2 ] 端点，关联边，相邻 若有边 e可表示为e=[vi,vj],称vi和vj是边e 的端点，反之称边 e为点 vi或vj的关联边。若 点 vi、vj 与同一边关联，称点 vi 和 vj 相邻；若 边ei和ej具有公共的端点，称边ei和ej相邻。 例如图8－1，
第八章 图与网络 Ch8 Graph and Network
§8-1 图的基本概念 Basic Concepts of Graph §8-2 最小树问题 Minimum Spanning Tree Problem §8-3 最短路问题 Shortest Path Problem §8-4 最大流问题 Maximum Flow Problem
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
河北工业大学管理学院 孔造杰 制作 Page 14 of 46
2003年9月13日12时46分
§8-2 最小树问题 Minimum Spanning Tree Problem
求最小树的方法：破圈法和避圈法 破圈法：任取一圈，去掉圈中最长边，直到2
7
v5 1
5 v2 v1
南岸
河北工业大学管理学院 孔造杰 制作 Page 20 of 46
2003年9月13日12时46分
§8-3 最短路问题 Shortest Path Problem
定义：设G＝[V,E]是一个无向图，对每一条边ei∈E有一个长度 C(ei) ≥0,G的任意支撑树T各条边的长度之和称为树T的 长度，记为C（T）。长度最小的支撑树称为最小树。 求最小树是在一个无向连通图G中求一棵最小支撑树。 求最小树问题的应用： ¾ 电信网络（计算机网络、电话专用线网络、有线电视网络等 等）的设计 ¾ 低负荷运输网络的设计，使得网络中提供链接的部分（如铁 路、公路等 等）的总成本最小 ¾ 高压输电线路网络的设计 ¾电器设备线路网络（如数字计算机系统）的设计，使得线路总 长度最短 ¾ 连接多个场所的管道网络设计
µ = {v0 , e1 , v1 , L, ek , v k }