图论——一个迷人的世界_亚瑟.本杰明_9787111551195

本书介绍了图论的基本概念，解释了图论中各种经典问题。例如，熄灯的问题、小生成树问题、哥尼斯堡七桥问题、中国邮递员问题、国际象棋中马的遍历问题和路的着色问题等等。书中也给出了各种类型的图，例如，二部图、欧拉图、彼得森图和树；等等。每一章都为读者设置了练习题，包含了具有挑战性的探索性问题。

原书前言我们常常认为数学理应享有较高的声誉，但事实并非如此。数学中的很多领域都让人感觉枯燥，需要花费大量的精力去学习和理解。近年来，有许多学术文章对美国高中生和其他国家的学生在数学和科学方面加以比较，得出了获得数学专业研究生学位的学生越来越少的报告。无论什么原因，事实是没有足够多的有天赋的美国学生对学习数学感到很开心。许多美国学生都在错失学习数学的机会。事实上，有许多数学分支是很有意思的。在这些领域内的许多有趣的定理背后都包含着一段这个定理由来的历史，一个关于那些甘于奉献的数学家们如何发现这些有趣和重要定理的故事。这些定理不一定是被专门钻研这个方向的人们发现，还有许多时候是意外收获。这些定理的证明对数学及其他领域是十分有用的，本书十分荣幸能给您介绍这样一个数学领域，欢迎来到图论的迷人世界。像其他专业领域一样，数学由许多方向组成，它们之间有共性，但也有自己特有的鲜明特征。有些方向可能你很熟悉，比如代数、几何、三角函数和微积分，学习和理解这些学科可能会需要你努力研习，当然这些领域也很有趣。事实上，学习任何学科都很有趣。但是，这些有趣的数学领域从哪里来呢？答案是它来自于人们本身，来自于他们的好奇心、他们的想象力、他们的聪明才智。虽然有些人是数学家，但也有些人不是，其中有些就是学生就像你我，或者当年的你我。我们的目的是在这里向您介绍一个也许比较陌生的图论领域。我们希望向您展示数学的乐趣所在。我们相信您能感觉到数学不仅有趣而且还会为之激动。我们不仅要介绍这些有趣的结果，同样期待能和您分享发现和解决这些问题的方法。在这里我们可以看到，一个有趣的问题往往不是用数学方法解决完就完成了任务，而是经常会引出一整套数学理论。尽管本书不打算深入钻研一些太高深的数学问题，但是我们会给出其中的一些思想或者思路来说明其正确性。第一章以一些好玩的问题作为引子，这些问题给出了这本以图论为主题的数学书中的主要概念。其中的一些问题具有历史性意义，当我们拥有足够多的信息来解决它们时，我们会重新拾起它们。这一部分初步探讨了图论中的一些基本数学概念。在这一章的最后，我们给出了一个通常被称为图论第一定理的定理，用来处理一个所有顶点都赋予了度数的图的问题。第二章从一场数学领域中的定理选美大赛来展开。我们看到，在最美丽的数学定理列表中不仅出现了关于图论的定理，而且一个在图论方面地位尤其特殊的数学家出现了。其中的一个定理引导我们步入图论中研究较多的一类图，即正则图。从这时开始，图的顶点的度数和长度都将加以讨论。本章的其余部分是关于图的结构的一些概念和思想。这章以图论中一个尚未解决的问题结束。第三章讨论了一个图所具备的最基本性质，在任何两个地点之间都可以互相旅行。这产生了图中的各点之间的距离问题，这个位置对应于所给定的位置是近还是远。这章还有一个幽默的概念，即厄多斯数，这个概念是在描述与厄多斯合作过的数学家以及与与厄多斯合作过的数学家合作过的数学家以及……第四章介绍了一个连通图拥有的最简单的结构，引导我们认识树形图因为它们看起来像树。这类图可以和化学联系在一起，也能够帮助我们解决一些需要做一系列决断的决策问题。本章最后讨论了一个实际问题，就是设计一个成本最低的公路系统，使我们在系统中任何两个位置之间可以旅行。图论有一个相当奇特的历史。这一领域的大部分知识开始于18世纪，那是天才的数学家莱昂哈德·欧拉提出和解决哥尼斯堡七桥问题，接着又描述了一个值得思考的更复杂的问题的时代。这产生了一类图形，我们以欧拉为之命名，并在第五章研究它，这一章还提起了另一个众所周知的问题中国邮递员问题，这是一个关于邮递员进行一次环形巡游的最短路程问题。第六章讨论了以19世纪一个著名的物理学家和数学家命名的图的问题，这个人是威廉·罗恩·哈密尔顿爵士。虽然哈密尔顿很少处理图论问题，但是他提出了十二面体代数系统，这促使他发明了一个在十二面体中寻找环形路径的游戏，且每个顶点恰好经过一次。20世纪中期的知识大爆炸也包含了这方面的内容。这章以一个重要的实际问题结束，即找到一个最短的或者最省钱的环形路径使其经过这个系统中的每个地方。有一个问题是关于一些对象的集合是否足够用以与另一个对象的集合匹配例如申请工作匹配或人与人之间的匹配。这种问题会在第七章中讨论。在19世纪末第一次提出将图论作为数学的一个理论领域，并且确立了图这个词，也就是我们这本书所讨论的主要内容，从这章中我们可以了解到一个赛制安排有多少种不同的方案。第八章关注的问题是一个图能否被分为其他特定类型的图，主要是圈。一些具体的完全图是否能以某种方式被分为三角形圈，这种情况对应了19世纪中期数学家托马斯·柯克曼提出并解决的通常被冠以柯克曼女生问题之后的问题。还介绍了图分解问题和图的顶点被整数适当标记并生成边的标记问题之间的联系。本章的最后以一个名为四色方柱的趣味游戏以及基于图论知识的解决方案收尾。通常会有这样的情况发生，游历中涉及单行道，为了在图中将它模型化，在边上标明方向是有必要的。这产生了定向图的概念，这样的结构也可以用于表示比赛中一支队伍战胜另一支队伍。对于这类数学问题会出现在第九章。这章还有一个大讨论，即各种各样的投票技术可以产生意想不到的结果。一些有趣的问题可以看作一个图是否可以在平面上没有交叉边地被画出。在第十章中借助可平面图的概念可以处理这类问题，其中讨论了一个砖厂问题，源自于第二次世界大战时的一个集中营。数学中最著名的问题之一就是任何一个地图的区域能否用四种颜色区分，使得有相邻边界的两个区域颜色不同？这个四色问题是在19世纪中期一个年轻的英国数学家提出的，当时三等分角和化圆为方的问题已经在社会上众所周知，而四色问题又悄悄地传播开来，问题出名不仅是因为解决这个问题的时间跨度长，还因为它的解决方法，在第十一章中我们会对其进行讨论。这引出了给一个图的顶点着色，并且怎样用其解决一系列问题的讨论，例如，从日程安排到交通指示灯阶段变化的问题。有趣的不仅仅是给一个图的顶点着色，无论是从实践的观点，还是理论的观点，给它的边着色都是值得关注的。这就是第十二章的主题。这也可以帮助我们解决一类日程安排问题，这也引出了图论中我们称之为拉姆齐数的一系列数值。这章还包括一个有趣的问题，叫作道路着色问题，它告诉我们在某些特定的仅包含单行道的交通系统中，每个地方都有相同数目的道路出口，那么道路可以被着色使得给出的一系列方向就必然能到达指定地点。而这本书的最主要的目的是为了说明数学的一个分支可以如此有趣（有时还很神秘），这本书也可以用作习题集。本书最后有包括书中的所有章节的练习题。最后，我很高兴能够得到非常专业的普林斯顿大学出版社员工的好评，尤其是维基·科恩（Vickie Kearn）、萨拉·勒纳（Sara Lerner）、艾莉森·纽齐斯（Alison Anuzis）、奎因·法斯汀（Quinn Fusting），还有我们最初原稿的匿名审稿人，他们的评论、反馈以及对细节的关注对这本书的改进十分有帮助。在此表示我们诚挚的感谢。

你还可能感兴趣

我要评论