运筹学第七章图与网络优化.pptVIP

第七章 图与网络优化;B;7.1 图与网络的基本概念;2 无向图与有向图;3 端点，关联边，相邻，次;3 端点，关联边，相邻，次;4 链，圈，初等链，初等圈，简单链（圈） 相邻节点的序列 {v1? ,v2? ,…, vn?} 构成一条链(link)p178； 在无向图中，节点不重复出现的链称为初等链； 首尾相连的链称为圈(loop) ；首尾相连的初等链称为初等圈； 边不重复出现的链（圈）称为简单链（圈）; ; ;7基础图，路，回路，欧拉回路 在有向图D(V,A)中去掉箭头，称为D的基础图，G（D） 在有向图中，链 路 圈 回路 走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 定理 ：偶点图一定存在欧拉回路(一笔画定理);7.2 树图与最小支撑树; 7.2.1 树的定义及其性质;;支撑树; 7.2.3 最小支撑树;Kruskal 算法基于下述定理 定理 4.1 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点，则关联边 eij 必在某个最小支撑树中。 推论 4.1 将网路中的节点划分为两个不相交的集合V1和V2，V2=V?V1，则V1和V2间权值最小的边必定在某个最小支撑树中。 最小支撑树不一定唯一 定理 4.1 推论4.1是一个构造性定理，它指示了找最小支撑树的有效算法;方法一（ Prim 算法）： 1、根据网路写出边权矩阵，两点间若没有边，则用?表示； 2、从 v1 开始标记，在第一行打 ? ，划去第一列； 3、从所有打 ? 的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打 ? ； 4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第 3 步。 该算法中，打 ? 行对应的节点在 V1中，未划去的列在 V2中;1;方法三（破圈法）任取一个圈，从圈中去掉一条权最大的边。在余下的图 中，重复这个步骤，直到出现一个不含圈的图为止。;斯坦纳树问题 ; 1967年大名鼎鼎的贝尔电话公司，遇上了一家精明的用户航空公司，这家用户要求在第四个点的位置上架上电话线。这样使得电话公司不仅要拉新线，增加服务网点，而且要减少收费。这件事的连锁反应迫使电话公司改变了坚持长达10年按照最少发生树长度收费的原则，并且不得??对最短网络问题进行研究。 ;斯坦纳比;正三角形加点可以节省最多。 ;;;; 由于其在运输、通信和计算机等现代经济与科技中的重要作用，近几十年来它的研究进展越来越快。1985年，格拉姆和金芳容借助于计算机进行了大量运算，证明了斯坦纳比大于0.824，虽距0.866不遥远，却始终未能达到最终目标。美国数学会主席曾感叹道：“这问题已经公开了22年，这件事总令你不安，你不能证明这样初级的东西。”也许源于猜想提出的戏剧性背景，也许源于理论意义以及贝尔实验室的学术权威，也许源于数学家对形成初等而又难解问题的爱好，人们对这个问题的研究历久不衰。 ;斯坦纳比的证明（2）;斯坦纳比的证明（3）;7.3 最短路问题p185;例1 狄克斯特拉算法;最短路问题的标号过程;步骤：;例 求节点v1到节点v5的最短距离及其路线; (2)在所有T标号中，最小的为T(v2)=3,于是令P(v2)=3;第三步：;第四步：;第五步：;; Dijkstra最短路算法的特点和适应范围;Warshall-Floyd算法 (1962);Floyd-Warshall 算法 (1962);小结; 4.5.1.3 最短路应用举例——市话扩容 (实装率=0.8);7.4 网络的最大流和最小截;7.4 网络的最大流和最小截;最大流问题也是一个线性规划问题p194; 7.4.1 增广链; 7.4.1 增广链; 7.4.1 增广链; 截集与截集容量;定义：最小截集是截集容量最小的截集（最小割）;;;;定理p195 福特-富克森定理：网路的最大流等于最小截集容量。; 7.4.2 确定网路最大流的标号法; 最大流最小截的标号法步骤; 最大流最小截的标号法步骤;最大流最小截集的标号法举例;最大流最小截集的标号法举例; 最大流标号法的复杂度讨论;多端网路问题;定义 弧的剩余容量;;;;;;;;;;;7.5 最小费用最大流