运筹学第五章 图与网络分析

④ A= {v1,v2 , v3， v4}
网络的生成树和线性规划的关系
■网络的一个生成树对应于线性规划的 一个基
■生成树上的边对应于线性规划的基变 量
■生成树的弦对应于线性规划的非基变 量
■生成树的变换对应于线性规划单纯形 法的进基和离基变换
破圈法举例
4
7 1
3
2 24
4
3
5 3
7
6
2
4
7
5 1
间的关系.
e1
v1
e2
v2
e5e3e6Fra biblioteke7 v4
e4
v3
子图：图的一部分，记为Ｇ１．
G1 (V1, E1), 其中V1 V , E1 E。
e1
v1
e2
v2
e5
e3
e6
e7 v4
e4
v3
图Ｇ
v1
e2
v2
e5
e3
e6
v4
e4
v3
图Ｇ１
多重边：两节点之间有多于一条边。
环：首尾相接的边
简单图：无环、无多重边的图。 2.有向图与无向图 ❖有向图：有方向的图。 ❖无向图：无方向的图。
问题：求网络中一定点到其它点的最短路。
5.3.1 最短路问题的Dijstra解法 方法：给vi点标号[αi,vk] 其中：αi：vi点到起点vs的最短距离
vk: vi的前接点
方法：(1) 给起点vs标号[0，vs]。 （2）把顶点集v分为互补的两部分A和Ā
其中：A：已标号点集 Ā：未标号点集
、时间、费用、容量等）， 1
4
则称这样的连通图为网络图 。
20
45
3
❖典例: 会议日程安排
某单位要在今后的三天内召开6个会议,每天 上下午各安排一个会议，参加会议的领导如 下∶
会议A: 朱、马、牛、姬、江、姚 会议B: 朱、杨、张、江 会议C: 马、姬、侯、王、姚 会议D: 朱、姬、张 会议E: 杨、侯、王 会议F: 刘、杨、王、江、姚
3.关联与相邻
❖关联(边与节点的关系):若e是v1、v2两节点间
的边，记e=[v1，v2 ]，称v1、v2 与e关联。
v1
e
v2
❖相邻（边与边、节点与节点的关系）：
点v1与v2有公共边，称节点v1与v2相邻；
边e1与e2 有公共节点，称边e1与e2相邻。
e1
V2
V1
e2
V3
4. 链、圈与连通图
■链:由图G中的某些相连的边构成的图形（首尾
2）把顶点集V分为互补的两部分 A,Ā，其中：
A：与已选边相关联的点集 Ā ：不与已选边相关联的点集
3) 考虑所有这样的边[vi,vj]，其中 vi∈A,vj∈Ā,挑选其中权最小的。
4）重复3），直至全部顶点均属于A即 可。
❖例２：用避圈法求图的最小 V1 支撑树。
3 V2 4
5 V3 1
7 V4
第5章 图与网络分析
第５章 图与网络分析
５.１基本概念 ５.２最小支撑树问题 ５.３最短路问题 ５.４最大流问题
5.１ 基本概念
1.图、子图与简单图
图：由节点和线组成的图形．
记为： G = ( V, E )
V={v1,v2,…,vm}—节点集,表示研究对象.
E={e1,e2,…,en}—边集，表示研究对象之
第二天 会议C
B
第三天 会议D
F
5.2 最小支撑树问题
C1 根
C2
C3
C4
叶
❖树：无圈的连通图，记为T。
❖树的性质
■ 树中任意两个节点间有 且只有一条链。
2
3
1
5
4
■ 在树中任意去掉一条边， 1
则不连通。
2
3
5
4
■如果树T有m个节点，则 边的个数为m-1。
2 1
3 5
4
❖图的支撑树
图G1和G2 的节点相同，但图G1边的集合包 含于G2边的集合，且 G1是树图，则 图G1 是G2 的支撑树。 一个图的支撑树不是唯一的。
8
①任选点v1，挑与之相关 联的权最小的边（ v1,v4） ②. A= {v1,v4},Ā={v2,v3}
3 V2 7
V1
4 V4
5
8
V3
从边（ v1,v2）,（ v1,v3）, （ v4,v2）, （1 v4,v3） 中选权最小的边（ v1,v2）。
③A= {v1,v2 ,v4},Ā={v3}
从边（ v1,v3）, （ v2,v3）, （ v4,v3） 中选 权最小的边（ v2,v3）。
每位领导每天最多只参加一个会议。会议A要 安排在第一天上午,会议F安排在第三天下午， 会议B要安排在任何一天的下午。试根据上述 要求排出一个会议日程表，使各位领导都能 参加相应的会议
解: 用节点表示会
A
B
议，若两个会议能
安排在一天，
F
则用连线连接。
EC
D
会议日程安排如下:
上午
下
午
第一天 会议A
E
图 G1
图 G2
❖最小支撑树 树枝总长最短的支撑树。 特点：各节点都连通且线路总长
最短．
❖最小支撑树的求法
1 破圈法 2 避圈法
5.2.1 求解最小支撑树问题的破圈法
❖方法：去边破圈的过程。 ❖步骤：1）在给定的赋权的连通图上任找
一 个圈。 2）在所找的圈中去掉一条权数最
大的边。 3）若所余下的图已不含圈，则计
v6
8 v5
v2
1
3
v1
3
v7
3 v6
v3 7
2
v4
v5
权和＝１９
例４ 电话线网架设问题
某６个城市之间的道路网如图所示．要 求沿着已知长度的道路联结６个城市的 电话线网，并使电话线的总长度最短．
v3
5
6
v1
1
7
5
v2
2
v5 3
v4
4 v6
4
v3
v1 1
5 v2
v5
3
v6
4
2
v4
权和＝１５
5.3 最短路问题
算结束，余下的图即为最小支撑 树，否则返回 1）。
❖例１：用破圈法求右图 的最小支撑树。
V2
V2
V1
V4 V1
V3
V3
总权数=3+4+1=8
3 V2 7
V1
4 V4
5
8
V3
1 V2
V4 V1
V4
V3
V2
V1
V4
V3
5.2.2 求解最小支撑树的避圈法
❖方法：选边的过程。 ❖步骤：1）从网络中任意选一点vi，找出 与vi相关联的权最小的边[vi,vj]，得第二个 顶点vj。
2
6
避圈法举例
4
7 1
3
2 24
4
3
5 3
6
2
4
7
5 1
2
6
例３ 校园局域网问题
某大学准备把所属７个学院办公室的计 算机联网．这个网络的可能联通的途径 如图所示．边上权数为这条边的长度， 单位为百米．试设计一个网络联通７个 学院办公室，并使总长度为最短．
v2
1
v3
3 4
v1
3
v7 5
7
2
v4
10 3 4
不能相接），称为图G中的一条链。
如：μ ={(1,2),(3,2),(3,4)}
2
1
4
■圈 3
封闭的链称为圈 2
如：μ={(1,2),(2,4),(3,4),(1,3} 1
4
3
■连通图
任意两个节点之间至
2
少有一条链的图称为连
1
4
通图
3
5.网络图
给图中的节点和边赋以
具体的含义和权数（如距离
2
50
70