教学讲稿图论课件

《教学讲稿图论课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用GraphTheoryandItsApplications主要内容图论前言数学预备知识前言课程目标学时和学分教学大纲教材和主要参考资料课程考核图论学科简介（1）图论是研究点与线组成的“图形”问题的一门科学。图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支属于应用数学分支哥尼斯堡七桥问题欧拉（1707~1782）：根据几何位置的解题方法，这是图论领域的第一篇论文，1736年，被尊称为图论和拓扑之父七桥问题近代图论的历史可追溯到18世纪的七桥问题:穿过Königsberg城的七座桥，要求每座桥通过一次且仅

2、通过一次。Euler1736年证明了不可能存在这样的路线。四色问题在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题“四色猜想”：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。四色问题1852年，刚从伦敦大学毕业的FrancisGuthrie提出了四色猜想。1878年著名的英国数学家Cayley向数学界征求解答。此后数学家Heawood花费了毕生的精力致力于四色研究，于1890年证明了五色定理（每个平面图都是5顶点可着色的）。直到1976年6月，美国数学家K.Appel与W.Haken，在3台不同

3、的电子计算机上，用了1200小时，才终于完成了“四色猜想”的证明，从而使"四色猜想"成为了四色定理。图论学科简介（2）19世纪末期，图论应用于电网络方程组和有机化学中的分子结构20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信等领域中的离散性问题物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等领域应用课程目标通过本课程学习，要求学生掌握图论的基本理论及推理方法，为通信网络、计算机、信息工程、密码学、运筹学、管理科学等等学科进一步学习和研究打下理论基础。掌握图论的基本理论与基本方法，并

4、用这些理论与方法解决一些实际问题，了解图论在现代信息科学、现代通信系统、计算机科学、管理与工程等中的应用。本课程特别强调理论与工程实践相结合，以提高学生的学习知识、运用知识能力。学时和学分学时数54学分数3教学大纲（共11章）通过教学，使学生掌握该课程的基本理论与方法，培养对离散对象的抽象思维与解决实际问题的能力，并为学习相关课程及将来从事科学研究创新和工程实践奠定理论基础，及培养学生理论与实践相结合的能力。第一章图的基本概念图和简单图同构子图顶点的度路和连通性圈最短路问题第二章树树割边和键割点连线问题第三章连通度连通度块可靠通信网建设问题第四章Euler环

5、游和Hamilton圈Euler环游Hamilton圈旅行售货员问题第五章匹配匹配偶图的匹配和覆盖完美匹配人员分派问题最优匹配问题第六章着色问题边色数Vizing定理点着色色数Brooks定理围长和色数第七章平面图平图和平面图对偶图Euler公式Kuratowski定理五色定理和四色猜想平面性算法第八章有向图有向图有向路有向圈第九章网络流割最大流最小割定理Menger定理第十章NP–完全问题优化问题P类和NP类Cook定理六个基本NPC问题第十一章图论的应用图论在现代网络设计和流量分析中的应用图论在信息安全中的应用图论在信号处理中的应用教材和主要参考资料（1

6、）《图论及其应用》，孙惠泉，科学出版社，2004年9月。《图论导引》，DouglasB.West著，李建中、骆吉洲译，机械工业出版社，2006年2月。《图论及其应用习题解答》，张克民、林国宁、张忠辅编，清华大学出版社，1988年4月。教材和主要参考资料（2）《图论及其应用》，J.A.邦迪及U.S.R默蒂，科学出版社。（原书：GraphTheorywithApplications,J.A.Bondy&U.S.R.Murty)有最新扩容版，2008年Springer出版的GTM丛书,GTM244GraphTheory.GraphTheory,ReinhardDi

7、estel，第四版,Springer，有中文版，李学良等译.学习方法目的明确态度端正理论和实践相结合充分利用资源逐步实现从知识到能力到素质的深化和升华课程考核平时成绩（30%-40%）闭卷考试（60%-70%）27图论模型为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。(1)化学中的图论模型19世纪，化学家凯莱用图论研究简单烃——即碳氢化合物用点抽象分子式中的碳原子和氢原子，用边抽象原子间的化学键。28通过这样的建模，能很好研究简单烃的同分异构现象.例如：C4H10的两种同分异构结构图模型为：hhh

8、hhhhhhhhhhhhhhhhh29(2)商业中的