1、 运 筹 学 Operations Research Chapter 6 网络模型Network Modeling6.1 最小 (支撑 )树问题 Minimal (Spanning)Tree Problem6.2 最短路问题 Shortest Path Problem 6.3 最大流问题 Maximal Flow Problem6.4 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem Date长汉口汉阳武昌您能从 武汉理工大学出发走过每座桥且只走一次然后回到学校吗 ?汉江江再建一座 大桥呢汉阳 武昌汉口 DateCh6 网 络
2、模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page 3 5v1v2v3v4v5v6843752618图 6 1运筹学中研究的 图 具有下列特征：（ 1）用点表示研究 对 象，用 边 （有方向或无方向）表示 对象之 间 某种关系。（ 2） 强 调 点与点之 间 的关 联 关系，不 讲 究 图 的比例大小与形状。（ 3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（ 4）建立一个网络模型，求最大值或最小值。DateCh6 网 络 模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page
3、4 边用 vi,vj表示或简记为 i， j，集合记为如图 6 1所示，点集合记为边上的数字称为权，记为 wvi,vj、 wi， j或 wij，集合记为连通的赋权图称为网络图，记为G V， E， W5v1v2v3v4v5v6843752618图 6 1Date6.1 最小 (支撑 )树问题Minimal (Spanning)Tree ProblemDateCh6 网 络 模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page 6 6.1.1树的概念 一个无圈并且连通的无向图称为树图或简称树 (Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达
4、成一个树图 。 可以证明：（ 1）一棵树的边数等于点数减 1；（ 2）在树中任意两个点之间添加一条边就形成圈；（ 3）在树中去掉任意一条边图就变为不连通。 在一个 连 通 图 G中，取部分 边连 接 G的所有点 组 成的 树称 为 G的 部分 树 或支撑 树 (Spanning Tree )。 图 6 2是图6 1的部分树。 v1v2v3v4v5v6432 1图 6 276.1 最小树问题 Minimal tree problem DateCh6 网 络 模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page 7 6.1.2 最小部分树将网络图 G边上的权看作两点间的长
5、度（距离、费用、时间），定义 G的部分树 T的长度等于 T中每条边的长度之和，记为C(T)。 G的所有部分树中长度最小的部分树称为 最小部分树 ，或简称为 最小树 。 最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法 ：任取一圈，去掉圈中最长边，直到无圈。6.1 最小树问题 Minimal tree problem DateCh6 网 络 模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page 8 5v1v2v3v4v5v6843752618图 6 1【 例 6-1】 用破圈法求图 6 1的最小树。 图 6 4图 6 4就是图 6 1的最小部分树，最小
6、树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同 6.1 最小树问题 Minimal tree problem DateCh6 网 络 模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page 9 加 边 法 ：取 图 G的 n个孤立点 v1， v2， ， vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n 1条边） v1v2v3v4v5v64352 1图 6 5在图 6 5中，如果添加边 v1, v2就形成圈 v1, v2, v4，这时就应避
7、开添加边 v1, v2，添加下一条最短边 v3, v6。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等 5v1 v3 v515v2 v4 v684375268Min C(T)=156.1 最小树问题 Minimal tree problem【 例 6-2】 用加边法求图 6 1的最小树图 6 1DateCh6 网 络 模型Network Model制作与教学武汉理工大学 管理学院 熊伟 Page 10 下一节：最短路问题1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（ 1）破圈法（ 2）加边法作业：教材习题 6.1， 6.4， 6.56.1 最小树问题 Minimal tree problem Date
