图论课件第一章_图的基本概念.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《图论课件第一章_图的基本概念.ppt》由会员分享,可在线阅读,更多相关《图论课件第一章_图的基本概念.ppt(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 图论及其应用图论及其应用应用数学学院应用数学学院1图论及其应用图论及其应用 作者作者:张先迪、李正良张先迪、李正良 购买地点:教材科购买地点:教材科2参考文献参考文献1 美,帮迪图论及其应用美,帮迪图论及其应用2 美美,Gary Chartrand图图论论导导引引,人人民民邮邮电电出版社,出版社,20073 Bela Bollobas,现现代代图图论论,科科学学出出版版社社,2001 中国科学院研究生教学丛书中国科学院研究生教学丛书4 美美,Fred Buckley图图论论简简明明教教程程,清清华华大大学出版社,学出版社,2005 李慧霸李慧霸 王风芹译王风芹译35 李尉萱,图论,湖南科学技
2、术出版社,李尉萱,图论,湖南科学技术出版社,19796 美,美,Douglas B.West图论导引图论导引,机械工业出,机械工业出版社,版社,2007 李建中,骆吉洲译李建中,骆吉洲译7 杨洪,图论常用算法选编,中国铁道出版杨洪,图论常用算法选编,中国铁道出版社,社,19888 陈树柏,网络图论及其应用,科学出版社,陈树柏,网络图论及其应用,科学出版社,198249 Chris Godsil,Gordon Royle Algebraic Graph Theory,世界图书出版公司北京公司,世界图书出版公司北京公司,200410 王朝瑞,图论,高等教育出版社,王朝瑞,图论,高等教育出版社,19
3、835第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容图的概念与图论模型图的概念与图论模型(一一)、图论课程简介、图论课程简介(二二)、图的定义与图论模型、图的定义与图论模型(三三)、图的同构、图的同构(五五)、顶点的度与图的度序列、顶点的度与图的度序列(四四)、完全图、偶图与补图、完全图、偶图与补图61 1、研究对象、研究对象图论是研究点与线组成的图论是研究点与线组成的“图形图形”问题的一问题的一门科学。属于应用数学分支。门科学。属于应用数学分支。(一一)、图论课程简介、图论课程简介2 2、发展历史、发展历史图论起源于图论起源于18世纪的世纪的1736年,标志事件是年,标志
4、事件是“哥尼斯堡七桥问题哥尼斯堡七桥问题数学家欧拉被称为数学家欧拉被称为“图论之父图论之父”20世纪世纪30年代出版第一本图论著作年代出版第一本图论著作73 3、应用状况、应用状况图论的应用已经涵盖了人类学、计算机科学、图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、流体动力学、心理学、社化学、环境保护、流体动力学、心理学、社会学、交通管理、电信以及数学本身等。会学、交通管理、电信以及数学本身等。目前,图论已形成很多分支:如结构图论、目前,图论已形成很多分支:如结构图论、网络图论、代数图论、拓扑图论等网络图论、代数图论、拓扑图论等4 4、教学安排、教学安排主要介绍图的一些基本概念、基本
5、理论和图主要介绍图的一些基本概念、基本理论和图论的典型应用。论的典型应用。60学时。学时。81 1、图的定义、图的定义(二二)、图的定义与图论模型、图的定义与图论模型一个图是一个序偶一个图是一个序偶,记,记为为G=(V,E),其中:其中:(1)V是一个有限的非空集合,称为顶点集合是一个有限的非空集合,称为顶点集合,其其元素称为顶点或点。用元素称为顶点或点。用|V|V|表示顶点数;表示顶点数;(2)E是由是由V中的点组成的无序对构成的集合,称中的点组成的无序对构成的集合,称为边集,其元素称为边,且同一点对在为边集,其元素称为边,且同一点对在E中可以中可以重复出现多次。用重复出现多次。用|E|E|
6、表示边数。表示边数。9图可以用图形表示:图可以用图形表示:V中的元素用平面上一个黑点表示,中的元素用平面上一个黑点表示,E中的元素用一条连接中的元素用一条连接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)。v1v2v3v4e1e
7、2e3e4e5e610图的相关概念:图的相关概念:有限图:顶点集和边集都有限的图称为有限图;有限图:顶点集和边集都有限的图称为有限图;平凡图:只有一个顶点的图称为平凡图;平凡图:只有一个顶点的图称为平凡图;空图:边集为空的图称为空图;空图:边集为空的图称为空图;n阶图:顶点数为阶图:顶点数为n的图称为的图称为n阶图;阶图;(n,m)图:顶点数为图:顶点数为n,边数为边数为m的图称为的图称为(n,m)图;图;边的重数:连接两个相同顶点的边的条数称为边的重数;边的重数:连接两个相同顶点的边的条数称为边的重数;重数大于重数大于1的边称为重边;的边称为重边;环:端点重合为一点的边称为环;环:端点重合为
8、一点的边称为环;简单图:无环无重边的图称为简单图;其余的图称为简单图:无环无重边的图称为简单图;其余的图称为复合图;复合图;11顶点顶点u与与v相邻接:顶点相邻接:顶点u与与v间有边相连接;其中间有边相连接;其中u与与v称为称为该边的两个端点;该边的两个端点;顶点顶点u与边与边e相关联:顶点相关联:顶点u是边是边e的端点;的端点;边边e1与边与边e2相邻接:边相邻接:边e1与边与边e2有公共端点;有公共端点;2 2、图论模型、图论模型为了抽象和简化现实世界,常建立数学模型。图是关系的为了抽象和简化现实世界,常建立数学模型。图是关系的数学表示,为了深刻理解事物之间的联系,图是常用的数学数学表示,
9、为了深刻理解事物之间的联系,图是常用的数学模型。模型。(1)化学中的图论模型化学中的图论模型19世纪,化学家凯莱用图论研究简单烃世纪,化学家凯莱用图论研究简单烃即碳氢化合物即碳氢化合物12用点抽象分子式中的碳原子和氢原子,用边抽象原子间用点抽象分子式中的碳原子和氢原子,用边抽象原子间的化学键。的化学键。通过这样的建模,能很好研究简单烃的同分异构现象通过这样的建模,能很好研究简单烃的同分异构现象例如:例如:C4H10的两种同分异构结构图模型为:的两种同分异构结构图模型为:hhhhhhhhhhhhhhhhhhhh13(2)商业中的图论模型商业中的图论模型商业中,经常用图来对仓库和零售店进行建模商业
10、中,经常用图来对仓库和零售店进行建模例如:令例如:令V=w1,w2,w3,r1,r2,r3,r4,r5代表代表3个仓库和个仓库和5个零售点个零售点E=w1r1,w1r2,w2r2,w2r3,w2r4,w3r3,w3r5代表每个仓库和每个代表每个仓库和每个零售店间的关联。则图模型图形为:零售店间的关联。则图模型图形为:w1r1r2w2r3r4w3r5(3)最短航线问题最短航线问题14用点表示城市,两点连线当且仅当两城市有航线。为了用点表示城市,两点连线当且仅当两城市有航线。为了求出两城市间最短航线,需要在线的旁边注明距离值。求出两城市间最短航线,需要在线的旁边注明距离值。例如:令例如:令V=a,
11、b,c,d,e代表代表5个城市个城市E=a b,ad,b c,be,de代表城市间的直达航线代表城市间的直达航线则航线图的图形为:则航线图的图形为:abcde500320140430370请求出从请求出从d到到c的最短路的最短路15(4)任务分配问题任务分配问题 有一个旅行团要组织一批人去旅游,其中一些人是朋友有一个旅行团要组织一批人去旅游,其中一些人是朋友他们要乘坐公共汽车去,而车上的位子是成对的。因此他们要乘坐公共汽车去,而车上的位子是成对的。因此为了让大家旅途更愉快,旅行团负责人需要将成对的朋为了让大家旅途更愉快,旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。友安排在一起。给
12、出一种安排方案。该问题可以建立一个图论模型来解决:旅行团的人抽象该问题可以建立一个图论模型来解决:旅行团的人抽象为图的顶点,两个顶点连线,当且仅当两个顶点代表的为图的顶点,两个顶点连线,当且仅当两个顶点代表的人是朋友。人是朋友。问题归结于在模型图中求所谓的问题归结于在模型图中求所谓的“匹配匹配”,关于图的匹配,关于图的匹配将在第五章介绍。将在第五章介绍。16(5)考试时间安排问题考试时间安排问题 一个教授需要对期末考试时间进行安排,使得学生们一个教授需要对期末考试时间进行安排,使得学生们不会有相互冲突的考试。如何解决?不会有相互冲突的考试。如何解决?该问题可以建立一个图论模型来解决:待考的课程
13、可该问题可以建立一个图论模型来解决:待考的课程可抽象为图的顶点,连接两个顶点的边表示至少有一个学生抽象为图的顶点,连接两个顶点的边表示至少有一个学生同时选择了这两门课程。同时选择了这两门课程。问题归结于在模型图中求所谓的问题归结于在模型图中求所谓的“顶点着色方案顶点着色方案”问题,问题,该问题将在第七章讨论。该问题将在第七章讨论。例如:有例如:有a,b,c,d,e,f 六门课程。按照上面方法建立六门课程。按照上面方法建立的模型图如下:的模型图如下:17 一种可行的安排方案为:第一时间:一种可行的安排方案为:第一时间:a,d,e;第二时间:第二时间:b,f;最后:;最后:c.abcefd 另一种
14、可行的安排方案为:第一时间:另一种可行的安排方案为:第一时间:a,e;第二时间:第二时间:c,d;最后:;最后:b,f.(6)旅行售货员问题旅行售货员问题 一电脑代理商要从她所在城市出发,乘飞机去六个城市,一电脑代理商要从她所在城市出发,乘飞机去六个城市,然后回到出发点,如果要求每个城市只经历一次,能否办然后回到出发点,如果要求每个城市只经历一次,能否办到?给出行走方案。到?给出行走方案。18 问题归结为在模型图中寻求所谓的问题归结为在模型图中寻求所谓的“哈密尔顿圈哈密尔顿圈”问题。问题。将在第四章介绍。将在第四章介绍。例如:如果模型图如下:例如:如果模型图如下:该问题可以建立一个图论模型来解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课件 第一章 基本概念
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内