图论第01讲.ppt

图论Graphic Theory 自我介绍 阙(quē)夏 自2001年开始讲授《算法与数据结构》课程 2005年开始讲授《图论》课程 quexia@hfut.edu.cn 课程简介 《图论》是计算机科学与技术专业、信息安全专业的选修课程。 通过本课程的学习，使学生对图论的历史背景、研究内容、相关技术及其发展有一个较为全面地了解，从而将所学知识和技术运用于实际应用领域奠定基础。 课程简介 本课程所介绍的内容包括： 图论的发展历程和经典问题； 图的基本概念； 有关树和图的算法； 网络流问题； 匹配问题、色数问题； 图论及其应用 第一章 图的基本概念 第二章 树 第三章 图的算法 第六章 网络流图问题 第七章 匹配理论、色数问题及其他 参考书籍 《图论》 王树禾著 科学出版社 2004 《集合论与图论》 耿素云著 北京大学出版社 1998 《离散数学引论》 王树禾著 中国科学技术大学出版社 第一章 图的基本概念 §1 引论 §2 图的概念 §3 道路和回路 §4 图的矩阵表示法 §5 中国邮路问题 §6 平面图 §1 引论 §1 引论－2 图论——计算机问题求解的描述工具。 什么是图论？ 图论是离散数学的分支： 图(graph)： 是一个离散集和某些两元素子集的集合。 数学形象是：纸上画几个顶点，把其中一些点用曲线段或直线连起来。图显示的是点与点之间的二元关系。 什么是图论？－2 图论的分支很多，例如： 图论 算法图论 极值图论 网络图论 模糊图论 代数图论 随机图论 超图论 §1 引论 为什么要学习图论？ 可以采用图论的成果和方法； 最重要的是： 可以培养我们思考问题和解决问题的能力。 什么是图论？－1 图论诞生和孕育于民间游戏。 创生：1736年 瑞士数学家欧拉——图论之父； 进展：1847年，基尔霍夫(Kirchhoff)运用图论解决了电路理论中求解联立方程的问题，引进了“树”概念； 1857年，Cayley在有机化学领域发现了一种重要的图，称为“树”，解决了计算饱和氢化物同分异构体的数目； 1930年，波兰数学家库拉托父斯基(Kuratowski)证明了平面图可以画在平面上； 什么是图论？－1 里程碑：1936年，匈牙利数学家寇尼希(D.Konig)发表名著《有限图和无限图理论》，使得图论成为一门独立的数学学科； 蓬勃发展：1946年，随着世界上第一台计算机的问世，使图论的发展突飞猛进。 其后，图论在现代数学、计算机科学、工程技术、优化管理等领域有大用而得以大力发展。 一、Konisberg七桥问题(Euler问题) 柯尼斯堡七桥问题是图论中的著名问题。 这个问题是基于一个现实生活中的事例：位于当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)有一条河，河中心有两个小岛。小岛与河的两岸有七条桥连接。如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点？ 一、Konisberg七桥问题(Euler问题)－1 一、Konisberg七桥问题(Euler问题)－2 不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。 莱昂哈德·欧拉(Leonhard Euler)在1736年圆满地解决了这一问题，证明这种方法并不存在。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的问题抽象简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。 一、Konisberg七桥问题(Euler问题)－3 一、Konisberg七桥问题(Euler问题)－4 如果通奇数座桥的地方不止两个，那麽满足要求的路线便不存在了。 如果只有两个地方通奇数座桥，则可从其中一地出发可找到经过所有桥的路线。 若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现。 二、哈密顿回路问题到货郎问题 1856年，哈密顿（Hamilton）提出了所谓环球旅行问题： 在正12面体上的20个顶点分别表示20个城市，两点间的连线表示城市间的道路。要求旅行者从某个城市出发，到达各个城市一次且