图论及其应用-杨春-课件-全-电子科技大学

0.810.60.40.20xt00.511.5210.500.51n1图论及其应用任课教师：杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2《图论及其应用》作者:张先迪、李正良购买地点：教材科0.810.60.40.20xt00.511.5210.500.51n3参考文献[1]美，帮迪《图论及其应用》[2]美，GaryChartrand《图论导引》，人民邮电出版社，2007[3]BelaBollobas，《现代图论》，科学出版社，2001中国科学院研究生教学丛书[4]美，FredBuckley《图论简明教程》，清华大学出版社，2005李慧霸王风芹译0.810.60.40.20xt00.511.5210.500.51n4[5]李尉萱，《图论》，湖南科学技术出版社，1979[6]美，DouglasB.West《图论导引》，机械工业出版社，2007李建中，骆吉洲译[7]杨洪，《图论常用算法选编》，中国铁道出版社，1988[8]陈树柏，《网络图论及其应用》，科学出版社，19820.810.60.40.20xt00.511.5210.500.51n5[9]ChrisGodsil，GordonRoyle《AlgebraicGraphTheory》，世界图书出版公司北京公司，2004[10]王朝瑞，《图论》，高等教育出版社，19830.810.60.40.20xt00.511.5210.500.51n6第一章图的基本概念本次课主要内容图的概念与图论模型(一)、图论课程简介(二)、图的定义与图论模型(三)、图的同构0.810.60.40.20xt00.511.5210.500.51n71、研究对象图论是研究点与线组成的“图形”问题的一门科学。属于应用数学分支.(一)、图论课程简介2、发展历史图论起源于18世纪的1736年，标志事件是“哥尼斯堡七桥问题.数学家欧拉被称为“图论之父”.20世纪30年代出版第一本图论著作.0.810.60.40.20xt00.511.5210.500.51n83、应用状况图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。4、教学安排主要介绍图的一些基本概念、基本理论和图论的典型应用。60学时。0.810.60.40.20xt00.511.5210.500.51n91、图的定义(二)、图的定义与图论模型一个图是一个序偶V,E，记为G=(V,E),其中：(1)V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；(2)E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。0.810.60.40.20xt00.511.5210.500.51n10图可以用图形表示：V中的元素用平面上一个黑点表示，E中的元素用一条连接V中相应点对的任意形状的线表示。例1、设图G＝V,E。这里V＝{v1,v2,v3,v4}E＝{e1,e2,e3,e4,e5,e6}，e1＝(v1,v2)，e2＝(v1,v3)，e3＝(v1,v4)，e4＝(v2,v3)，e5＝(v3,v2)，e6＝(v3,v3)。v1v2v3v4e1e2e3e4e5e60.810.60.40.20xt00.511.5210.500.51n11图的相关概念：有限图：顶点集和边集都有限的图称为有限图；平凡图：只有一个顶点的图称为平凡图；空图：边集为空的图称为空图；n阶图：顶点数为n的图称为n阶图；(n,m)图：顶点数为n,边数为m的图称为(n,m)图；边的重数：连接两个相同顶点的边的条数称为边的重数；重数大于1的边称为重边；环：端点重合为一点的边称为环；简单图：无环无重边的图称为简单图；其余的图称为复合图；0.810.60.40.20xt00.511.5210.500.51n12顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为该边的两个端点；顶点u与边e相关联：顶点u是边e的端点；边e1与边e2相邻接：边e1与边e2有公共端点；2、图论模型为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。(1)化学中的图论模型19世纪，化学家凯莱用图论研究简单烃——即碳氢化合物0.810.60.40.20xt00.511.5210.500.51n13用点抽象分子式中的碳原子和氢原子，用边抽象原子间的化学键。通过这样的建模，能很好研究简单烃的同分异构现象.例如：C4H10的两种同分异构结构图模型为：hhhhhhhhhhhhhhhhhhhh0.810.60.40.20xt00.511.5210.500.51n14(2)商业中的图论模型商业中，经常用图来对仓库和零售店进行建模例如：令V={w1,w2,w3,r1,r2,r3,r4,r5}代表3个仓库和5个零售点E={w1r1,w1r2,w2r2,w2r3,w2r4,w3r3,w3r5}代表每个仓库和每个零售店间的关联。则图模型图形为：w1r1r2w2r3r4w3r5(3)最短航线问题0.810.60.40.20xt00.511.5210.500.51n15用点表示城市，两点连线当且仅当两城市有航线。为了求出两城市间最短航线，需要在线的旁边注明距离值。例如：令V={a,b,c,d,e}代表5个城市}E={ab,ad,bc,be,de}代表城市间的直达航线则航线图的图形为：abcde500320140430370请求出从d到c的最短路0.810.60.40.20xt00.511.5210.500.51n16(4)任务分配问题有一个旅行团要组织一批人去旅游，其中一些人是朋友他们要乘坐公共汽车去，而车上的位子是成对的。因此为了让大家旅途更愉快，旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。该问题可以建立一个图论模型来解决：旅行团的人抽象为图的顶点，两个顶点连线，当且仅当两个顶点代表的人是朋友。问题归结于在模型图中求所谓的“匹配”，关于图的匹配将在第五章介绍。0.810.60.40.20xt00.511.5210.500.51n17(5)考试时间安排问题一个教授需要对期末考试时间进行安排，使得学生们不会有相互冲突的考试。如何解决？该问题可以建立一个图论模型来解决：待考的课程可抽象为图的顶点，连接两个顶点的边表示至少有一个学生同时选择了这两门课程。问题归结于在模型图中求所谓的“顶点着色方案”问题，该问题将在第七章讨论。例如：有a,b,c,d,e,f六门课程。按照上面方法建立的模型图如下：0.810.60.40.20xt00.511.5210.500.51n18一种可行的安排方案为：第一时间：a,d,e;第二时间：b,f；最后：c.abcefd另一种可行的安排方案为：第一时间：a,e;第二时间：c,d；最后：b,f.(6)旅行售货员问题一电脑代理商要从她所在城市出发，乘飞机去六个城市，然后回到出发点，如果要求每个城市只经历一次，能否办到？给出行走方案。0.810.60.40.20xt00.511.5210.500.51n19问题归结为在模型图中寻求所谓的“哈密尔顿圈”问题。将在第四章介绍。例如：如果模型图如下：该问题可以建立一个图论模型来解决：城市抽象为图的顶点，边代表城市间的直达航线。abcdef可行方案:(1)h,d,e,c,b,a,h(2)h,d,e,c,a,b,h0.810.60.40.20xt00.511.5210.500.51n20在图论中，一个很值得研究的问题是如何比较两个图的异同，这就是图的同构问题。定义：设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：设u1↔u2v1↔v2,u1,v1V1,u2,v2V2;u1v1E1,当且仅当u2v2E2,且u1v1与u2v2的重数相同。称G1与G2同构，记为：由定义可以得到图同构的几个必要条件：(三)、图的同构12GG(1)顶点数相同；(2)边数相同；(3)关联边数相同的顶点个数相同。0.810.60.40.20xt00.511.5210.500.51n21判定图的同构是很困难的，属于NP完全问题。对于规模不大的两个图，判定其是否同构，可以采用观察加推证的方法。例2证明下面两图不同构。u1v1证明:u1的两个邻接点与v1的两个邻接点状况不同。所以，两图不同构。0.810.60.40.20xt00.511.5210.500.51n22例3证明下面两图同构。证明:作映射f:vi↔ui(i=1,2….10)(a)v1v2v3v4v5v6v7v8v9v10u1u2u3u4u5u6u7u8u9u10(b)容易证明，对vivjE((a)),有f(vivj,),,ui,uj,,E,((b))(1i10,1j10)由图的同构定义知，图(a)与(b)是同构的。0.810.60.40.20xt00.511.5210.500.51n23例4指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。0.810.60.40.20xt00.511.5210.500.51n24作业P29—P303,4,5,60.810.60.40.20xt00.511.5210.500.51n25ThankYou!0.810.60.40.20xt00.511.5210.500.51n26第一章图的基本概念本次课主要内容(二)、顶点的度与图的度序列(一)、完全图、偶图与补图0.810.60.40.20xt00.511.5210.500.51n27(一)、完全图、偶图与补图1、每两个不同的顶点之间都有一条边相连的简单图称为完全图.在同构意义下，n个顶点的完全图只有一个，记为KnK2K3K5容易求出：1()(1)2nmKnn0.810.60.40.20xt00.511.5210.500.51n282、所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中.完全偶图是指具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n图1图2图1与图2均是偶图，图2是K2,30.810.60.40.20xt00.511.5210.500.51n29偶图是一种常见数学模型。例1学校有6位教师将开设6门课程。六位教师的代号是xi（i=1,2,3,4,5,6)，六门课程代号是yi（i=1,2,3,4,5,6)。已知，教师x1能够胜任课程y2和y3；教师x2能够胜任课程y4和y5；教师x3能够胜任课程y2；教师x4能够胜任课程y6和y3；教师x5能够胜任课程y1和y6；教师x6能够胜任课程y5和y6。请画出老师和课程之间的状态图。x1x5x4x3x2x6y4y3y1y2y5y60.810.60.40.20xt00.511.5210.500.51n303、对于一个简单图G=（V,E），令集合1,,EuvuvuvV则称图H=（V，E1\E）为G的补图，记为HGHG例如，下面两个图互为补图。G1G20.810.60.40.20xt00.511.5210.500.51n31HG定理：若n阶图G是自补图(),则有：GG0,1(mod4)n证明：n阶图G是自补图，则有：补图是相对于完全图定义的。补图是图论中经常涉及的概念，在图论研究中有重要的作用如果图G与其补图同构，则称G为自补图。0.810.60.40.20xt00.511.5210.500.51n32HG所以：1()()()(1)2nmGmGmKnn