管理科学图与网络分析.ppt

* * * * * * * 第3章 图与网络分析 最 小 支 撑 树 最 短 路 问 题 最 大 流 问 题 本章内容重点 * 引 言 图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段。 * 引 言 第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围绕游戏而产生，最有代表性的工作是所谓的哥尼斯堡七桥问题，即一笔画问题。 * 引 言 哥尼斯堡（现名加里宁格勒）是欧洲一个城市，普雷格尔河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？ A B C D * 引 言 第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等. * 引 言 * 引 言 四色问题的发现 　　1852年，刚从伦敦大学毕业的弗南希斯在对英国的地图着色时，发现了一个有趣的现象：无论多么复杂的地图，只需要用四种颜色就能将它区分开来，也就是说，用四种颜色着色就能保证不会有两个相邻地区的颜色相同。 　　弗南希斯将自己的发现告诉给哥哥弗德雷克，引起了弗德雷克的浓厚兴趣，他深信弟弟所发现的这个结论是正确的，并企图从数学的角度对这个结论给予证明，但所有的努力都失败了。在百思不得其解的情况下，只得专程去请教他的老师、英国著名的 数学家德·摩根教授。摩根教授绞尽脑汁研究这个问题，可也一无所获。后来，他将这一猜想写信告诉了在都柏林的著名数学家哈密尔顿，于是“四色猜想”首次以 数学的形式提了出来。 * 引 言 四色问题的证明 　　　本世纪70年代中期，美国伊利诺斯州立大学的数学家阿佩尔和哈肯独树一帜，利用高速计算机对“四色猜想”进行证明。他们运用了一种“不可避免性”理论，从一万多张地图中挑选了近两千张上机检验，对每一张地图都使用了二十万种可能的方法着色，计算机作了两百亿个逻辑判定，经过1200小时的计算，终于在1976年6月证明了这个数学名题。伊利诺斯数学杂志的审稿人，对阿佩尔与哈肯证明的审查，也是通过计算机来实现的。 　　阿佩尔与哈肯的工作，使延续了124年之久的四色问题得到证明，成为四色定理。 * 引 言 第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。 * 基 本 概 念 一个图是由一些点及一些点之间的连线（不带箭头或带箭头）所组成的。 不带箭头的联线称为边。 带箭头的联线称为弧。 * 基 本 概 念 如果一个图G是由点及边所构成，则称之为无向图（也简称图）。 e3 e5 e6 e2 e1 e4 v3 v2 v4 v1 G=（V,E） V={v1,v2,v3,v4} E={e1,e2,e3,e4,e5,e6,e7} * 基 本 概 念 如果一个图D是由点及弧所构成，则称之为有向图。 a8 a3 a4 a6 a7 a5 v4 v5 v2 v3 D=（V,A） V={v1,v2,v3,v4,v5,v6,v7} A={a1,a2,a3,a4, a5,a6,a7 ,a8,a9,a10} v1 v7 v6 a9 a10 a1 a2 * 基 本 概 念 e1 V2 V1 e2 V3 v1 e v2 关联（边与点的关系）：若e是v1、v2两点间 的边，记e=[v1，v2 ]，称v1、v2 与e关联。 相邻（边与边、点与点的关系）： 点v1与v2有公共边，称点v1与v2相邻； 边e1与e2 有公共点，称边e1与e2相邻。 * 基 本 概 念 在图G中某个边e的两个端点相同，称e为环。若两个点之间有多于一条的边，称为多重边。一个无环、无多重边的图称为简单图，一个无环、允许有多重边的图称为多重图。 e3 e5 e6 e2 e1 e4 e7 v3 v2 v4 v1 e7是环 e1,e2是多重边 * 圈（Circuit） 封闭的链称为圈 如：μ