图论qc.pptVIP

华中农业大学理学院 参考书 集合论与图论》，离散数学二分册，耿素云，北大出版社，1998年2月 图论，王树禾，科学出版社，2004年1月 现代图论（影印版），[绝版]，Modern Graph Theory ，Springer-Verlag，Bela Bollobas，中国科学院研究生教学丛书，科学出版社，2001年1月 一　图论的发展 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。 图论最早起源于一些数字游戏的难题研究，图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。 图论发展的三个阶段 图论产生和发展历经了二百多年的历史,大体上可以划分为三个阶段。 第一阶段是从1736年到十九世纪中叶。 这时的图论处于萌芽阶段,多数问题是围绕着游戏产生的,最具有代表性的工作是著名的瑞士数学家L.Euler于1736年的Konigsberg柯尼斯堡七桥问题。他的那篇论文被公认为图论历史上第一篇论文:“依据几何位置的解题方法”。标志着图论的诞生 图论发展的三个阶段 第二阶段从十九世纪中叶到1936年。这个时期中图论问题大量出现,如四色问题 1852年 和Hamilton哈密尔顿问题 1856年 。同时出现了以图为工具去解决其它领域中一些问题的成果。最有代表性的工作是Kirchhoff 1847年 和Cayley 1857年 分别用树的概念去研究电网络方程组问题和有机化学的分子结构问题。“图 Graph ”这个词第一次出现是在1878年的英国《自然》杂志中。进入本世纪三十年代,出现了一大批精彩的新理论和结果。 图论发展的三个阶段 1936 年以后是第三阶段。由于生产管理、军事、交通运输、计算机和通讯网络等方面的需要提出一系列问题, 特别是许多离散性问题的出现大大促进了图论的发展。进入七十年代以后, 特别是大型电子计算机的出现, 使大规模问题的求解成为可能,图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都得到“爆炸性发展。”图论越来越受到全世界数学界和其它科学界的广泛重视。各种国际学术交流活动十分活跃。大型国际会议频频召开,国际《图论杂志》也于1977 年创刊. 由于图论的重要性,越来越多的高等院校已把它列为数学、计算机科学、电子学和科学管理等专业本科生的必修课和选修课。以考察高校本科生的数学基础和综合应用能力为主的美国大学生数学建模竞赛,从1985年开赛以来已超过二十二个竞赛题中,有1/4的问题须借助于图论这个数学工具才能解决。 高等院校理工科非数学专业所学的数学课程,如《高等数学》、《线性代数》所授内容基本上都二十世纪以前的数学内容, 对现代数学和现代数学方法基本上没有涉及。在这个迈向新世纪的年代, 我们面临加快现代化建设, 深化教学改革的任务。教学领域迫切需要加强课程建设, 引进当代科技发展的新成果, 更新和优化教学内容, 培养跨世纪的人才。《图论》课程的开设正是为着这个目的, 它对拓宽学生的知识面, 优化学生的知识和能力结构很有必要。 图论的特点 图论极有趣味性, 严格来讲它是组合数学的一个重要分支。虽然图论只是研究点和线的学问,但其应用领域十分广阔,不局限于数学和计算机学科, 还涵盖了社会学、交通管理、电信领域等等。图论这门学科具有以下特点: ① 图论蕴含了丰富的思想、漂亮的图形和巧妙的证明; ② 涉及的问题多且广泛, 问题外表简单朴素,本质上却十分复杂深刻; ③ 解决问题的方法千变万化, 非常灵活, 常常是一种问题一种解法。 由以上三个特点可以看出,图论与其它的数学分支不同,它不像群论、拓扑等学科那样有一套完整的理论体系和解决问题的系统方法。而且图论所研究的内容非常广泛,例如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等等 二　图论方法 相关术语 通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路； 通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路； 具有欧拉回路的图称为欧拉图； 具有欧拉通路但无欧拉回路的图称为半欧拉图。 相关术语 判别方法： 1 无向连通图是欧拉图当且仅当其所有顶点的度数都是偶数； 2 无向连通图是半欧拉图当且仅当其奇点数为2； Fleur