运筹学第89章新ppt课件.ppt

《运筹学第89章新ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter8图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容：学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。18世纪，Königsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答

2、，发表了第一篇论文。七桥问题图的基本概念与模型中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。图的基本概念与模型Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路

3、线如何确定。thedodecahedronisHamiltonian显然这样的路线存在且不唯一图的基本概念与模型50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于4×4，5×5，或8×8的棋盘上马的跳动如何？图的基本概念与模型幻方

4、问题图的基本概念与模型某团体举行舞会，其中有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识鸽笼原理和Ramsey数图的基本概念与模型四色猜想能否用四种颜色给地图染色，使相邻的国家有不同的颜色。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。图的基本概念与模型Möbius在1840年的一次演讲中提出如下问题：一个国王有

5、五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。平面图与网络图的基本概念与模型n-方体Qnn方体n维立方体n=3的情形，上底下底是两个2维立方体。对应顶点连线后(同时把上底中顶点标号末位加号0，下底中顶点标号末位加号1)得到3维立方体。完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连

6、。完全二分图记为Km,nK3,3K2,4G2G1G2G1G2G1网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256图的基本概念与模型一个图是二部图当且仅当它不含奇圈。设G是一个简单图，若δ(G)≥2，则G中必含有圈。设G是简单图，若δ(G)≥3,则G必有偶圈。

7、设有2n个电话交换台，每个台与至少n个台有直通线路，则该交换系统中任二台均可实现通话。回答：图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：2m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。图的基本概念与模型图的矩阵描述：如何在计算机中存储一个图呢？现在已有很

8、多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等1.邻接矩阵对于图G=（V，E），

9、V

10、=n，

11、E

12、=m，有nn阶方矩阵A=(aij)nn，其中图的基本概念与模型2.关联矩阵对于图G=(V,E),

13、V

14、=n,

15、E

16、=m,有mn阶矩阵M=(mij)mn，其中:3.权矩阵对于赋权图G=(V,E),其中边有权,构造矩阵B=(bij)nn其中：图的基本概念与模型v5