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

1、1,第3章 图与网络分析,最 小 支 撑 树 最 短 路 问 题 最 大 流 问 题,2,引 言,图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段。,3,引 言,第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围绕游戏而产生，最有代表性的工作是所谓的哥尼斯堡七桥问题，即一笔画问题。,4,引 言,哥尼斯堡（现名加里宁格勒）是欧洲一个城市，普雷格尔河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,5,引 言,

2、第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.,6,引 言,7,引 言,四色问题的发现 1852年，刚从伦敦大学毕业的弗南希斯在对英国的地图着色时，发现了一个有趣的现象：无论多么复杂的地图，只需要用四种颜色就能将它区分开来，也就是说，用四种颜色着色就能保证不会有两个相邻地区的颜色相同。 弗南希斯将自己的发现告诉给哥哥弗德雷克，引起了弗德雷克的浓厚兴趣，他深信弟弟所发现的这个结论是正确的，并企图从数学的角度对这个结论给予证明，但所有的努力

3、都失败了。在百思不得其解的情况下，只得专程去请教他的老师、英国著名的 数学家德摩根教授。摩根教授绞尽脑汁研究这个问题，可也一无所获。后来，他将这一猜想写信告诉了在都柏林的著名数学家哈密尔顿，于是“四色猜想”首次以 数学的形式提了出来。,8,引 言,四色问题的证明 本世纪70年代中期，美国伊利诺斯州立大学的数学家阿佩尔和哈肯独树一帜，利用高速计算机对“四色猜想”进行证明。他们运用了一种“不可避免性”理论，从一万多张地图中挑选了近两千张上机检验，对每一张地图都使用了二十万种可能的方法着色，计算机作了两百亿个逻辑判定，经过1200小时的计算，终于在1976年6月证明了这个数学名题。伊利诺斯数学杂志的

4、审稿人，对阿佩尔与哈肯证明的审查，也是通过计算机来实现的。 阿佩尔与哈肯的工作，使延续了124年之久的四色问题得到证明，成为四色定理。,9,引 言,第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。,10,基 本 概 念,一个图是由一些点及一些点之间的连线（不带箭头或带箭头）所组成的。,不带箭头的联线称为边。,带箭头的联线称为弧。,11,基 本 概 念,如果一个图G是由点及边所构成，则称之

5、为无向图（也简称图）。,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,12,基 本 概 念,如果一个图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,13,基 本 概 念,e1 V2 V1 e2 V3,v1 e v2,关联（边与点的关系）：若e是v1、v2两点间 的边，

6、记e=v1，v2 ，称v1、v2 与e关联。,相邻（边与边、点与点的关系）： 点v1与v2有公共边，称点v1与v2相邻； 边e1与e2 有公共点，称边e1与e2相邻。,14,基 本 概 念,在图G中某个边e的两个端点相同，称e为环。若两个点之间有多于一条的边，称为多重边。一个无环、无多重边的图称为简单图，一个无环、允许有多重边的图称为多重图。,e3,e5,e6,e2,e1,e4,e7,v3,v2,v4,v1,e7是环,e1,e2是多重边,15,圈（Circuit） 封闭的链称为圈 如：=(1,2),(2,4),(3,4),(1,3),链:由图G中的某些点与边相间构成的序列 V1,e1,V2,e2, ,Vk,ek,若满足 ,则称此 点边序列为G中的一条链。 如： =(1,2),(3,2),(3,4),4,2,3,1,4,2,3,1,基 本 概 念,16,连通图 任意两个节点之间至少有一条链的图称为连通图,4,2,3,1,网络,给图中的点和边赋以具体的含义和权数（如距离、费用、容量等），则称这样的图为网络图。,4,2,3,1,50 70 20 45,基 本 概 念,17,基