图论及其应用杨春全.pptx

《图论及其应用杨春全.pptx》由会员分享，可在线阅读，更多相关《图论及其应用杨春全.pptx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单击此处添加标题公司介绍丨品牌宣讲LOGOLOGOBUSINESS ANALYSIS REPORT2图论及其应用 作者:张先迪、李正良 购买地点：教材科第1页/共854页3参考文献1 美，帮迪图论及其应用2 美，Gary Chartrand图论导引，人民邮电出版社，20073 Bela Bollobas，现代图论，科学出版社，2001 中国科学院研究生教学丛书4 美，Fred Buckley图论简明教程，清华大学出版社，2005 李慧霸 王风芹译第2页/共854页45 李尉萱，图论，湖南科学技术出版社，19796 美，Douglas B.West图论导引，机械工业出版社，2007 李建中，骆吉

2、洲译7 杨洪，图论常用算法选编，中国铁道出版社，19888 陈树柏，网络图论及其应用，科学出版社，1982第3页/共854页59 Chris Godsil，Gordon Royle Algebraic Graph Theory，世界图书出版公司北京公司，200410 王朝瑞，图论，高等教育出版社，1983第4页/共854页6第一章 图的基本概念本次课主要内容图的概念与图论模型(一)、图论课程简介(二)、图的定义与图论模型(三)、图的同构第5页/共854页71、研究对象 图论是研究点与线组成的“图形”问题的一门科学。属于应用数学分支.(一)、图论课程简介2、发展历史 图论起源于18世纪的1736

3、年，标志事件是“哥尼斯堡七桥问题.数学家欧拉被称为“图论之父”.20世纪30年代出版第一本图论著作.第6页/共854页83、应用状况 图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。4、教学安排 主要介绍图的一些基本概念、基本理论和图论的典型应用。60学时。第7页/共854页91、图的定义(二)、图的定义与图论模型 一个图是一个序偶，记为G=(V,E),其中：(1)V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；(2)E

4、是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。第8页/共854页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)。v1v2v3v4e1e2e3e4e5e6第9页/共854页11图的相关概念：有限图：顶点集和边集都有限的图称为有限图；平凡图：只有一个顶点的图称为平凡图；空图：边集

5、为空的图称为空图；n阶图：顶点数为n的图称为n阶图；(n,m)图：顶点数为n,边数为m的图称为(n,m)图；边的重数：连接两个相同顶点的边的条数称为边的重数；重数大于1的边称为重边；环：端点重合为一点的边称为环；简单图：无环无重边的图称为简单图；其余的图称为复合图；第10页/共854页12顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为该边的两个端点；顶点u与边e相关联：顶点u是边e的端点；边e1与边e2相邻接：边e1与边e2有公共端点；2、图论模型为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。(1)化学中的图论模型19世纪，化学家凯莱用图论研究简单烃即碳氢化合物第11页/共854页13用点抽象分子式中的碳原子和氢原子，用边抽象原子间的化学键。通过这样的建模，能很好研究简单烃的同分异构现象.例如：C4H10的两种同分异构结构图模型为：hhhhhhhhhhh