9-图论.ppt

* 9 图与网络优化（重点章节） 1.?????? 本章学习要求 (1)??? 应熟悉的内容 a.?????? 图与网络的基本概念 b.?????? 中国邮递员问题（欧拉回路、欧拉图） c.?????? 最小费用最大流 (2)??? 应掌握的内容 a.?????? 树图 (a) 树的定义、性质、最小生成树定义 (b) 最小生成树的寻求（破圈法和避圈法） (3)??? 应熟练掌握的内容 a.?????? 最短路径问题的DIJKSTRA算法 b.?????? 最大流问题（增广链）的标号算法 2.?????? 本章重点难点分析 ?? 重点：最短路径问题，最大流问题标号算法 ?? 难点：最大流最小割定理，最大流问题标号算法（特别是对增广链的理解） ? 图与网络优化问题的实践意义 图论是应用十分广泛的运筹学分支。 由于凡是具有二元关系的系统问题都可用图论方法求解，因此庞大复杂的工程系统问题和管理问题都可通过图描述解决许多工程设计和管理决策的最优化问题。其实，图论的形成，除了欧拉之外，还有物理和化学等其它学科的科学家的贡献 .今天，图与网络优化已广泛的应用于物理、化学、控制论、信息论、科学管理、计算机以及交通、运输、能源等各个领域。 图与网络的基本概念 a.?????? 端点、相邻、关联边、环、多重边 b.?????? 简单图、链、初等链、圈、初等圈、简单圈、路、 回路 c.?????? 度（次）、奇点、偶点、悬挂点 d.?????? 完全图、连通图、连通子图、支撑子图（生成图）、有向图、赋权图 e.?????? 树、支撑树（生成树）、最小支撑树 最小支撑树的实践意义 系统内各元素的相互关系如此复杂，人们迫切需要了解系统内的主要关系及其形成的框架结构。如果将问题系统内各元素的相互关系用图加以表示，那么寻找图的最小支撑树的意义就在于它能把系统内的主要关系加以提取和清楚地表达，从而便于人们更好地认识系统。 寻找一个连通图的最小支撑树的两种方法 破圈法是“见圈破圈”，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。 避圈法则采取先将图中的点都取出来，然后，逐渐向上面添边，并保证后添入的边不与以前添上的边构成圈就可以了，这个过程直到将边集中能加入的边（加入后不够成圈）都加入了为止。 最短路径问题 最短路问题，即是从给定的赋权网络图中找出任意两点间的最短距离。这里的权数可以是时间、费用、长度等等。有些问题如仓库和商场选址、输油管线的铺设、设备更新、连续投资等都可转化为最短路问题予以研究。因此，在实际中有广泛的应用。解决这类问题的最经典的算法是Dijkstra 算法。 关于Dijkstra 算法本书有较细致的讲解，在此不再详述。不过在应用时，要注意： a.?????? 权数必须是非负数 b.?????? T标号点和P标号点有不同意义。其中，T标号点表示已找到从原点到该点的路的那些点；P标号点表示已找到从原点到该点的最短路的那些点。 最短路径问题的Dijkstra法图上标号的步骤： 1 标号 （1） 标号初始点给 标号 其他点 标号 （2） 对刚给 标号的点 ，找出与其有连接边或弧的未有 标号的点 ，更新其 标号公式如下： （3） 对所有 标号取最小值，对应的点给 标号公式如下 当所求最短路的终点已有P标号,停止. 为 到 的最短路长.然后转2 2 求出最短路,从始点出发找与其连接的边或弧,两端点的 标号的差等于边或弧的权值,则该边或弧在最短路上. 例1：某石油公司需铺设一条从R国的S地到C国的T地的输油管线，可能经过的地区及地区间的距离（百公里）如下图所示。求从S到T的最短输油管线路。 解： 0：S0=｛S｝. 1：T(v1)=10, ?(v1)=S; T(v2)=15, ?(v2)=S; 故，P(v1)=10, ?*(v1)=S, S1=｛S, v1｝. 2：T(v3)= P(v1)+d(v1, v3)=10+20=30, ?(v3)=v1; T(v5)= P(v1)+d(v1, v5)=10+10=20, ?(v5)= v1; ?(v2)= v1; 故，P(v2)=14, ?*(v2)= v1, S2=｛S, v1, v2｝.