毕业设计（论文）数学归纳法在图论中的应用.doc

目 录1引言12 数学归纳法概论12.1数学归纳法简史12.2 数学归纳法的理论基础归纳与演绎22.3 数学归纳法的适用范围32.4 数学归纳法和发现法32.5 数学归纳法和最小数原理32.6 数学归纳法的类型43图论中的数学归纳法73.1图论的定义73.2图论的分类83.3哈密顿回路9 3.4图论的应用4结束语11参考文献12致谢13数学归纳法在图论中的应用数学系本1102班 指导老师： 摘 要：本文首先介绍了数学归纳法的历史来源，理论基础，适用范围等一些数学归纳法的知识，紧接着又详细的介绍了数学归纳法的种类，比如说我们常说的第一数学归纳法和第二数学归纳法，还有一些我们不熟知的，像反归纳法，跳跃归纳法，双重归纳法等等。他们在图论的证明中都有很大的应用。因此说明数学归纳法在解决图论问题时是一种不错的方法。最后列举了一些图论中用到归纳法的例子，使得文章的论证更具有说服力。关键词：数学归纳法，图论，反归纳法，跳跃归纳法，双重归纳法。 Application of mathematical induction in graph theoryZhangNaDepartment of Mathematics of the 1102 classTutor:Chen JinMeiAbstract：This paper introduces the knowledge of historical sources, rationale, scope and some mathematical induction mathematical induction, followed by another detailed description of the types of mathematical induction, for example, we often say that the first mathematical induction and two mathematical induction, we are not familiar with some, like the anti-induction, induction jumping, dual induction, and so on. They all have great application in graph theory Proof. So explain mathematical induction in solving problems in graph theory is a good way. Finally, cited a number of graph theory used in induction example, the article makes the argument more persuasive.Keywords: mathematical induction, graph theory, anti-induction, induction jumping, double induction.1引言谈到数学归纳法，也许我们每个人对它都不陌生。记得高中学习数列时老师用数学归纳法给我们解决一道道证明题吗？那时我们对这种方法也许并没有太多的认知。但是，今天我们就来深入的研究和探讨下数学归纳法。在数学证明当中我们经常用到的一种方法就是数学归纳法，它经常被用来证明一些与自然数有关的命题。数学归纳法可具体分为一下几种：第一数学归纳法，第二数学归纳法，反向归纳法，跳跃归纳法，双重归纳法等等。大多数人只知道有第一数学归纳法和第二数学归纳法，对其他的方法是闻所未闻。这就使得数学归纳法的历史来源，理论基础和运用技巧等不被人们所熟知。再谈图论，它已经拥有300多年的历史了, 但一直以来解决好图论的相关问题始终是人们关注的焦点。然而伴随着信息技术的发展， 图论又重新回到了人们的视野当中，又便成了人们研究和讨论的热点问题，下面我就来简单的一一介绍一下这些问题。2 数学归纳法概论 2.1数学归纳法简史 归纳思想是这样产生的：我们都知道数学归纳法中有两个非常重要的基础推理归纳推理和演绎推理，它们大概是在公元前六世纪出现的。到了公元前三世纪的时候，著名数学家欧几里德在证明“质数的个数是无穷的 时候指出:如果有个质数, 就必定会有个质数” , 这实际上就渗透了数学归纳法的思想。.但是到了近代，数学归纳法才被真正意义上地应用到数学证明当中。十六世纪时, 意大利非常有名的数学家莫洛里科就证明了“前个奇数的和等于”这一重要结论 。他通过推理得到：第一个平方数加第二个奇数等于第二个平方数, 第二个平方数加第三个奇数等于第三个平方数, 因此，他成为历史上第一位应用数学归纳法的数学家。但他所用的这种证明方法却因风格比较随便而没能让世人得到认可。 到了十七世纪, 法国的数学家帕斯卡又运用数学归纳法证明了二项式系数公式 = 。此举使他成为继莫洛里科之后第二个应用数学归纳法的人.但同样令人遗憾地是，这种方法没有没有延续到现在就消失了。1838年 英国的数学家摩尔根开始提出把这种方法称作“逐次归纳法”，而后又改做了“数学归纳法”。就这样慢慢地数学归纳法就开始得到了人们的认同和重视，并加之以应用。但是直到十九世纪末，意大利的皮亚诺得出了自然数公理，并和当时已存在的归纳公理联系起来，这一举使得数学归纳法数学界里得到普遍地认可,之后便被广泛地应用到了数学各种命题的证明之中.。2.2 数学归纳法的理论基础归纳与演绎考虑问题，有两种不同的推理方式，一种是归纳法，一种是演绎法。我国著名翻译家严复曾将这两个词分别译为“内籀”和“外籀”，并对其进行了解释。 简单地说，归纳就是由特殊的例子归结出一般的结论；而演绎就是将一般的结论应用于特殊的例子中。归纳法可以产生新的结果。物理学，化学，生物学等学科往往通过实验，采用归纳法得出结论。但由于归纳法是以特殊的，有限多的事实为基础，得出的结论有可能并不全面。演绎法当然是可靠的（除非所依据的一般结论本身不正确），所以在数学中经常使用，但缺点是不能发现更一般的结果,所以归纳与演绎应当结合起来使用。数学归纳法实际上就是归纳与演绎的无缝结合，也称做完全归纳法，简称为归纳法。但它与上面所说的归纳法（也称作不完全归纳法）是有区别的。因为数学归纳法不仅有归纳，而且有演绎。运用它而得到的结论是千真万确的真理。一般来说，凡是遇到与自然有关的一些命题，就应当联想到数学归纳法。这是因为自然数是意大利数学家佩亚诺提出的佩亚诺公理数。佩亚诺公理一共有五条，其中最后一条被称为归纳公理，叙述如下：设S是自然数集N的一个子集，满足条件：；如果,那么。那么一定就是.或者换一种说法，也就是通常说的数学归纳法：设是关于自然数的命题。如果成立；对一切,由成立可以推出成立。那么对于，都成立。因此数学归纳法分为两个部分：通过实例，归纳出一个命题(或者是给出需要证明的命题),先验证成立（或对若干个特别的值成立）。这一步称为“奠基”。假设成立，然后利用演绎的方法来证明命题成立。其中假设成立的,称为归纳假设，它往往是推出的重要依据。在不致混淆时，,也常常写成,或,。2.3 数学归纳法的适用范围数学归纳法的作用是证明与自然数相关的数学命题, 但并不是说每一与自然数 相关的数学命题就必须采用数学归纳法来求证(例如“”，且并不是任意一个与自然数 相关的命题都可以用数学归纳法证明(如“时,无正整数解”这种题)2.4 数学归纳法和发现法数学归纳法是一种证明命题的方法，而发现法却是一种探求命题的方法。两者的运用范围是不同的。但是运用联想在证明一些问题的时候，如果考虑到它的来龙去脉， 就显得十分自然了。这便让数学归纳法和发现法在形式上有了某种联系。一般来讲， 探求或是发现定理都会有这样一个过程:对现象进行观察并整理观察得到的结果； 尝试运用归纳推理的方法进行大胆猜想；应用已有的公理和定理进行系统地证明猜想。综上，将以上三个步骤概括为“观察猜想论证在数学中，发现法始于观察和归纳推理, 终于用数学归纳法证明。所以得出“观察+归纳推理+数学归纳法=发现法”。2.5 数学归纳法和最小数原理 归纳原理与最小数原理是等价的。最小数原理:自然数集的任一非空子集必有最小元素。从最小数原理可以推出归纳原理：设满足归纳原理中的(1),(2).如果，那么不是空集。由最小数原理，有一个最小元素.由（1）,.由于的最小性，即它们在中。但由（2）,导出，与矛盾，所以。反过来，从归纳原理可以推出最小数原理：设为的非空子集。如果，那么1就是中的最小元素。如果1，那么含有1，即命题“”对成立。如果对每个，都有，那么由归纳原理，。与非空矛盾。因此必有某个，而在这个数中，第一个属于的就是中的最小数。从上面的推导可以看出，最小数原理常用在反证法中。2.6 数学归纳法的类型第一数学归纳法 第一步先证明当取第一个数( 例如)时看结论正确性第二步, 再假设取( ；且)时结论也正确,最后去证明时结论也是正确的。完成以上步骤之后, 就可以认为命题对于从开始的所有自然数都适用。例1 对任意图,有 。(其中为中顶点的最大度, 为色数, 即使图为着色的的最小值。证明: 对顶点归纳证明,显然,当时,命题成立。假设命题对顶点个数-1时成立。设是的任一顶点, 由归纳法假设,，其中为主子图中顶点的最大度。显然, , 故有。用+1种颜色对着色。设与邻接的顶点是 ,用表示顶点, 所着的颜色。因为,故从+1种颜色中必然可以找到一种颜色( , =1, 2, , )，对着颜色。于是命题得证。第二数学归纳法第二数学归纳法它的原理是关于设一个与自然数相关的命题，若： 当时，命题成立； 假设当时命题成立，则当 时，命题也成立。那么，就说该命题对所有的自然数都是成立的。例 若是树，则（其中：为图的边数，为图的顶点数）.证: 对用归纳法。当时，且。假设定理对少于个顶点的所有树均成立，并设是有个顶点的树。设，因为是中唯一的路，所以不包含路。从而 不连通且的分支和是无圈且连通的，因此是树。并且和的顶点数均小于。所以由归纳假设，.对成立；从而.反归纳法若一个与自然数有关的命，如果命题对无穷多个自然数成立；假设命题对正确，就能推出命题对正确。则命题对所有自然数均正确。例 若阶图是一棵完全二叉树，则是有条边的连通图。证对顶点进行归纳，当或时，命题显然成立的。假设对顶点命题也成立，那么对个顶点的图分两种情况讨论：如果在阶图中移去不是一个叶端点（其度为）那么就变成，的三个分支的分离图。设的顶点数和边数分别为的顶点数边数分别为。那么的顶点数为，由归纳得知当 ，有，因为，所以，要使得和是连通的， 则和必须有一边相连。当和相连时变成图，这时含有个顶点，边为，而， 所以 。即图是个顶点，它的边为。如果在阶图移去是一个叶端点（其度为），那么就变成'两个分支的分离图。设为含有个顶点的图，其边数为，那么就是只含有个顶点的图，所以。跳跃归纳法若一个命题对自然数都是正确的，如果有假设命题对自然数正确，就能推出命题对自然数正确，则命题对一切自然数都正确。定理 对整数 其中是数）。证 ：对进行归纳。因为和所以当时定理成立。设和是正整数，并且假设定理对于所有适合的正整数和都成立。则由定理：对于任意两个整数 和 ，有和归纳法假设，有 于是，定理对所有的正整数和都成立。双重归纳法若命题与两个独立的自然数与有关， 若命题对 与是正确的； 若从命题对自然数对就能推出命题对自然数对 正确与自然数对也正确，那么命题 对一切自然数对都正确。3图论中的数学归纳法3.1图论的定义一些点之间用边（线）相连，便成为图。图论也是归纳法可以大显身手的地方。例 个点（），有些点之间连了线。证明：当线的条数时，一定会出现三角形（即三个点两两连线）；而当线的条数为时，不一定会出现三角形。证明：当时，结论显然。假设命题对于成立。考虑（）个点，其中连线的条数。设其中两点相连。其余个点中，任一点若与都相连，则已经出现三角形。否则，每点至多与中一点相连。则个点之间的连线条。根据归纳假设，必定会出现三角形。另一方面，取个点将与相连（），共线条线，但图中没有出现三角形。3.2图论的分类一个图中，从点引出的边数（以为端点的边数），称为的次数，记为如果从点到点的边是有方向的，那么从点引出的边数，称为的出次，记为；而引向点的边数，称为的入次，记为边有方向的图，称为有向图，否则称为无向图。显然，所有点的次数的和是图中边数的二倍。对于有向图，所有出次的和等于所有入次的和，而且等于图中的边数。即，（表示图中的边数）。例 种昆虫，每两种之中有一种能消灭另一种。证明：能将这种昆虫排成一列，使得每一种昆虫能消灭紧接在它后面的那一种昆虫。证明：可以改为更一般的自然数，用归纳法来证明作一个图，的每一个点表示一种昆虫，如果昆虫可以消灭昆虫，我们就作一条从到的有向边这样得到的图形称为有向完全图如果不考虑方向，它就称为完全图，记作要证明的结论是有向完全图中必有哈密顿链，即可以沿着边（当然要按照这 条边的方向前进）走过每个点恰好一次。当时结论显然。假设命题对成立，个点排列为这时有三种情况：如果有边，那么即为所求如果有边，那么即为所求如果都不成立，那么有边及在中一定有一个使得边与同时存在（我们选取为中第一个使边存在的数）这时即为所求。例 在一个有向图中，已知每点的出次不超过。证明：可将图中的顶点分别染上种颜色中的一种，使得同色的顶点之前无边相连。解：对点数进行归纳。当时，结论显然，假设结论对成立，考虑个点的图。因为而所有所以从而必有一点的入次去掉及以为端点的边对剩下的图用归纳假设，将它的顶点分别染上种颜色中的一种，使得同色的顶点之间无边相连。因为 ，所以可将染成颜色与相连的点（至多个）均不相同。3.3哈密顿回路哈密顿回路是以1856年哈密顿首先提出的所谓环球航行问题而得名。哈密顿回路问题不同于Euler回路问题，它是求对顶点的遍历，在运筹学中有着实际意义。特别是求哈密顿回路中距离最短的问题，是有名的旅行商人命题，它在起初是通过设计这样一个游戏得名的：给定世界上20个城市，用一个代表地球的十二面体的20个顶点分别代表这20个城市。从某一顶点出发，沿着十二面体的棱，经过每个顶点恰好一次，最后回到出发点。谈到哈密顿问题，几乎所有的图论教科书都提到哈密顿这个游戏。 3.4 图论的应用 例 设平面上已给个点，每三点不共线。在这些点之间连条线段。证明：至少能形成个以已知点为顶点的三角形。解：的情况不难验证。假设命题对于成立，考虑的情况。首先由例知，至少能形成一个（以已知点为顶点的）三角形。设为以已知点为顶点的三角形。由向其他点（不包括的顶点）引出（）条线段。如果那么这条线段比其他点的个数多出而每多一条线段至少能形成一个三角形，其中两个顶点在中，一个是其他顶点。因而三角形的个数。如果那么中至少有一个（因为不防设去掉（及由它们引出的线段）后，剩下个点，而线段不少于条。因此，根据归纳假设，至少能形成个三角形，连同在内至少个。于是，命题对一切均成立。 4结束语数学归纳法是一种常用的不可缺少的推理论证方法,没有它, 在图论中很多与自然数有关的命题难以证明; 同时对于与自然数有关的命题, 把n所取的无穷多个值一一加以验证是不可能的, 用不完全归纳法验证其中一部分又很不可靠, 数学归纳法则是一种用有限步骤证明与自然数有关的命题的可靠方法, 其思维方式对于开发学生的智力有重要价值。在图论学习中, 掌握并应用好这一方法有十分重要的意义。 参考文献1 韩景志.漫谈数学归纳法J.数学通报,1997(7):6-8. 2 王天成.数学归纳法的逻辑原理及其在图论中的应用J.青海师范大学师 范学院学报,2008,19(1):66-67.3 方冬云.数学归纳法在图论中的应用J.莆田学院学报,2009(02):40-42.4 余航.图论应用问题探析J.商场现代化,2008(18):393-394.5 华罗庚.数学归纳法M.上海:上海教育出版社,1963.11:23-25.6 冯跃峰.归纳奠基浅析J.安徽:中学数学教学.1988,4:12-13.7 卢开澄,卢华明.图论及其应用M.北京: 清华大学出版社.1995.8 刘世泽.反证法的逻辑依据J.高等函授学报.1997-4.9 JA邦迪,USR默蒂.图论及其应用M.吴望明，译.北京：科学出版社1984.10 王淑栋,庞善臣.系列平行图的边色数J.山东科技大学致谢时光荏苒，岁月如梭，短暂而有意义的四年大学生活即将结束。此时看着毕业论文摆在面前，我感慨万千。它不仅承载了我四年来的学习收获，更让我学会了如何求学、如何进行科学研究甚至如何做人。回想起四年的学习生活，有太多的人给予了我帮助与鼓励，教导与交流。在此我将对我的恩师们，还有所有的同学们表示我的谢意！首先，衷心感谢我的恩师对我的悉心教诲和指导！在跟随陈金梅老师的这段时间里，我不仅跟陈老师学到了许多专业知识，同时也学习到了他严谨求实、一丝不苟的治学态度和踏踏实实、孜孜不倦的工作精神，它将使我受益终生。在此我对陈老师的教育和培养表示衷心的感谢！同时我还还要感谢学校领导和数学系的师生对我日常生活的关心和帮助，思想上的激励和启发，以及为我提供了良好的学习环境。谢谢你们！ 最后，我要感谢我的家人在这些年来给予我的大力支持，尤其要感谢我的妈妈，正是她为我仔细检查该文，才使得本文更加流畅、整洁。