图论及其应用文档资料

《图论及其应用文档资料》由会员分享，可在线阅读，更多相关《图论及其应用文档资料（854页珍藏版）》请在装配图网上搜索。

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1 图论及其应用图论及其应用任课教师：杨春任课教师：杨春数学科学学院数学科学学院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2图论及其应用图论及其应用 作者作者:张先迪、李正良张先迪、李正良 购买地点：教材科购买地点：教材科 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3参考文献参考文献1 美，帮迪图论及其应用美，帮迪图论及其应用2 美，美，Gary Cha

2、rtrand图论导引图论导引，人民邮电，人民邮电出版社，出版社，20073 Bela Bollobas，现代图论，现代图论，科学出版社，科学出版社，2001 中国科学院研究生教学丛书中国科学院研究生教学丛书4 美，美，Fred Buckley图论简明教程图论简明教程，清华大学，清华大学出版社，出版社，2005 李慧霸李慧霸 王风芹译王风芹译 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 45 李尉萱，图论，湖南科学技术出版社，李尉萱，图论，湖南科学技术出版社，19796 美，美，Douglas B.West图论导引图论导引，机械工业

3、出，机械工业出版社，版社，2007 李建中，骆吉洲译李建中，骆吉洲译7 杨洪，图论常用算法选编，中国铁道出版社，杨洪，图论常用算法选编，中国铁道出版社，19888 陈树柏，网络图论及其应用，科学出版社，陈树柏，网络图论及其应用，科学出版社，1982 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 59 Chris Godsil，Gordon Royle Algebraic Graph Theory，世界图书出版公司北京公司，世界图书出版公司北京公司，200410 王朝瑞，图论，高等教育出版社，王朝瑞，图论，高等教育出版社，1983 0

4、.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容图的概念与图论模型图的概念与图论模型(一一)、图论课程简介、图论课程简介(二二)、图的定义与图论模型、图的定义与图论模型(三三)、图的同构、图的同构 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 71 1、研究对象、研究对象 图论是研究点与线组成的图论是研究点与线组成的“图形图形”问题的一门科问题的一门科学。属于应用数学分支学。属于应用数学分支.(一一)、图论课

5、程简介、图论课程简介2 2、发展历史、发展历史 图论起源于图论起源于18世纪的世纪的1736年，标志事件是年，标志事件是“哥尼哥尼斯堡七桥问题斯堡七桥问题.数学家欧拉被称为数学家欧拉被称为“图论之父图论之父”.20世纪世纪30年代出版第一本图论著作年代出版第一本图论著作.0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 83 3、应用状况、应用状况 图论的应用已经涵盖了人类学、计算机科学、化图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数

6、学本身等通管理、电信以及数学本身等。目前，图论已形成很多分支：如随机图论、网络目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。图论、代数图论、拓扑图论、极值图论等。4 4、教学安排、教学安排 主要介绍图的一些基本概念、基本理论和图论的主要介绍图的一些基本概念、基本理论和图论的典型应用。典型应用。60学时。学时。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 91 1、图的定义、图的定义(二二)、图的定义与图论模型、图的定义与图论模型 一个图是一个序偶一个图是一个序偶，记为，记为G=(V,E),其中：其中

7、：(1)V是一个有限的非空集合，称为顶点集合是一个有限的非空集合，称为顶点集合,其其元素称为顶点或点。用元素称为顶点或点。用|V|V|表示顶点数；表示顶点数；(2)E是由是由V中的点组成的无序对构成的集合，称中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在为边集，其元素称为边，且同一点对在E中可以中可以重复出现多次。用重复出现多次。用|E|E|表示边数。表示边数。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10图可以用图形表示：图可以用图形表示：V中的元素用平面上一个黑点表示，中的元素用平面上一个黑点表示，E中的

8、元素用一条连接中的元素用一条连接V中相应点对的任意形状的线表示。中相应点对的任意形状的线表示。例例1、设图、设图G。这里。这里Vv1,v2,v3,v4Ee1,e2,e3,e4,e5,e6，e e1 1(v(v1 1,v,v2 2)，e e2 2(v(v1 1,v,v3 3)，e e3 3(v(v1 1,v,v4 4)，e e4 4(v(v2 2,v,v3 3)，e e5 5(v(v3 3,v,v2 2)，e e6 6(v(v3 3,v,v3 3)。v1v2v3v4e1e2e3e4e5e6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

9、 11图的相关概念：图的相关概念：有限图：顶点集和边集都有限的图称为有限图；有限图：顶点集和边集都有限的图称为有限图；平凡图：只有一个顶点的图称为平凡图；平凡图：只有一个顶点的图称为平凡图；空图：边集为空的图称为空图；空图：边集为空的图称为空图；n阶图：顶点数为阶图：顶点数为n的图称为的图称为n阶图；阶图；(n,m)图：顶点数为图：顶点数为n,边数为边数为m的图称为的图称为(n,m)图；图；边的重数：连接两个相同顶点的边的条数称为边的重数；边的重数：连接两个相同顶点的边的条数称为边的重数；重数大于重数大于1的边称为重边；的边称为重边；环：端点重合为一点的边称为环；环：端点重合为一点的边称为环；

10、简单图：无环无重边的图称为简单图；其余的图称为简单图：无环无重边的图称为简单图；其余的图称为复合图；复合图；0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12顶点顶点u与与v相邻接：顶点相邻接：顶点u与与v间有边相连接；其中间有边相连接；其中u与与v称为称为该边的两个端点；该边的两个端点；顶点顶点u与边与边e相关联：顶点相关联：顶点u是边是边e的端点；的端点；边边e1与边与边e2相邻接：边相邻接：边e1与边与边e2有公共端点；有公共端点；2 2、图论模型、图论模型为了抽象和简化现实世界，常建立数学模型。图是关系的为了抽象和简化现实世

11、界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。模型。(1)化学中的图论模型化学中的图论模型19世纪，化学家凯莱用图论研究简单烃世纪，化学家凯莱用图论研究简单烃即碳氢化合物即碳氢化合物 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13用点抽象分子式中的碳原子和氢原子，用边抽象原子间用点抽象分子式中的碳原子和氢原子，用边抽象原子间的化学键。的化学键。通过这样的建模，能很好研究简单烃的同分异构现象通过这样的建模，能很好研究简单烃的同分异构现象.

12、例如：例如：C4H10的两种同分异构结构图模型为：的两种同分异构结构图模型为：hhhhhhhhhhhhhhhhhhhh 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14(2)商业中的图论模型商业中的图论模型商业中，经常用图来对仓库和零售店进行建模商业中，经常用图来对仓库和零售店进行建模例如：令例如：令V=w1,w2,w3,r1,r2,r3,r4,r5代表代表3个仓库和个仓库和5个零售点个零售点E=w1r1,w1r2,w2r2,w2r3,w2r4,w3r3,w3r5代表每个仓库和每个代表每个仓库和每个零售店间的关联。则图模型图形为：

13、零售店间的关联。则图模型图形为：w1r1r2w2r3r4w3r5(3)最短航线问题最短航线问题 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15用点表示城市，两点连线当且仅当两城市有航线。为了用点表示城市，两点连线当且仅当两城市有航线。为了求出两城市间最短航线，需要在线的旁边注明距离值。求出两城市间最短航线，需要在线的旁边注明距离值。例如：令例如：令V=a,b,c,d,e代表代表5个城市个城市E=a b,ad,b c,be,de代表城市间的直达航线代表城市间的直达航线则航线图的图形为：则航线图的图形为：abcde500320140

14、430370请求出从请求出从d到到c的最短路的最短路 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16(4)任务分配问题任务分配问题 有一个旅行团要组织一批人去旅游，其中一些人是朋友有一个旅行团要组织一批人去旅游，其中一些人是朋友他们要乘坐公共汽车去，而车上的位子是成对的。因此他们要乘坐公共汽车去，而车上的位子是成对的。因此为了让大家旅途更愉快，旅行团负责人需要将成对的朋为了让大家旅途更愉快，旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。友安排在一起。给出一种安排方案。该问题可以建立一个图论模型来解决：旅行团的人抽象该

15、问题可以建立一个图论模型来解决：旅行团的人抽象为图的顶点，两个顶点连线，当且仅当两个顶点代表的为图的顶点，两个顶点连线，当且仅当两个顶点代表的人是朋友。人是朋友。问题归结于在模型图中求所谓的问题归结于在模型图中求所谓的“匹配匹配”，关于图的匹配，关于图的匹配将在第五章介绍。将在第五章介绍。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17(5)考试时间安排问题考试时间安排问题 一个教授需要对期末考试时间进行安排，使得学生们一个教授需要对期末考试时间进行安排，使得学生们不会有相互冲突的考试。如何解决？不会有相互冲突的考试。如何解决？该

16、问题可以建立一个图论模型来解决：待考的课程可该问题可以建立一个图论模型来解决：待考的课程可抽象为图的顶点，连接两个顶点的边表示至少有一个学生抽象为图的顶点，连接两个顶点的边表示至少有一个学生同时选择了这两门课程。同时选择了这两门课程。问题归结于在模型图中求所谓的问题归结于在模型图中求所谓的“顶点着色方案顶点着色方案”问题，问题，该问题将在第七章讨论。该问题将在第七章讨论。例如：有例如：有a,b,c,d,e,f 六门课程。按照上面方法建立六门课程。按照上面方法建立的模型图如下：的模型图如下：0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

17、 18 一种可行的安排方案为：第一时间：一种可行的安排方案为：第一时间：a,d,e;第二时间：第二时间：b,f；最后：；最后：c.abcefd 另一种可行的安排方案为：第一时间：另一种可行的安排方案为：第一时间：a,e;第二时间：第二时间：c,d；最后：；最后：b,f.(6)旅行售货员问题旅行售货员问题 一电脑代理商要从她所在城市出发，乘飞机去六个城市，一电脑代理商要从她所在城市出发，乘飞机去六个城市，然后回到出发点，如果要求每个城市只经历一次，能否办然后回到出发点，如果要求每个城市只经历一次，能否办到？给出行走方案。到？给出行走方案。0.8 1 0.6 0.4 0.2 0 x t 0 0.5

18、 1 1.5 2 1 0.5 0 0.5 1 n 19 问题归结为在模型图中寻求所谓的问题归结为在模型图中寻求所谓的“哈密尔顿圈哈密尔顿圈”问题。问题。将在第四章介绍。将在第四章介绍。例如：如果模型图如下：例如：如果模型图如下：该问题可以建立一个图论模型来解决：城市抽象为该问题可以建立一个图论模型来解决：城市抽象为图的顶点，边代表城市间的直达航线。图的顶点，边代表城市间的直达航线。abcdef 可行方案可行方案:(1)h,d,e,c,b,a,h (2)h,d,e,c,a,b,h 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 在

19、图论中，一个很值得研究的问题是如何比较两个在图论中，一个很值得研究的问题是如何比较两个图的异同，这就是图的同构问题。图的异同，这就是图的同构问题。定义：设有两个图定义：设有两个图G1=(V1,E1)和和G2=(V2,E2),若在其顶点若在其顶点集合间存在双射，使得边之间存在如下关系：设集合间存在双射，使得边之间存在如下关系：设u1u2v1v2,u1,v1 V1,u2,v2 V2;u1v1 E1,当且仅当当且仅当u2v2 E2,且且u1v1与与u2v2的重数相同。称的重数相同。称G1与与G2同构，记为：同构，记为：由定义可以得到图同构的几个必要条件：由定义可以得到图同构的几个必要条件：(三三)、

20、图的同构、图的同构12GG(1)顶点数相同；顶点数相同；(2)边数相同；边数相同；(3)关联边数相同的顶点关联边数相同的顶点个数相同。个数相同。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 判定图的同构是很困难的，属于判定图的同构是很困难的，属于NP完全问题。对于规模完全问题。对于规模不大的两个图，判定其是否同构，可以采用观察加推证的不大的两个图，判定其是否同构，可以采用观察加推证的方法。方法。例例2 证明下面两图不同构。证明下面两图不同构。u1v1证明证明:u1的两个邻接点与的两个邻接点与v1的两个邻接点状况不同。所以，的两

21、个邻接点状况不同。所以，两图不同构。两图不同构。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 例例3 证明下面两图同构。证明下面两图同构。证明证明:作映射作映射f:vi ui (i=1,2.10)(a)v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10(b)容易证明，对容易证明，对 vi v j E(a),有有f(v i vj,),ui,uj,E,(b)(1 i 10,1 j 10)由图的同构定义知，图由图的同构定义知，图(a)与与(b)是同构的。是同构的

22、。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 例例4 指出指出4个顶点的非同构的所有简单图。个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为分析：四个顶点的简单图最少边数为0，最多边数为，最多边数为6，所以，所以可按边数进行枚举。可按边数进行枚举。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24作业作业P29P30 3,4,5,6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25Than

23、k You!0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容(二二)、顶点的度与图的度序列、顶点的度与图的度序列(一一)、完全图、偶图与补图、完全图、偶图与补图 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27(一一)、完全图、偶图与补图、完全图、偶图与补图1、每两个不同的顶点之间都有一条边相连的简单图称为、每两个不同的顶点之间都有一条边相连的简单图称为完全图完全图.在同构意义下，在同构意义下，n个顶点

24、的完全图只有一个，记为个顶点的完全图只有一个，记为 KnK2K3K5容易求出：容易求出：1()(1)2nm Kn n 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 2、所谓具有二分类（、所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，）的偶图（或二部图）是指一个图，它的点集可以分解为两个它的点集可以分解为两个(非空非空)子集子集X和和Y，使得每条边的一个，使得每条边的一个端点在端点在X中，另一个端点在中，另一个端点在Y中中.完全偶图是指具有二分类（完全偶图是指具有二分类（X,Y）的简单偶图，其中）的简单偶图，其中X的每个

25、顶点与的每个顶点与Y的每个顶点相连，若的每个顶点相连，若|X|=m，|Y|=n，则这样，则这样的偶图记为的偶图记为 K m,n 图图1图图2 图图1与图与图2均是偶图，图均是偶图，图2是是K2,3 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 偶图是一种常见数学模型。偶图是一种常见数学模型。例例1 学校有学校有6位教师将开设位教师将开设6门课程。六位教师的代号是门课程。六位教师的代号是xi（i=1,2,3,4,5,6)，六门课程代号是，六门课程代号是yi（i=1,2,3,4,5,6)。已知，。已知，教师教师x1能够胜任课程能够

26、胜任课程y2和和y3；教师；教师x2能够胜任课程能够胜任课程y4和和y5；教师教师x3能够胜任课程能够胜任课程y2；教师；教师x4能够胜任课程能够胜任课程y6和和y3；教师教师x5能够胜任课程能够胜任课程y1和和y6；教师；教师x6能够胜任课程能够胜任课程y5和和y6。请画出老师和课程之间的状态图。请画出老师和课程之间的状态图。x1x5x4x3x2x6y4y3y1y2y5y6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 303、对于一个简单图、对于一个简单图G=（V,E），令集合），令集合1,Euv uv u vV则称图则称图H=

27、（V，E1E）为）为G的补图，记为的补图，记为 HGHG例如，下面两个图互为补图。例如，下面两个图互为补图。G1G2 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31HG定理：若定理：若n阶图阶图G是自补图是自补图(),则有：则有：GG0,1(mod 4)n 证明：证明：n阶图阶图G是自补图，则有：是自补图，则有：补图是相对于完全图定义的。补图是相对于完全图定义的。补图是图论中经常涉及的概念，在图论研究中有重补图是图论中经常涉及的概念，在图论研究中有重要的作用要的作用如果图如果图G与其补图同构，则称与其补图同构，则称G为自补图。为

28、自补图。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 32HG所以：所以：1()()()(1)2nm Gm GmKn n0,1(mod 4)n 由于由于n是正整数，所以：是正整数，所以：1()(1)4m Gn n 自补图是很有意义的图类。它在对角型拉姆齐数自补图是很有意义的图类。它在对角型拉姆齐数方面的研究、关于图的香农容量的研究、强完美图方面的研究、关于图的香农容量的研究、强完美图方面的研究等都有重要作用。方面的研究等都有重要作用。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5

29、1 n 33HG(二二)、顶点的度与图的度序列、顶点的度与图的度序列G的顶点的顶点v的度的度d(v)是指是指G中与中与v关联的边的数目，关联的边的数目，每个环计算两次。每个环计算两次。1、顶点的度及其性质、顶点的度及其性质分别用分别用(G)(G)和和(G)(G)表示图表示图G G的最小与最大度。的最小与最大度。例例2 在在10个顶点以下的单图中，哪些阶数的图可能个顶点以下的单图中，哪些阶数的图可能为自补图？画出为自补图？画出8阶的阶的4个自补图个自补图(共共10个个)。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 34HG奇数度的顶

30、点称为奇点，偶数度的顶点称偶点。奇数度的顶点称为奇点，偶数度的顶点称偶点。设设G=(V,E)为简单图，如果对所有为简单图，如果对所有 ，有，有vVd(v)=k，称图，称图G为为k-正则图正则图 定理：定理：图图G=(V,E)中所有顶点的度的和等于边数中所有顶点的度的和等于边数m的的2倍，即：倍，即：()()2vVGdvm证明：由顶点度的定义知：图中每条边给图的总证明：由顶点度的定义知：图中每条边给图的总度数贡献度数贡献2度，所以，总度数等于边数度，所以，总度数等于边数2倍。倍。注：该定理称为图论第一定理，是由欧拉提出的。注：该定理称为图论第一定理，是由欧拉提出的。欧拉一身发表论文欧拉一身发表论

31、文886篇，著作篇，著作90部。该定理还有部。该定理还有一个名字：一个名字：“握手定理握手定理”。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 35HG推论推论1 在任何图中，奇点个数为偶数。在任何图中，奇点个数为偶数。证明：设证明：设V1,V2分别是分别是G中奇点集和偶点集中奇点集和偶点集.则由则由握手定理有：握手定理有：12v Vv Vv Vd vd vd v是偶数，由于是偶数，由于 是偶数，是偶数，所以所以 是是偶数，于是偶数，于是 是偶数。是偶数。2v Vdv 1v Vdv1V推论推论2 正则图的阶数和度数不同时为奇数正则图

32、的阶数和度数不同时为奇数。证明证明：设设G是是k-正则图，若正则图，若k为奇数，则由推论为奇数，则由推论1知知正则图正则图G的点数必为偶数的点数必为偶数 例例4 与与是简单图是简单图G的最大度与最小度，求证：的最大度与最小度，求证：2 mn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 36HG()()2vVGndvmn证明：由握手定理有：证明：由握手定理有：所以有：所以有：2 mn 2、图的度序列及其性质、图的度序列及其性质一个图一个图G的各个点的度的各个点的度d1,d2,dn构成的非负整数组构成的非负整数组(d1,d2,dn)称

33、为称为G的度序列的度序列。任意一个图任意一个图G对应唯一一个度序列，图的度序列是对应唯一一个度序列，图的度序列是刻画图的特征的重要刻画图的特征的重要“拓扑不变量拓扑不变量”。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 37HG 图图G 的的“拓扑不变量拓扑不变量”是指与图是指与图G有关的一个有关的一个数数或数组或数组(向量向量)。它对于与图。它对于与图G同构的所有图来说，同构的所有图来说，不会发生改变。不会发生改变。一个图一个图G可以对应很多拓扑不变量。如果某组不可以对应很多拓扑不变量。如果某组不变量可完全决定一个图，称它为不变量

34、的完全集。变量可完全决定一个图，称它为不变量的完全集。定理：非负整数组定理：非负整数组(d1,d2,.,d n)是图的度序列的是图的度序列的充分必要条件是：充分必要条件是：为偶数。为偶数。1niid证明：必要性由握手定理立即得到。证明：必要性由握手定理立即得到。如果如果 为偶数，则数组中为奇数的数字个数为偶数，则数组中为奇数的数字个数1niid必为偶数。按照如下方式作图必为偶数。按照如下方式作图G:若若di为偶数，则在为偶数，则在与之对应的点作与之对应的点作di/2个环；对于剩下的偶数个奇数，个环；对于剩下的偶数个奇数，0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

35、 1 0.5 0 0.5 1 n 38HG两两配对后分别在每配对点间先连一条边，然后两两配对后分别在每配对点间先连一条边，然后在每个顶点画在每个顶点画dj-1/2个环。该图的度序列就是已知个环。该图的度序列就是已知数组。数组。一个非负数组如果是某简单图的度序列，我们称一个非负数组如果是某简单图的度序列，我们称它为可图序列，简称图序列。它为可图序列，简称图序列。关于图序列，主要研究关于图序列，主要研究3个问题：个问题：(1)存在问题：什么样的整数组是图序列？存在问题：什么样的整数组是图序列？(2)计数问题：一个图序列对应多少不同构的图？计数问题：一个图序列对应多少不同构的图？(3)构造问题：如何

36、画出图序列对应的所有不同构图？构造问题：如何画出图序列对应的所有不同构图？研究现状研究现状:(1)彻底解决了，彻底解决了，(2)解决得不好，解决得不好，(3)没有解决。没有解决。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 39HG定理：非负整数组定理：非负整数组12121(,),2nnniidddddddm是图序列的充分必要条件是：是图序列的充分必要条件是：1112312(1,1,1,)ddnddddd是图序列。是图序列。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4

37、0HG例例5 是否为图序列？如果是，是否为图序列？如果是，作出对应的一个简单图。作出对应的一个简单图。(6,5,4,3,2,2,2)解：解：1(4,3,2,1,1,1)2(2,1,0,0,1)由于由于 是图序列，所以原序列是是图序列，所以原序列是图序列。图序列。2(2,1,0,0,1)0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 41HG定理定理:(厄多斯厄多斯1960)非负整数组非负整数组12121(,),2nnniidddddddm是图序列的充分必要条件是：是图序列的充分必要条件是：11(1)min,11rniiii rdr r

38、r drn 该定理证明很难！该定理证明很难！上世纪上世纪60年代以来，人们又研究所谓的唯一图序列问题。年代以来，人们又研究所谓的唯一图序列问题。例例5就是一个唯一图序列！就是一个唯一图序列！0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 42HG定理定理:一个满足一个满足d2=dn-1的图序列的图序列12(,)nddd1(1),1,1,2nndddnn是唯一图序列的充分必要条件是下列条件之一满足：是唯一图序列的充分必要条件是下列条件之一满足：1(2),2,5nddn12(3),1nddd121(4),2,1,2nddddnn11(5)

39、,2nnnddd11(6),31nnnddd12(7),13,6nndddn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 43HG3、图的频序列及其性质、图的频序列及其性质定理：定理：一个简单图一个简单图G的的n个点的度不能互不相同个点的度不能互不相同 证明：证明：因为图因为图G为简单图为简单图，所以所以：(G)n-1。情形情形1：若：若G没有孤立点，则没有孤立点，则 1()1,()d vnvV G 由鸽笼原理：必有两顶点度数相同；由鸽笼原理：必有两顶点度数相同；情形情形2：若：若G只有一个孤立点，设只有一个孤立点，设G1表示表示

40、G去掉孤去掉孤立点后的部分，则：立点后的部分，则：11()2,()d vnvV G 由鸽笼原理：在由鸽笼原理：在G1里必有两顶点度数相同；里必有两顶点度数相同；情形情形3：若：若G只有两个以上的孤立点，则定理显然只有两个以上的孤立点，则定理显然成立。成立。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 44HG定义：定义：设设n阶图阶图G的各点的度取的各点的度取s个不同的非负整数个不同的非负整数d1,d2,ds。又设度为。又设度为di的点有的点有bi个个(i=1,2,s)，则，则 1siibn故非整数组故非整数组(b1,b2,bs)是

41、是n的一个划分，称为的一个划分，称为G的频的频序列。序列。定理：定理：一个一个n阶图阶图G和它的补图有相同的频序列。和它的补图有相同的频序列。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 45作业作业P29P30 8,9,10,11 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 46Thank You!0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 47第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主

42、要内容子图、图运算、路与连通性子图、图运算、路与连通性(一一)、子图的相关概念、子图的相关概念(三三)、路与连通性、路与连通性(二二)、图运算、图运算 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 481 1、子图、子图简单地说，图简单地说，图G的任意一部分的任意一部分(包括本身包括本身)都称为是图都称为是图G的的的一个子图。的一个子图。定义定义1 1 如果如果(一一)、子图的相关概念、子图的相关概念()(),()()VHVGEHE G且且H H中边的重数不超过中边的重数不超过G G中对应边的条数，则称中对应边的条数，则称H H为为

43、G G的子图，记为的子图，记为HG当当 时，称时，称H H是是G G的真子图，记为的真子图，记为 ,HGHGHG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 492 2、点与边的导出子图、点与边的导出子图(1)图图G的顶点导出子图的顶点导出子图定义定义2 2 如果如果 ，则以，则以 为顶点集，为顶点集，以两个端点均在以两个端点均在 中的边集组成的图，称为中的边集组成的图，称为图图G G的点导出子图。记为：的点导出子图。记为：()VVG G V V V 例例1 如图所示，求如图所示，求 。其中。其中G V 1,3,5V 12345图

44、图G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 50解：由点导出子图的定义得：解：由点导出子图的定义得：GV135(2)图图G的边导出子图的边导出子图定义定义3 3 如果如果 ，则以，则以 为边集，为边集，以以 中边的所有端点为顶点集组成的图，称为中边的所有端点为顶点集组成的图，称为图图G G的边导出子图。记为：的边导出子图。记为：()EE G E E G E 例例2 如图所示，求如图所示，求 。其中。其中G E 13,24,35E 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.

45、5 1 n 51解：由边导出子图的定义得：解：由边导出子图的定义得：12345图图GGE 12345 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 523 3、图的生成子图、图的生成子图定义定义3 3 如果图如果图G G的一个子图包含的一个子图包含G G的所有顶点，称的所有顶点，称该子图为该子图为G G的一个生成子图的一个生成子图例例2 如图所示，求如图所示，求G的所有生成子图的所有生成子图123图图G解：按边数分别求出解：按边数分别求出 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0

46、.5 1 n 53定理：简单图定理：简单图G=(n,m)的所有生成子图个数为的所有生成子图个数为2m(二二)、图运算、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。作，称为图运算。图运算形式很多。1、图的删点、删边运算、图的删点、删边运算(1)、图的删点运算、图的删点运算设设 ，在，在G中删去中删去 中的顶点和中的顶点和G中与之关联的所有边中与之关联的所有边的

47、操作，称为删点运算。记为的操作，称为删点运算。记为()VVG V GV 特别地，如果只删去一个点特别地，如果只删去一个点v，则记为，则记为G-v.0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 54(2)、图的删边运算、图的删边运算设设 ，在，在G中删去中删去 中的所有边的操作，称为删边运算。中的所有边的操作，称为删边运算。记为记为()EE G E GE 特别地，如果只删去一条边特别地，如果只删去一条边e，则记为，则记为G-e.注：删点、删边后得到的图是原图的子图。注：删点、删边后得到的图是原图的子图。2、图的并运算、图的并运算 设设

48、G1,G2是是G的两个子图，的两个子图，G1与与G2并是指由并是指由 为为顶点集，以顶点集，以 为边集组成的子图。记为：为边集组成的子图。记为：12()()VGVG12()()EGEG12GG 特别是，如果特别是，如果G1,G2不相交不相交(没有公共顶点没有公共顶点)，称它们的并为直接并，称它们的并为直接并，可以记为：可以记为：12GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 552、图的交运算、图的交运算 设设G1,G2是是G的两个子图，的两个子图，G1与与G2交是指由交是指由 为为顶点集，以顶点集，以 为边集组成的子图。记

49、为：为边集组成的子图。记为：12()()VGVG12()()EGEG12GG 设设G1,G2是两个图，是两个图，G1与与G2的差是指从的差是指从G1中删去中删去G2中的边得到的中的边得到的新图。记为新图。记为G1-G2.3、图的差运算、图的差运算4、图的对称差运算、图的对称差运算(或环和运算或环和运算)设设G1,G2是两个图，是两个图，G1与与G2的对称差定义为：的对称差定义为：121212()()GGGGGG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 56例例3 已知已知G1与与G2，求，求12GG12GG12GG21GG12

50、GG1234abcdefG1h2354cdegijG2解：由相应运算定义得下面结果：解：由相应运算定义得下面结果：1234abcdef5hgij12GG234cde12GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5712GG123abf21GGh2354gij1234abf5hgij12GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 585、图的联运算、图的联运算 设设G1,G2是两个不相交的图，作是两个不相交的图，作G1+G2，并且将，并且将G1中每个顶点和

51、中每个顶点和G2中的每个顶点连接，这样得到的新图称为中的每个顶点连接，这样得到的新图称为G1与与G2的联图。记为的联图。记为：12GG例例4 已知已知G1与与G2，求，求12GG21G1345G2解：由联图的定义得：解：由联图的定义得：2134512GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 596、图的积图、图的积图 设设 是两个图。对点集是两个图。对点集111222(,),(,),GVEGVE12VVV 的任意两个点的任意两个点u=(u1,u2)与与v=(v1,v2),当当(u1=v1和和u2adjv2)或或(u2=v2

52、和和u1adjv1)时，把时，把u与与v相连。如此得到的新图称为相连。如此得到的新图称为G1与与G2的的积图。记为积图。记为12GGG 例例5 已知已知G1与与G2，画，画12GGGG112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)12GGG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 606、图的合成图、图的合成图 设设 是两个图。对点集是两个图。对点集111222(,),(,),GVEGVE12VVV 的任意两个点的任意两个点u=(u1,u2)与与v=(v1,v2),当当(u1adjv1)或或(u1

53、=v1和和u2adjv2)时，把时，把u与与v相连。如此得到的新图称为相连。如此得到的新图称为G1与与G2的的合成图。记为合成图。记为12GGG 例例6 已知已知G1与与G2，画，画G112G234512GGG(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)12GGG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 61 图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的采用所谓的“超立方体超立方体”结构。采用该结构可使网络具有较好的可结构。采用该结构

54、可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。“超立方体超立方体”可以采用积图来递归构造。定义如下：可以采用积图来递归构造。定义如下：(1)1方体方体12QK(2)n方体定义为：方体定义为：21nnQKQQ1Q3Q2 “超立方体超立方体”常采用下面简单的递归构造方法：常采用下面简单的递归构造方法：0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 62 n方体方体Q n的顶点可用一个长度为的顶点可用一个长度为n的二进制码来表示。的二进制码来表示。

55、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的性质研究，可以查阅到很多文献。经典文章是：

56、的性质研究，可以查阅到很多文献。经典文章是：Saad Y,Schultz M H.Topological properties of hypercubes J.IEEETrans.Comput.1988,37(7):867-8727、图的联合、图的联合 把把G1的一个顶点和的一个顶点和G2的一个顶点粘合在一起后得到的新图称为的一个顶点粘合在一起后得到的新图称为G1与与G2的联合。记为：的联合。记为：12GGG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 63(三三)、路与连通性、路与连通性 对图的路与连通性进行研究，在计算机网络研

57、究中有十分重要的对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。性也是主要问题之一，它与图的连通性问题相对应。1、路与连通性的相关概念、路与连通性的相关概念(1)、图中的途径、图中的途径 G的一条途径（或通道或通路）是指一个有限非空序列的一条途径（或通道或通路）是指一个有限非空序列w=v0 e1 v1 e2 v2

58、ek vk，它的项交替地为顶点和边，使得，它的项交替地为顶点和边，使得 ，ei的端点是的端点是vi-1和和vi.1ik 途径中边数称为途径的长度；途径中边数称为途径的长度；v0,vk分别称为途径的起点与终点，分别称为途径的起点与终点，其余顶点称为途径的内部点。其余顶点称为途径的内部点。(2)、图中的迹、图中的迹 边不重复的途径称为图的一条迹。边不重复的途径称为图的一条迹。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 64 图中顶点图中顶点u与与v的距离：的距离：u与与v间最短路的长度称为间最短路的长度称为u与与v间距离。记为间距离。

59、记为d(u,v).如果如果u与与v间不存在路，定义间不存在路，定义d(u,v)=.(3)、图中的路、图中的路(4)、图中两顶点的距离、图中两顶点的距离注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹 与圈。闭迹也称为回路。长度为与圈。闭迹也称为回路。长度为k的圈称为的圈称为k圈，圈，k为奇数时称为奇为奇数时称为奇 圈，圈，k为偶数时称为偶圈。为偶数时称为偶圈。顶点不重复的途径称为图的一条路。顶点不重复的途径称为图的一条路。(5)、图中两顶点的连通性、图中两顶点的连通性 图图G中点中点u与与v说是连通的，如果说是连通的，如果u与与v

60、间存在通路。否则称间存在通路。否则称u与与v不连不连通。点的连通关系是等价关系。通。点的连通关系是等价关系。如果图如果图G中任意两点是连通的，称中任意两点是连通的，称G是连通图，否则，称是连通图，否则，称G是非连通是非连通图。非连通图中每一个极大连通部分，称为图。非连通图中每一个极大连通部分，称为G的连通分支。的连通分支。G的连通的连通分支的个数，称为分支的个数，称为G的分支数，记为的分支数，记为()G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 65(6)、图的直径、图的直径 连通图连通图G的直径定义为：的直径定义为：()m a

61、 x(,),()dGduvuvVG 如果如果G不连通，图不连通，图G的直径定义为的直径定义为()d G 例例7 证明：在证明：在n阶连通图中阶连通图中(1)至少有至少有n-1条边；条边；(2)如果边数大于如果边数大于n-1，则至少有一条闭迹；，则至少有一条闭迹；(3)如果恰有如果恰有n-1条边，则至少有一个奇度点。条边，则至少有一个奇度点。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 66证明证明：(1)由于由于G连通，所以，存在如下形式的途径：连通，所以，存在如下形式的途径：121nnvvvv 显然该途径至少含有显然该途径至少含有

62、n-1条边。条边。(v1,v2,v n是是G的的n个不同顶点个不同顶点)(2)考虑考虑G中途径：中途径：121:nnWvvvv 若若W是路，则长为是路，则长为n-1;但由于但由于G的边数大于的边数大于n-1,因此，存在因此，存在vi与与vj,它它们相异，但邻接。于是：们相异，但邻接。于是：1iijivvvv 为为G中一闭途径，于是也就存在闭迹。中一闭途径，于是也就存在闭迹。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 67(3)若不然，若不然，G中顶点度数至少为中顶点度数至少为2，于是由握手定理：，于是由握手定理：()2()21vV

63、Gmd vnmnmn 这与这与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中圈。中圈。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

64、1 0.5 0 0.5 1 n 682、连通性性质、连通性性质 定理定理1：若图：若图G不连通，则其补图连通不连通，则其补图连通 证明：对证明：对 ,如果如果u,v属于属于G的同一分支，设的同一分支，设w是与是与u,v处于不同分支中的点，则在处于不同分支中的点，则在G的补图中，的补图中，u与与w,v与与w分别邻接，于是，分别邻接，于是，u与与v在在G的补图中是连通的。的补图中是连通的。,()u vVG 如果如果u与与v在在G的两个不同分支中，则在的两个不同分支中，则在G的补图中必然邻接，因此，的补图中必然邻接，因此，也连通。也连通。所以，若所以，若G不连通，不连通，G的补图是连通的。的补图是连

65、通的。3、偶图的判定定理、偶图的判定定理 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 69定理定理2 一个图是偶图当且当它不包含奇圈一个图是偶图当且当它不包含奇圈。证明：证明：必要性必要性：设：设G是具有二分类（是具有二分类（X,Y）的偶图，并且）的偶图，并且C=v0 v1 vk v0是是G的一个圈的一个圈 不失一般性，可假定不失一般性，可假定 。一般说来，。一般说来，0vX2ivX21ivY。又因为 ，所以，所以 0vXkvY由此即得由此即得C是偶圈是偶圈。充分性充分性：在：在G中任意选取点中任意选取点u,定义定义V的分类如下：

66、的分类如下：X=x|d(u,x)是偶数，是偶数，x V(G)Y=y|d(u,y)是奇数，是奇数，y V(G)下面证明：对下面证明：对X中任意两点中任意两点v与与w,v与与w不邻接！不邻接！0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 70 设设v与与w是是X中任意两个顶点。中任意两个顶点。P是一条最短是一条最短(u,v)路路，而，而Q是一条最是一条最短的短的(u,w)路。路。QPvuwu1 又设又设u1是是P和和Q的最后一个交点。由于的最后一个交点。由于P,Q是最短路，所以，是最短路，所以，P,Q中中u到到u1段长度相同，因此奇偶性相同。又段长度相同，因此奇偶性相同。又P,Q的长均是偶数，所以，的长均是偶数，所以，P,Q中中u1v段和段和u1w段奇偶性相同。段奇偶性相同。如果如果v与与w邻接，则可得到奇圈，矛盾！邻接，则可得到奇圈，矛盾！0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 71作业作业P29P30 13,14,20,22 0.8 1 0.6 0.4 0.