运筹学第7章

ChinaUniversityofMiningandTechnology运筹学Chapter6图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容：ChinaUniversityofMiningandTechnology-2-运筹学学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。ChinaUniversityofMiningandTechnology-3-运筹学6.1图的基本概念和模型ChinaUniversityofMiningandTechnology-4-运筹学长江汉江武昌汉口汉阳您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗?图的基本概念与模型ChinaUniversityofMiningandTechnology-5-运筹学18世纪，Königsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文。七桥问题图的基本概念与模型ChinaUniversityofMiningandTechnology-8-运筹学ACBDACBD如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点？求从图中任一点出发，通过每条边一次，最后回到起点。桥所连接的地区视为点每一座桥视为一条线图的基本概念与模型ChinaUniversityofMiningandTechnology-10-运筹学中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。图的基本概念与模型ChinaUniversityofMiningandTechnology-11-运筹学Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。thedodecahedronisHamiltonian显然这样的路线存在且不唯一图的基本概念与模型ChinaUniversityofMiningandTechnology-12-运筹学50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于4×4，5×5，或8×8的棋盘上马的跳动如何？图的基本概念与模型ChinaUniversityofMiningandTechnology-13-运筹学61875329420112494031221234341322321444423324151345363425161453735261786462927189747382519101483930幻方问题图的基本概念与模型ChinaUniversityofMiningandTechnology-14-运筹学某团体举行舞会，其中有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识鸽笼原理和Ramsey数图的基本概念与模型ChinaUniversityofMiningandTechnology-15-运筹学四色猜想能否用四种颜色给地图染色，使相邻的国家有不同的颜色。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。图的基本概念与模型ChinaUniversityofMiningandTechnology-17-运筹学Möbius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。平面图与网络图的基本概念与模型ChinaUniversityofMiningandTechnology-21-运筹学图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的基本概念与模型ChinaUniversityofMiningandTechnology-22-运筹学图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：},{EVG其中:V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。当V,E为有限集合时，G称为有限图，否则，称为无限图.ChinaUniversityofMiningandTechnology-23-运筹学v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。图的基本概念与模型ChinaUniversityofMiningandTechnology-24-运筹学在一个图的几何实现中，两条边的交点可能不是图的顶点。例如4e1e2e3e5e6e1v2v3v4v有时也用m(G)=|E|表示图G中的边数，用n(G)=|V|表示图G中的顶点个数，简记为m,n.图G中的点数记为p(G)，边数记为q(G).此时，图G可以表示为G=(p,q).ChinaUniversityofMiningandTechnology-25-运筹学通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的），而边仅在端点处相交，这样画出的平面图形称为图的图示。平面图ChinaUniversityofMiningandTechnology-26-运筹学环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。只有一个顶点的图称为平凡图；边集是空集的图称为空图。v3e7e4e8e5e6e1e2e3v1v2v4v5图的基本概念与模型ChinaUniversityofMiningandTechnology-27-运筹学完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.2(1)|()|22nnnnnEKC完全图ChinaUniversityofMiningandTechnology-28-运筹学K3K4K5K5ChinaUniversityofMiningandTechnology-29-运筹学n-方体Qnn方体n维立方体n=3的情形，上底下底是两个2维立方体。对应顶点连线后(同时把上底中顶点标号末位加号0，下底中顶点标号末位加号1)得到3维立方体。ChinaUniversityofMiningandTechnology-30-运筹学G的补图(complement)：设G是一个图，以V(G)为顶点集，以{(x,y)|(x,y)∉E(G)}为边集的图称为G的补图，记为GC。ChinaUniversityofMiningandTechnology-31-运筹学次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。图的基本概念与模型ChinaUniversityofMiningandTechnology-32-运筹学链，圈，连通图图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5},,,,,{110kkvevev起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。图的基本概念与模型ChinaUniversityofMiningandTechnology-33-运筹学二部图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。图的基本概念与模型ChinaUniversityofMiningandTechnology-34-运筹学完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,nK3,3K2,4ChinaUniversityofMiningandTechnology-35-运筹学子图，部分图(支撑子图)图G1={V1、E1}和图G2={V2，E2}如果有称G1是G2的一个子图。若有，则称G1是G2的一个部分图(支撑子图)。2121EEVV和2121EEVV，＝v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图的基本概念与模型ChinaUniversityofMiningandTechnology-36-运筹学顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为G[W]。导出子图G[V-W]记为G-W，即]\)([(WGVGWG它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。ChinaUniversityofMiningandTechnology-37-运筹学e1e3e2Gv3v4v5v2v1e3e2v3v4v2G[v2,v3,v4]G-{v1,v5}e1e3e2v3v4v5v2v1ChinaUniversityofMiningandTechnology-38-运筹学边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为G[F]。记G-F表示以E(G)\F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。ChinaUniversityofMiningandTechnology-39-运筹学e1e3e2Gv3v4v5v2v1G[e1,e2,e3]G-e1e1e3e2v3v4v5v2v1e1e3e2v3v4v2v1ChinaUniversityofMiningandTechnology-40-运筹学1G2G21GG21GG图的运算ChinaUniversityofMiningandTechnology-41-运筹学21GG21GG)()(212121GGGGGG)()(122121GGGGGGorChinaUniversityofMini