《图论及其应用 杨春 ppt课件 全.ppt》由会员分享，可在线阅读，更多相关《图论及其应用 杨春 ppt课件 全.ppt（854页珍藏版）》请在三一办公上搜索。
1、1,图论及其应用,任课教师：杨春,数学科学学院,2,图论及其应用 作者: 张先迪、李正良 购买地点：教材科,3,参考文献,1 美，帮迪图论及其应用2 美，Gary Chartrand图论导引，人民邮电出版社，20073 Bela Bollobas，现代图论，科学出版社，2001 中国科学院研究生教学丛书4 美，Fred Buckley图论简明教程，清华大学出版社，2005 李慧霸 王风芹译,4,5 李尉萱，图论，湖南科学技术出版社，19796 美，Douglas B.West图论导引，机械工业出版社，2007 李建中，骆吉洲译7 杨洪，图论常用算法选编，中国铁道出版社，19888 陈树柏，网络
2、图论及其应用，科学出版社，1982,5,9 Chris Godsil，Gordon Royle Algebraic Graph Theory，世界图书出版公司北京公司，200410 王朝瑞，图论，高等教育出版社，1983,6,第一章 图的基本概念,本次课主要内容,图的概念与图论模型,(一)、图论课程简介,(二)、图的定义与图论模型,(三)、图的同构,7,1、研究对象,图论是研究点与线组成的“图形”问题的一门科学。属于应用数学分支.,(一)、图论课程简介,2、发展历史,图论起源于18世纪的1736年，标志事件是“哥尼斯堡七桥问题.,数学家欧拉被称为“图论之父”.,20世纪30年代出版第一本图论著
3、作.,8,3、应用状况,图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。,目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。,4、教学安排,主要介绍图的一些基本概念、基本理论和图论的典型应用。60学时。,9,1、图的定义,(二)、图的定义与图论模型,一个图是一个序偶，记为G=(V,E),其中：,(1) V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；,(2) E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数
4、。,10,图可以用图形表示：V中的元素用平面上一个黑点表示，E中的元素用一条连接V中相应点对的任意形状的线表示。,例1、设图G。这里Vv1,v2,v3,v4Ee1,e2,e3,e4,e5,e6，,e1(v1,v2)，e2(v1,v3)，e3(v1,v4)，e4(v2,v3)，e5(v3,v2)，e6(v3,v3)。,11,图的相关概念：,有限图：顶点集和边集都有限的图称为有限图；,平凡图：只有一个顶点的图称为平凡图；,空图：边集为空的图称为空图；,n阶图：顶点数为n的图称为n阶图；,(n, m) 图：顶点数为n,边数为m的图称为(n, m) 图；,边的重数：连接两个相同顶点的边的条数称为边的重
5、数；重数大于1的边称为重边；,环：端点重合为一点的边称为环；,简单图：无环无重边的图称为简单图；其余的图称为复合图；,12,顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为该边的两个端点；,顶点u与边e相关联：顶点u是边e的端点；,边e1与边e2相邻接：边e1与边e2有公共端点；,2、图论模型,为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。,(1) 化学中的图论模型,19世纪，化学家凯莱用图论研究简单烃即碳氢化合物,13,用点抽象分子式中的碳原子和氢原子，用边抽象原子间的化学键。,通过这样的建模，能很好研究简单烃的同分异构现
6、象.,例如：C4H10的两种同分异构结构图模型为：,14,(2) 商业中的图论模型,商业中，经常用图来对仓库和零售店进行建模,例如：令V=w1,w2,w3,r1,r2,r3,r4,r5代表3个仓库和5个零售点,E=w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5代表每个仓库和每个零售店间的关联。则图模型图形为：,(3) 最短航线问题,15,用点表示城市，两点连线当且仅当两城市有航线。为了求出两城市间最短航线，需要在线的旁边注明距离值。,例如：令V=a, b, c, d, e代表5个城市,E=a b, ad, b c , be, de代表城市间的直达航线,则航线图
7、的图形为：,请求出从d到c的最短路,16,(4) 任务分配问题,有一个旅行团要组织一批人去旅游，其中一些人是朋友他们要乘坐公共汽车去，而车上的位子是成对的。因此为了让大家旅途更愉快，旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。,该问题可以建立一个图论模型来解决：旅行团的人抽象为图的顶点，两个顶点连线，当且仅当两个顶点代表的人是朋友。,问题归结于在模型图中求所谓的“匹配”，关于图的匹配将在第五章介绍。,17,(5) 考试时间安排问题,一个教授需要对期末考试时间进行安排，使得学生们不会有相互冲突的考试。如何解决？,该问题可以建立一个图论模型来解决：待考的课程可抽象为图的顶点，连接两个
8、顶点的边表示至少有一个学生同时选择了这两门课程。,问题归结于在模型图中求所谓的“顶点着色方案”问题，该问题将在第七章讨论。,例如：有a, b, c ,d, e, f 六门课程。按照上面方法建立的模型图如下：,18,一种可行的安排方案为：第一时间：a, d, e;第二时间：b, f ；最后：c.,另一种可行的安排方案为：第一时间：a, e;第二时间：c, d ；最后：b, f .,(6) 旅行售货员问题,一电脑代理商要从她所在城市出发，乘飞机去六个城市，然后回到出发点，如果要求每个城市只经历一次，能否办到？给出行走方案。,19,问题归结为在模型图中寻求所谓的“哈密尔顿圈”问题。将在第四章介绍。,
9、例如：如果模型图如下：,该问题可以建立一个图论模型来解决：城市抽象为图的顶点，边代表城市间的直达航线。,可行方案: (1) h, d, e, c, b, a, h (2) h, d, e, c, a, b, h,20,在图论中，一个很值得研究的问题是如何比较两个图的异同，这就是图的同构问题。,定义：设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：设u1u2v1v2, u1,v1 V1, u2,v2 V2; u1v1 E1,当且仅当u2v2 E2,且u1v1与u2v2的重数相同。称G1与G2同构，记为：,由定义可以得到图同构的几个必要条件：
10、,(三)、图的同构,(1) 顶点数相同；(2) 边数相同；(3) 关联边数相同的顶点个数相同。,21,判定图的同构是很困难的，属于NP完全问题。对于规模不大的两个图，判定其是否同构，可以采用观察加推证的方法。,例2 证明下面两图不同构。,证明:u1的两个邻接点与v1的两个邻接点状况不同。所以，两图不同构。,22,例3 证明下面两图同构。,证明:作映射f : vi ui (i=1,2.10),容易证明，对vi v j E (a),有f (v i vj,),ui,uj,E,(b) (1 i 10, 1j 10 ),由图的同构定义知，图(a)与(b)是同构的。,23,例4 指出4个顶点的非同构的所有
11、简单图。,分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。,24,作业,P29P30 3, 4, 5, 6,25,Thank You !,26,第一章 图的基本概念,本次课主要内容,(二)、顶点的度与图的度序列,(一)、完全图、偶图与补图,27,(一)、完全图、偶图与补图,1、每两个不同的顶点之间都有一条边相连的简单图称为完全图 .,在同构意义下，n个顶点的完全图只有一个，记为 Kn,容易求出：,28,2、所谓具有二分类（X, Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中.,完全偶图是指具有二分
12、类（X, Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为 K m, n,图1与图2均是偶图，图2是K2,3,29,偶图是一种常见数学模型。,例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。请画出老师和课程之间的状态图。,30,3、对于一个简单图G =（V, E），令集
13、合,则称图H =（V，E1E）为G的补图，记为,例如，下面两个图互为补图。,31,定理：若n阶图G是自补图( ),则有：,证明：n阶图G是自补图，则有：,补图是相对于完全图定义的。,补图是图论中经常涉及的概念，在图论研究中有重要的作用,如果图G与其补图同构，则称G为自补图。,32,所以：,由于n是正整数，所以：,自补图是很有意义的图类。它在对角型拉姆齐数方面的研究、关于图的香农容量的研究、强完美图方面的研究等都有重要作用。,33,(二)、顶点的度与图的度序列,G的顶点v的度d (v)是指G中与v关联的边的数目，每个环计算两次。,1、顶点的度及其性质,分别用(G)和(G)表示图G的最小与最大度。
14、,例2 在10个顶点以下的单图中，哪些阶数的图可能为自补图？画出8阶的4个自补图(共10个)。,34,奇数度的顶点称为奇点，偶数度的顶点称偶点。,设G = (V, E)为简单图，如果对所有 ，有,d (v) = k，称图G为k-正则图,定理： 图G= (V, E)中所有顶点的度的和等于边数m的2倍，即：,证明：由顶点度的定义知：图中每条边给图的总度数贡献2度，所以，总度数等于边数2倍。,注：该定理称为图论第一定理，是由欧拉提出的。欧拉一身发表论文886篇，著作90部。该定理还有一个名字：“握手定理”。,35,推论1 在任何图中，奇点个数为偶数。,证明：设V1,V2分别是G中奇点集和偶点集.则由
15、握手定理有：,是偶数，由于 是偶数， 所以 是偶数，于是 是偶数。,推论2 正则图的阶数和度数不同时为奇数 。,证明 ： 设G是k-正则图，若k为奇数，则由推论1知正则图G的点数必为偶数,例4 与是简单图G的最大度与最小度，求证：,36,证明：由握手定理有：,所以有：,2、图的度序列及其性质,一个图G的各个点的度d1, d2, dn构成的非负整数组 (d1, d2, dn)称为G的度序列 。,任意一个图G对应唯一一个度序列，图的度序列是刻画图的特征的重要“拓扑不变量”。,37,图G 的“拓扑不变量”是指与图G有关的一个数或数组(向量)。它对于与图G同构的所有图来说，不会发生改变。,一个图G可以
16、对应很多拓扑不变量。如果某组不变量可完全决定一个图，称它为不变量的完全集。,定理：非负整数组(d1,d2,., d n)是图的度序列的充分必要条件是： 为偶数。,证明：必要性由握手定理立即得到。,如果 为偶数，则数组中为奇数的数字个数,必为偶数。按照如下方式作图G:若di为偶数，则在与之对应的点作di/2个环；对于剩下的偶数个奇数，,38,两两配对后分别在每配对点间先连一条边，然后在每个顶点画dj-1/2个环。该图的度序列就是已知数组。,一个非负数组如果是某简单图的度序列，我们称它为可图序列，简称图序列。,关于图序列，主要研究3个问题：,(1) 存在问题：什么样的整数组是图序列？,(2) 计数
17、问题：一个图序列对应多少不同构的图？,(3) 构造问题：如何画出图序列对应的所有不同构图？,研究现状: (1)彻底解决了，(2)解决得不好，(3)没有解决。,39,定理：非负整数组,是图序列的充分必要条件是：,是图序列。,40,例5 是否为图序列？如果是，作出对应的一个简单图。,解：,由于 是图序列，所以原序列是图序列。,41,定理: (厄多斯1960)非负整数组,是图序列的充分必要条件是：,该定理证明很难！,上世纪60年代以来，人们又研究所谓的唯一图序列问题。,例5就是一个唯一图序列！,42,定理: 一个满足d2=dn-1的图序列,是唯一图序列的充分必要条件是下列条件之一满足：,43,3、图
18、的频序列及其性质,定理： 一个简单图G的n个点的度不能互不相同,证明： 因为图G为简单图，所以：(G)n-1。,情形1：若G没有孤立点，则,由鸽笼原理：必有两顶点度数相同；,情形2：若G只有一个孤立点，设G1表示G去掉孤立点后的部分，则：,由鸽笼原理：在G1里必有两顶点度数相同；,情形3：若G只有两个以上的孤立点，则定理显然成立。,44,定义： 设n阶图G的各点的度取s个不同的非负整数d1,d2, ds。又设度为di的点有bi个 (i = 1,2,s)，则,故非整数组(b1,b2, bs)是n的一个划分，称为G的频序列。,定理： 一个n阶图G和它的补图有相同的频序列。,45,作业,P29P30
19、 8, 9, 10, 11,46,Thank You !,47,第一章 图的基本概念,本次课主要内容,子图、图运算、路与连通性,(一)、子图的相关概念,(三)、路与连通性,(二)、图运算,48,1、子图,简单地说，图G的任意一部分(包括本身)都称为是图G的的一个子图。,定义1 如果,(一)、子图的相关概念,且H中边的重数不超过G中对应边的条数，则称H为G的子图，记为,当 时，称H是G的真子图，记为,49,2、点与边的导出子图,(1) 图G的顶点导出子图,定义2 如果 ，则以 为顶点集，以两个端点均在 中的边集组成的图，称为图G的点导出子图。记为：,例1 如图所示，求 。其中,50,解：由点导出
20、子图的定义得：,(2) 图G的边导出子图,定义3 如果 ，则以 为边集，以 中边的所有端点为顶点集组成的图，称为图G的边导出子图。记为：,例2 如图所示，求 。其中,51,解：由边导出子图的定义得：,52,3、图的生成子图,定义3 如果图G的一个子图包含G的所有顶点，称该子图为G的一个生成子图,例2 如图所示，求G的所有生成子图,解：按边数分别求出,53,定理：简单图G=(n,m)的所有生成子图个数为2m,(二)、图运算,在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。,1、图的删点、删边
21、运算,(1)、图的删点运算,设 ，在G中删去 中的顶点和G中与之关联的所有边的操作，称为删点运算。记为,特别地，如果只删去一个点v，则记为G-v.,54,(2)、图的删边运算,设 ，在G中删去 中的所有边的操作，称为删边运算。记为,特别地，如果只删去一条边e，则记为G-e.,注：删点、删边后得到的图是原图的子图。,2、图的并运算,设G1,G2是G的两个子图，G1与G2并是指由 为顶点集，以 为边集组成的子图。记为：,特别是，如果G1,G2不相交(没有公共顶点)，称它们的并为直接并，可以记为：,55,2、图的交运算,设G1,G2是G的两个子图，G1与G2交是指由 为顶点集，以 为边集组成的子图。
22、记为：,设G1,G2是两个图，G1与G2的差是指从G1中删去G2中的边得到的新图。记为G1-G2.,3、图的差运算,4、图的对称差运算(或环和运算),设G1,G2是两个图，G1与G2的对称差定义为：,56,例3 已知G1与G2，求,解：由相应运算定义得下面结果：,57,58,5、图的联运算,设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为 ：,例4 已知G1与G2，求,解：由联图的定义得：,59,6、图的积图,设 是两个图。对点集,的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)
23、或(u2=v2和u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为,例5 已知G1与G2，画,60,6、图的合成图,设 是两个图。对点集,的任意两个点u=(u1,u2)与v=(v1,v2),当(u1adjv1)或(u1=v1和u2adjv2)时，把u与v相连。如此得到的新图称为G1与G2的合成图。记为,例6 已知G1与G2，画,61,图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的“超立方体”结构。采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。,“超立方体”可以采用积图来递归构造。定义如下：,(1) 1方体,
24、(2) n方体定义为：,“超立方体”常采用下面简单的递归构造方法：,62,n方体Q n的顶点可用一个长度为n的二进制码来表示。Q n的顶点数目正好等于2n个。,由n-1方体Q n-1构造Q n的方法是：将Q n-1拷贝一个。将原Q n-1每个顶点的码前再添加一个零，将拷贝得来的n-1方体每个顶点的码前面再添加一个1。然后在两个n-1方体之间连线：当且仅当两个顶点码只有一位对应位数字不同时，该两点连线。如此得到的图即为n方体。,关于n方体Q n的性质研究，可以查阅到很多文献。经典文章是：Saad Y, Schultz M H. Topological properties of hypercub
25、es J. IEEETrans. Comput . 1988, 37(7) : 867-872,7、图的联合,把G1的一个顶点和G2的一个顶点粘合在一起后得到的新图称为G1与G2的联合。记为：,63,(三)、路与连通性,对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。,1、路与连通性的相关概念,(1)、图中的途径,G的一条途径（或通道或通路）是指一个有限非空序列w= v0 e1 v1 e2 v2ek vk，它的项交替地为顶点和
26、边，使得 ，ei的端点是vi-1和vi.,途径中边数称为途径的长度；v0,vk分别称为途径的起点与终点，其余顶点称为途径的内部点。,(2)、图中的迹,边不重复的途径称为图的一条迹。,64,图中顶点u与v的距离：u与v间最短路的长度称为u与v间距离。记为d (u, v). 如果u与v间不存在路，定义d (u, v)=.,(3)、图中的路,(4)、图中两顶点的距离,注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹 与圈。闭迹也称为回路。长度为k的圈称为k圈，k为奇数时称为奇 圈，k为偶数时称为偶圈。,顶点不重复的途径称为图的一条路。,(5)、图中两顶点的连通性,图G中点u与v说是连通的，如
27、果u与v间存在通路。否则称u与v不连通。点的连通关系是等价关系。,如果图G中任意两点是连通的，称G是连通图，否则，称G是非连通图。非连通图中每一个极大连通部分，称为G的连通分支。G的连通分支的个数，称为G的分支数，记为,65,(6)、图的直径,连通图G的直径定义为：,如果G不连通，图G的直径定义为,例7 证明：在n阶连通图中,(1) 至少有n-1条边；,(2) 如果边数大于n-1，则至少有一条闭迹；,(3) 如果恰有n-1条边，则至少有一个奇度点。,66,证明： (1) 由于G连通，所以，存在如下形式的途径：,显然该途径至少含有n-1条边。(v1,v2, , v n是G的n个不同顶点),(2)
28、 考虑G中途径：,若W是路，则长为n-1;但由于G的边数大于n-1,因此，存在vi与vj,它们相异，但邻接。于是：,为G中一闭途径，于是也就存在闭迹。,67,(3) 若不然，G中顶点度数至少为2，于是由握手定理：,这与G中恰有n-1条边矛盾！,例8 证明：若2，则G中必然含有圈。,证明：只就连通图证明即可！,设W=v1v2.vk-1vk是G中的一条最长路。由于2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路,所以，这样的邻接点必然是v1,v2,.,vk-2中之一。设该点为vm，则vmvm+1.v kvm为G中圈。,68,2、连通性性质,定理1：若图G不连通，则其补图连通,证明：对
29、,如果u, v属于G的同一分支，设w是与u, v处于不同分支中的点，则在G的补图中，u与w, v与w分别邻接，于是，u与v在G的补图中是连通的。,如果u与v在G的两个不同分支中，则在G的补图中必然邻接，因此，也连通。,所以，若G不连通，G的补图是连通的。,3、偶图的判定定理,69,定理2 一个图是偶图当且当它不包含奇圈。,证明： 必要性：设G是具有二分类（X, Y）的偶图，并且C = v0 v1 vk v0是G的一个圈,不失一般性，可假定 。一般说来，,。又因为 ，所以,由此即得C是偶圈。,充分性：在G中任意选取点u, 定义V的分类如下：,X = x | d (u, x) 是偶数，x V (G
30、),Y = y | d (u, y) 是奇数，y V (G),下面证明：对X中任意两点v与w , v与w不邻接！,70,设v与w是X中任意两个顶点。P是一条最短(u , v)路 ，而Q是一条最短的(u, w)路。,又设u1是P和Q的最后一个交点。由于P, Q是最短路，所以，P,Q中u到u1段长度相同，因此奇偶性相同。又P,Q的长均是偶数，所以，P,Q中u1v段和u1w段奇偶性相同。,如果v与w邻接，则可得到奇圈，矛盾！,71,作业,P29P30 13, 14, 20, 22,72,Thank You !,73,第一章 图的基本概念,本次课主要内容,最短路算法、图的代数表示,(一)、最短路算法,
31、(二)、图的代数表示,1、图的邻接矩阵,2、图的关联矩阵,74,1、相关概念,(1) 赋权图,(一)、最短路算法,在图G的每条边上标上一个实数w (e)后, 称G为边赋权图。被标上的实数称为边的权值。,若H是赋权图G的一个子图，称 为子图H的权值。,权值的意义是广泛的。可以表示距离，可以表示交通运费，可以表示网络流量，在朋友关系图甚至可以表示友谊深度。但都可以抽象为距离。,75,(2) 赋权图中的最短路,设G为边赋权图。u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。,解决某类问题的一组有穷规则，称为算法。,(3) 算法,1) 好算法,算法总运算量是问
32、题规模的多项式函数时，称该算法为好算法。(问题规模：描述或表示问题需要的信息量),算法中的运算包括算术运算、比较运算等。运算量用运算次数表示。,2) 算法分析,76,对算法进行分析，主要对时间复杂性进行分析。分析运算量和问题规模之间的关系。,2、最短路算法,1959年，旦捷希(Dantjig）发现了在赋权图中求由点a到点b的最短路好算法，称为顶点标号法。,t (an) : 点an的标号值，表示点 a1=a 到an的最短路长度,Ai =a1,a2, ., ai:已经标号的顶点集合。,Ti : a1到ai的最短路上的边集合,算法叙述如下：,77,(1) 记 a=a1 , t(a1) =0, A1=
33、 a1, T1= ;,(2) 若已经得到 Ai = a1,a2, ai , 且对于 1ni,已知t(an),对每一个an Ai , 求一点：,使得：,(3) 设有mi ，1mii ,而bmi(i)是使 取最小值，令：,(4) 若ai+1=b ,停止，否则，记 ,转(2).,78,时间复杂性分析：,对第i次循环：步骤(2)要进行i次比较运算，步骤(3)要进行i次加法与i次比较运算。所以，该次循环运算量为3i .所以，在最坏的情况下，运算量为n2级，是好算法。,算法证明：,定理1：算法中的函数t(ai)给出了a与ai的距离。,证明：略,79,例1 如图所示，求点a到点b的距离。,解 1. A1=
34、a，t (a) = 0，T1 = ,2. b1 (1)= v3 ;,3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)， T2 =av3;,80,2. A2 =a, v3, b1 (2) =v1, b2 (2) =v2 ;,3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)，,T3 =av3, av1;,2. A3 =a, v3, v1, b1 (3) =v2, b2 (3) =v2 , b3 (3) =v4 ;,3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(
35、v1v4) = 3 (最小)，,T4 =av3, av1, v1v4,2. A4 = a, v3, v1, v4，b1 (4) = v2，b2 (4) = v2，b3 (4) = v2, b4 (4) = v5 ;,3. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)，,T5 =av3, av1, v1v4, v4v5 ;,81,2. A5 = a, v3, v1, v4, v5，b1 (5) = v2，b2 (5) = v2， b3 (5) = v2 , b4 (5) = v2, b5 (5) = v2 ;,3. m5 = 4, t(v2
36、) = t(v4) + l(v4v2) = 7 (最小)，,T6 =av3, av1, v1v4, v4v5, v4v2;,2. A6 = a, v3, v1, v4, v5, v2, b2 (6) = v6, b4 (6) = b， b5 (6) = v6，b6 (6) = v6 ;,3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)，,T7 =av3, av1, v1v4, v4v5, v4v2, v2v6 ;,2. A7 = a, v3, v1, v4, v5, v2, v6, b4 (7) = b，b5 (7) =b， b7 (7
37、) =b ;,3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)，,82,T8 =av3, av1, v1v4, v4v5, v4v2, v2v6, v6b;,于是知a与b的距离,d (a, b) = t (b) = 11,由T8导出的a到b的最短路为：,课外作业,某公司在六个城市C1,C2,C3,C4,C5,C6中有分公司，从Ci到Cj的直接航程票价记在下述矩阵的(i, j)位置上，表示没有直接航程。制作一张任意两城市间的最便宜的路线表。,83,例2 某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。求最少的操作次数能均分酒。
38、,解：设x1,x2,x3分别表示8,5,3升酒壶中的酒量。则,容易算出(x1,x2,x3) 的组合形式共24种。,每种组合用一个点表示，两点连线，当且仅当可通过倒酒的方式相互变换。,若各边赋权为1，则问题转化为在该图中求(8,0,0)到(4,4,0)的一条最短路。结果如下：,84,例3 在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河？,分析：人，狼，羊，菜所有组合形式为：,但是以下组合不能允许出现：,狼羊菜，羊菜，狼羊，人，人狼，人菜，共6种。,岸上只能允许出现10种组合：,人狼羊菜，人狼羊，
39、人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。,每种情况用点表示；,85,两点连线，当且仅当两种情况可用载人(或加一物)的渡船相互转变。,于是，问题转化为求由顶点“人狼羊菜”到顶点“空”的一条最短路。,每条边赋权为1,结果为：,人狼羊菜狼菜人狼菜狼人狼羊羊人羊空；,(2) 人狼羊菜狼菜人狼菜菜人羊菜羊人羊空。,86,(二)、图的代数表示,用邻接矩阵或关联矩阵表示图，称为图的代数表示。用矩阵表示图，主要有两个优点： (1) 能够把图输入到计算机中；(2) 可以用代数方法研究图论。,1、图的邻接矩阵,定义1 设G为n阶图，V=v1, v2, , vn,邻接矩阵A(G)=(aij),其中：,87,例如
40、：写出下图G的邻接矩阵：,解：邻接矩阵为：,88,图G的邻接矩阵的性质,(1)非负性与对称性,由邻接矩阵定义知aij是非负整数，即邻接矩阵是非负整数矩阵；,在图中点vi与vj邻接，有vj与vi邻接，即aij =aji.所以，邻接矩阵是对称矩阵。,(2) 同一图的不同形式的邻接矩阵是相似矩阵。,这是因为，同图的两种不同形式矩阵可以通过交换行和相应的列变成一致。,(3) 如果G为简单图，则A(G)为布尔矩阵;行和(列和)等于对应顶点的度数；矩阵元素总和为图的总度数，也就是G的边数的2倍。,89,(4) G连通的充分必要条件是：A(G)不能与如下矩阵相似,证明：1) 必要性,若不然：设A11对应的顶
41、点是v1,v2, vk , A22对应的顶点为vk+1,vk+2, vn,显然，vi (1ik)与vj (k+1in)不邻接，即G是非连通图。矛盾！,2) 充分性,若不然：设G1与G2是G的两个不连通的部分，并且设V(G1)=v1,v2,vk, V(G2)=vk+1,vk+2,vn, 如果在写,90,G的邻接矩阵时，先排V(G1)中点，再排V(G2)中点，则G的邻接矩阵形式必为：,(5) 定理：设 ，则a ij (k)表示顶点vi到顶点vj的途径长度为k的途径条数。,证明：对k作数学归纳法证明。,当k=1时，由邻接矩阵的定义，结论成立；,设结论对k-1时成立。当为k时：,一方面：先计算Ak ;
42、,91,另一方面：考虑vi到vj的长度为k的途径,设vm是vi到vj的途径中点，且该点和vj邻接。则vi到vj的经过vm且长度为k的途径数目应该为：,所以，vi到vj的长度为k的途径数目为：,即为,例4 求下图中v1到v3的途径长度为2和3的条数。,92,解：由于：,所以，v1到v3的途径长度为2和3的条数分别为：3和4。,推论: (1)A2的元素aii (2)是vi的度数，A3的元素aii (3)是含vi的三角形个数的2倍；,93,(2) 若G是连通的，对于i j , vi和vj间距离是使An的aij (n)0的最小整数。,2、图的关联矩阵,(1) 若G是(n, m) 图。定义G的关联矩阵：
43、,其中：,例如：,94,(2) 关联矩阵的性质,1) 关联矩阵的元素为0，1或2；,2) 关联矩阵的每列和为2；每行的和为对应顶点度数；,95,作业,P29P30 16,96,Thank You !,97,第一章 图的基本概念,本次课主要内容,邻接谱与图的邻接代数,(一)、邻接谱,(二)、图的邻接代数,(三)、图空间简介,98,(一)、邻接谱,1、图的特征多项式,定义1：图的邻接矩阵A(G)的特征多项式：,称为图G的特征多项式。,例1、设单图G的特征多项式为：,求证: (1) a1=0 ; (2) a2= m (G) ;,(3) a3是G中含有不同的K3子图的个数2倍。,99,证明：由矩阵理论
44、：对每个1in,(-1)iai是A(G)的所有i阶主子式之和。,(1) 由于A(G)的主对角元全为零，所以所有1阶主子式全为零，即：a1=0 ;,这样的一个2阶主子式对应G中的一条边，反之亦然，所以，有：,(2) 对于单图G, A(G)中非零的2阶主子式必为如下形式：,100,这样的一个3阶主子式对应G中的一个K3，反之亦然.设G中有S个K3, 则：,(3) 对于单图G, A(G)中非零的3阶主子式必为如下形式：,101,2、图的邻接谱,定义2：图的邻接矩阵A(G)的特征多项式的特征值及其重数，称为G的邻接谱。,例2、求出K n的谱。,解：K n的邻接矩阵为：,102,于是：,103,所以：,
45、例3，若两个非同构的图具有相同的谱，则称它们是同谱图。求证：下面两图是同谱图。,104,证明：G与H显然不同构。,通过直接计算：,所以G与H是同谱图。,例4，设单图A(G)的谱为：,则：,证明：由矩阵理论：,105,a ii (2)表示点vi的度数，由握手定理：,即：,例5，设是单图G = (n, m)的任意特征值，则：,证明：不失一般性，设=1，2，,n是G的全体特征值。,G是单图，有：,106,又由例4，有：,对向量(1,1,1)与(2,3,4,n)用柯西不等式得：,所以，有：,由(1)与(2)得：,107,注：对于图谱的研究，开始于二十世纪60年代。形成了代数图论的主要研究方向之一。图谱
46、研究在流体力学，量子化学，量子物理与非线性物理以及网络技术中都有重要的应用。国内，中国科技大学数学系是最早展开该课题研究的单位(1978年就有很好的研究成果)。他们对图论的研究主要有两个方面：一是图谱问题，二是组合网络研究，也有达到国际水平的研究成果(1994年开始).关于组合网络问题，将在第三章作一些介绍。,108,(二)、图的邻接代数,1、图的邻接代数的定义,定义3：设A是无环图G的邻接矩阵，称：,对于矩阵的加法和数与矩阵的乘法来说作成数域C上的向量空间，称该空间为图G的邻接代数。,注： 向量空间的定义可简单地记为“非空”、“两闭”、“八条”,2、图的邻接代数的维数特征,109,定理1：G
47、为n阶连通无环图，则：,证明：由哈密尔顿凯莱定理(见北大数学力学系高等代数)：,所以：,下面证明：E, A, A2, , A d (G)线性无关！,若不然，则存在不全为零的数a0 ,a1 , , a d (G) ,使：,110,设a m-10 , 但当k m 时，有a k =0. 于是有：,假定：v1 v2 v d(G)+1 是G中一条最短的 (v1, v d(G)+1)路，易知：d (G) n.,于是，d(v1, v m ) = m-1 , (m=1, 2, , d (G)+1),注意到：A k的元素a1m (k)在 k 0,所以， 的一行m列元为am-1a1m (m-1)0，这样有：,11
48、1,产生矛盾！,定理结果分析：不等式右端的界是紧的！,因为：n点路的直径为n-1, 所以，此时该路的邻接代数的维数正好为n。,此外：当G为K n时，有：,112,定理2：集合：,对于图的对称差运算和数乘运算：,(三)、图空间简介,来说作成数域 F = 0, 1 上的m维向量空间。,注：图空间概念是网络图论中的一个基本概念。研究通信网络，如果要用图论方法，建议参看陈树柏的网络图论及其应用，科学出版社，1982年。学习网络图论的主要基础是电工学与矩阵理论知识。,113,证明: (1) 证明M是F上的向量空间，只需要验证“两闭”与“八条”即可。,(2) M的维数为m,令,又令：,可以证明：g1,g2
49、,gm为M的一组基！,事实上：对,若E(Gi)=ei1,ei2,eik,则：,114,另一方面：若,则：c1=c2= = cm =0,所以：,115,作业,设G是一个r度正则图，证明：,r是G的的一个特征值；,(2) 特征值r的重数等于G的连通分支数；,(3) G的任意特征值满足：,116,Thank You !,117,第一章 图的基本概念,本次课主要内容,极图理论简介,(一)、l 部图的概念与特征,(二)、托兰定理,(三)、托兰定理的应用,(四)、交图与团图简介,118,1978年，数学家Bollobas写了一本书极值图论(Extremal Graph）,是关于极值图论问题的经典著作。,P
50、. Erds是该研究领域的杰出人物。他是数学界的传奇人物，国际图论大师，获过Wolf数学奖。他是20世纪最伟大的数学家之一，也是人类历史上发表数学论文最多的数学家(1000多篇),第二名是欧拉(837篇)。他于1996年9月20日因心脏病去世，享年83岁，他的逝世当时惊动了整个数学界。,极图属于极值图论讨论的范畴，主要研究满足某个条件下的最大图或最小图问题。,上世纪70年代末，极值图论已经形成了相对完整的理论体系，但还有很多引人入胜的公开性问题没有解决，所以，直到现在，它仍然是重要研究方向。但是，该方向是比较困难的数学研究方向之一。,119,本次课，主要介绍极值图论中的一个经典结论：托兰定理。
