[工学]图论第01讲

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

1、图论GraphicTheory阙夏制作自我介绍阙(quē)夏自2001年开始讲授《算法与数据结构》课程2005年开始讲授《图论》课程quexia@hfut.edu.cn课程简介《图论》是计算机科学与技术专业、信息安全专业的选修课程。通过本课程的学习，使学生对图论的历史背景、研究内容、相关技术及其发展有一个较为全面地了解，从而将所学知识和技术运用于实际应用领域奠定基础。课程简介本课程所介绍的内容包括：图论的发展历程和经典问题；图的基本概念；有关树和图的算法；网络流问题；匹配问题、色数问题；图论及其应用第一章图的基本概念第二章树第三章图的算法第六章

2、网络流图问题第七章匹配理论、色数问题及其他参考书籍《图论》王树禾著科学出版社2004《集合论与图论》耿素云著北京大学出版社1998《离散数学引论》王树禾著中国科学技术大学出版社第一章图的基本概念§1引论§2图的概念§3道路和回路§4图的矩阵表示法§5中国邮路问题§6平面图§1引论§1引论－2图论——计算机问题求解的描述工具。实际问题数学模型求解算法（算法）编程实现用大量数据验证抽象求解测试什么是图论？图论是离散数学的分支：图(graph)：是一个离散集和某些两元素子集的集合。数学形象是：纸上画几个顶点，把其中一些点用曲线段或直线连起来。图显示的

3、是点与点之间的二元关系。什么是图论？－2图论的分支很多，例如：图论算法图论极值图论网络图论模糊图论代数图论随机图论超图论§1引论为什么要学习图论？可以采用图论的成果和方法；最重要的是：可以培养我们思考问题和解决问题的能力。什么是图论？－1图论诞生和孕育于民间游戏。创生：1736年瑞士数学家欧拉——图论之父；进展：1847年，基尔霍夫(Kirchhoff)运用图论解决了电路理论中求解联立方程的问题，引进了“树”概念；1857年，Cayley在有机化学领域发现了一种重要的图，称为“树”，解决了计算饱和氢化物同分异构体的数目；1930年，波兰数学家库

4、拉托父斯基(Kuratowski)证明了平面图可以画在平面上；什么是图论？－1里程碑：1936年，匈牙利数学家寇尼希(D.Konig)发表名著《有限图和无限图理论》，使得图论成为一门独立的数学学科；蓬勃发展：1946年，随着世界上第一台计算机的问世，使图论的发展突飞猛进。其后，图论在现代数学、计算机科学、工程技术、优化管理等领域有大用而得以大力发展。一、Konisberg七桥问题(Euler问题)柯尼斯堡七桥问题是图论中的著名问题。这个问题是基于一个现实生活中的事例：位于当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)有一条河，河中心有两个小岛。小

5、岛与河的两岸有七条桥连接。如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点？一、Konisberg七桥问题(Euler问题)－1如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?一、Konisberg七桥问题(Euler问题)－2不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。莱昂哈德·欧拉(LeonhardEuler)在1736年圆满地解决了这一问题，证明这种方法并不存在。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的问题抽象简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样

6、若从某点出发后最后再回到这点，则这一点的线数必须是偶数。一、Konisberg七桥问题(Euler问题)－3ACBD如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?求从图中任一点出发，通过每条边一次，最后回到起点。ACBD桥所连接的地区视为点每一座桥视为一条线一、Konisberg七桥问题(Euler问题)－4如果通奇数座桥的地方不止两个，那麽满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中一地出发可找到经过所有桥的路线。若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现。>>二、哈密顿回路问题到货郎问题185

7、6年，哈密顿（Hamilton）提出了所谓环球旅行问题：在正12面体上的20个顶点分别表示20个城市，两点间的连线表示城市间的道路。要求旅行者从某个城市出发，到达各个城市一次且仅一次，最后返回出发城市。注意！！不是所有图都能找到这样的路线！三、哈密顿回路问题到货郎问题两个问题：（1）经过每个顶点一次且仅一次；（2）代价最小的Hamilton回路。(目前无有效的方法求解)货郎问题（TravelingSalesmanProblem）一个货郎到各村去卖货，要求每个村子至少去一次，最后返回出发点，为其设计一种销售路线，使总耗时最短。求解方法：把路线全排

8、列，求其中最小的。这类问题称为NPC问题。哈密顿回路和七桥问题的区别Hamilton回路：侧重顶点（一次行遍顶）；七桥问题：侧重边（一次行遍桥/边）。