运筹学第7章图与网络优化要点.ppt

Chapter 7 图与网络优化 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学, 控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1所示。 第一节 图的基本概念 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 基本概念 例如.图8-4是一个无向图G=（V，E） 其中V = {v1,v2,v3,v4} E = { [v1,v2],[v2,v1],[v2,v3], [v3,v4],[v1,v4], [v2,v4], [v3,v3] } 图8-5是一个有向图D=（V，A） 其中V = {v1,v2,v3,v4,v5,v6,v7} A = {(v1 ,v2),(v1 ,v3),(v3 ,v2), (v3 ,v4), (v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3), (v5 ,v4),(v5 ,v6),(v6 ,v7)} 链： 由两两相邻的点及其相关联的边构成的点边序列, 如: （v0 ,e1 ,v1 ,e2 ,v2 ,e3 ,v3 ,…,vn-1 ,en , vn ）; 其中v0 ，vn分别为链的起点和终点， v1 ,v2 ,…,vn-1称为中间点 ； 圈： 起点与终点重合的链； 简单链（圈）：链（圈）中所含的边均不相同； 初等链（圈）：链（圈）中所含的点均不相同,也称通路； 有向图：关联边有方向 弧：有向图的边a=(u ,v),起点u,终点v; 路：若有从u到v不考虑方向的链,且各方向一致,则称之为从u到v的路； 初等路: 各顶点都不相同的路； 初等回路:u = v 的初等 路; 连通图： 若不考虑方向 是无向连通图; 强连通图：任两点有路; 图的基本性质： 第二节 树 树的概念 构造生成树的方法 最小生成树问题 第三节 最短路问题 Dijkstra算法步骤： 网络系统上流的特点： 发点的总流出量和收点的总流入量必 相等； 每一个中间点的流入量与流出量的代数和等于零； 每一个弧上的流量不能超过它的最大通过能力（即容量）。 二、一笔画问题 欧拉链 如果连通多重图G中存在一条链，并且经过G的每条边一次且仅一次，那么这条链叫做欧拉链. 欧拉圈 如在连通多重图G中存在一个简单圈，经过G的每条边一次且仅一次，那么这个圈叫做欧拉圈。 欧拉图 一个图如果有欧拉圈，那么这个图叫做欧拉图。 很明显，一个图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链。 定理 9 一个连通多重图G是欧拉图当且仅当是G中无奇点。 证: 必要性，显然。 充分性， 不妨设连通多重图G至少有三点，对G的边数q用数学归纳法。因为G是连通的，并且不含奇点，故q≥3。 当q=3时，显然G是欧拉图。 假设 q = n 时成立。q = n+1的情形：由于G是无奇点的连通图，并且G的点数 p ≥ 3，因此存在三个点μ,v,w,使得[μ,v],[w,v]∈E。 从G中去掉边[μ,v],[w,v]，增加新边[μ,w]，得到一个新的多重图G1，G1有q-1条边，且仍不含奇点，G1至多有两个分图。 若G1是连通的，则由归纳假设，G1有欧拉圈C1。把C1中的边[w,μ]换成[μ,v],[w,v]，即是G中的欧拉圈。 若G1有两个分图G1，G2，令v在G1中。由归纳假设，G1，G2分别有欧拉圈C1，C2，把C2中的边[μ,w]换成[μ,v], C1及[v,w]即是G中的欧拉圈。 推论 一个多重连通图G有欧拉链当且仅当G恰有两个奇点。 二、奇偶点图上作业法 作业 课后习题 7.3 7.4（b） 7.9 7.11 7.12 7.16 vs v2 v4 v1 v3