运筹学第8-9章[新].

ChinaUniversityofMiningandTechnology运筹学Chapter8图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容：ChinaUniversityofMiningandTechnology-2-运筹学学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。ChinaUniversityofMiningandTechnology-3-运筹学18世纪，Königsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文。七桥问题图的基本概念与模型ChinaUniversityofMiningandTechnology-4-运筹学中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。图的基本概念与模型ChinaUniversityofMiningandTechnology-5-运筹学Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。thedodecahedronisHamiltonian显然这样的路线存在且不唯一图的基本概念与模型ChinaUniversityofMiningandTechnology-6-运筹学50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于4×4，5×5，或8×8的棋盘上马的跳动如何？图的基本概念与模型ChinaUniversityofMiningandTechnology-7-运筹学61875329420112494031221234341322321444423324151345363425161453735261786462927189747382519101483930幻方问题图的基本概念与模型ChinaUniversityofMiningandTechnology-8-运筹学某团体举行舞会，其中有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识鸽笼原理和Ramsey数图的基本概念与模型ChinaUniversityofMiningandTechnology-9-运筹学四色猜想能否用四种颜色给地图染色，使相邻的国家有不同的颜色。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。图的基本概念与模型ChinaUniversityofMiningandTechnology-10-运筹学Möbius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。平面图与网络图的基本概念与模型ChinaUniversityofMiningandTechnology-11-运筹学n-方体Qnn方体n维立方体n=3的情形，上底下底是两个2维立方体。对应顶点连线后(同时把上底中顶点标号末位加号0，下底中顶点标号末位加号1)得到3维立方体。ChinaUniversityofMiningandTechnology-12-运筹学完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,nK3,3K2,4ChinaUniversityofMiningandTechnology-13-运筹学G2G112GG12GGG2G112GGChinaUniversityofMiningandTechnology-14-运筹学G2G112GGChinaUniversityofMiningandTechnology-15-运筹学网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256图的基本概念与模型ChinaUniversityofMiningandTechnology-16-运筹学一个图是二部图当且仅当它不含奇圈。设G是一个简单图，若δ(G)≥2，则G中必含有圈。设G是简单图，若δ(G)≥3,则G必有偶圈。设有2n个电话交换台，每个台与至少n个台有直通线路，则该交换系统中任二台均可实现通话。回答：ChinaUniversityofMiningandTechnology-17-运筹学图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：mvdvdvdVvVvVv2)()()(212m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。2)(Vvvd1)(Vvvd图的基本概念与模型ChinaUniversityofMiningandTechnology-18-运筹学图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中其它之间有关联边时与当且仅档0vv1jiija图的基本概念与模型ChinaUniversityofMiningandTechnology-19-运筹学2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:其他的一个端点是边当且仅当的两个端点是边当且仅当0ev1ev2jijiijm3.权矩阵对于赋权图G=(V,E),其中边有权,构造矩阵B=(bij)nn其中：),(jivvjiwEvvEvvwbjijijiji),(0),(图的基本概念与模型ChinaUniversityofMiningandTechnology-20-运筹学v5v1v2v3v4v6433225643701010110100101011110101000110111101065432166654321vvvvvvAvvvvvv下图所表示的图可以构造邻接矩阵A如下图的基本概念与模型例1ChinaUniversityofMiningandTechnology-21-运筹学v1v2v3v4v5v6v7v8v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4下图所表示的图可以构造邻接矩阵M如下:M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000图的基本概念与模型例2ChinaUniversityofMiningandTechnology-22-运筹学654321654321030303302004020576305020007204346040vvvvvvvvvvvvBv5v1v2v3v4v64332256437下图所表示的图可以构造权矩阵B如下:图的基本概念与模型例3ChinaUniversityofMiningandTechnology-23-运筹学树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员树与图的最小树ChinaUniversityofMiningandTechnology-24-运筹学某企业的组织机构图也可用树图表示。树与图的最小树厂长人事科财务科总工程师生产副厂长经营副厂长技术科新产品开发科生产科设备科供应科动力科检验科销售科ChinaUniversityofMiningandTechnology-25-运筹学树是一个不包含圈的简单连通图。树中度为1的点称为树叶，度大于1的点称为分枝点。具有k个连通分支的不包含圈的图称为k-树，或森林。下是具有六个顶点的树，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。ChinaUniversityofMiningandTechnology-26-运筹学树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6树与图的最小树ChinaUniversityofMiningandTechnology-27-运筹学图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝。一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2树与图的最小树ChinaUniversityofMiningandTechnology-28-运筹学(赋权)图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5树与图的最小树ChinaUniversityofMiningandTechnology-29-运筹学v1v2v3v4v5v643521得到最小树：MinC(T)=15树与图的最小树ChinaUniversityofMiningandTechnology-30-运筹学避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618树与图的最小树ChinaUniversityofMiningandTechnology-31-运筹学v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15树与图的最小树ChinaUniversityofMiningandTechnology-32-运筹学8.3最短路问题ChinaUniversityofMiningand