[理学]第七章 图论-1st.pdfVIP

离散数学 大连理工大学软件学院 陈志奎 教授 办公室：综合楼411 ，Tel 实验室：教学楼A318/A323/A320 ，Tel ： 24 Mobile: Email: zkchen@ zkchen00@ 第七章 图论 2 图论（Graph Theory）是数学的一个分支。它以图为研 究对象。图论中的图是由若干给定的点及连接两点的线 所构成的图形，这种图形通常用来描述某些事物之间的 某种特定关系，用点代表事物，用连接两点的线表示相 应两个事物间具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被 好多位数学家各自独立地建立过。关于图论的文字记载 最早出现在欧拉1736年的论着中，他所考虑的原始问题 有很强的实际背景。 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱 格尔河上有七座桥将河中的岛及岛与河岸联结起来，如 下图所示，A、B、C，D表示陆地。 3 问题是要从这四块陆地中任何一块开始，通过 每一座桥正好一次，再回到起点。然而无数次 的尝试都没有成功。欧拉在1736年解决了这个 问题，他用抽象分析法将这个问题化为第一个 图论问题：即把每一块陆地用一个点来代替， 将每一座桥用联接相应的两个点的一条线来代 替，从而相当于得到一个[图]。欧拉证明了这 个问题没有解，并且推广了这个问题，给出了 对於一个给定的图可以某种方式走遍的判定法 则。这项工作使欧拉成为图论 〔及拓扑学〕的 创始人。 4 1859年，英国数学家哈密顿发明了一种游戏：用 一个规则的实心十二面体，它的20个顶点标出 世界著名的20个城市，要求游戏者找一条沿着 各边通过每个顶点刚好一次的闭回路，即「绕 行世界」。用图论的语言来说，游戏的目的是 在十二面体的图中找出一个生成圈。这个问题 后来就叫做哈密顿问题。由於运筹学、计算机 科学和编码理论中的很多问题都可以化为哈密 顿问题，从而引起广泛的注意和研究。 5 在图论的历史中，还有一个最著名的问题——四色猜 想。这个猜想说，在一个平面或球面上的任何地图 能够只用四种颜色来着色，使得没有两个相邻的国 家有相同的颜色。每个国家必须由一个单连通域构 成，而两个国家相邻是指它们有一段公共的边界， 而不仅仅只有一个公共点。四色猜想有一段有趣的 历史。每个地图可以导出一个图，其中国家都是点， 当相应的两个国家相邻时这两个点用一条线来连接。 所以四色猜想是图论中的一个问题。它对图的着色 理论、平面图理论、代数拓扑图论等分支的发展起 到推动作用。 图论的广泛应用，促进了它自身的发展。20世纪 40-60年代，拟阵理论、超图理论、极图理论，以及 代数图论、拓扑图论等都有很大的发展 6 第七章 图论 •在讨论关系时，我们曾经引进过图的一些 概念。在那里，图只是作为表达集合上二 元关系的一种工具。在这一章我们把这些 基本概念加以推广，并且把图看成一个抽 象的数学系统来研究