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

目 录 1引言 1 2 数学归纳法概论 1 2.1数学归纳法简史 1 2.2 数学归纳法的理论基础—归纳与演绎 2 2.3 数学归纳法的适用范围 3 2.4 数学归纳法和发现法 3 2.5 数学归纳法和最小数原理 3 2.6 数学归纳法的类型 4 3图论中的数学归纳法 7 3.1图论的定义 7 3.2图论的分类 8 3.3哈密顿回路 9 3.4图论的应用 4结束语 11 参考文献 12 致谢 13 数学归纳法在图论中的应用 数学系本1102班 指导老师： 摘 要：本文首先介绍了数学归纳法的历史来源，理论基础，适用范围等一些数学归纳法的知识，紧接着又详细的介绍了数学归纳法的种类，比如说我们常说的第一数学归纳法和第二数学归纳法，还有一些我们不熟知的，像反归纳法，跳跃归纳法，双重归纳法等等。他们在图论的证明中都有很大的应用。因此说明数学归纳法在解决图论问题时是一种不错的方法。最后列举了一些图论中用到归纳法的例子，使得文章的论证更具有说服力。 关键词：数学归纳法，图论，反归纳法，跳跃归纳法，双重归纳法。 Application of mathematical induction in graph theory ZhangNa Department of Mathematics of the 1102 class Tutor:Chen JinMei Abstract：’ 时候指出:如果有个质数, 就必定会有个质数” , 这实际上就渗透了数学归纳法的思想。.但是到了近代，数学归纳法才被真正意义上地应用到数学证明当中。 十六世纪时, 意大利非常有名的数学家莫洛里科就证明了“前个奇数的和等于”这一重要结论 。他通过推理得到：第一个平方数加第二个奇数等于第二个平方数, 第二个平方数加第三个奇数等于第三个平方数, …因此，他成为历史上第一位应用数学归纳法的数学家。但他所用的这种证明方法却因风格比较随便而没能让世人得到认可。 到了十七世纪, 法国的数学家帕斯卡又运用数学归纳法证明了二项式系数公式 = 。此举使他成为继莫洛里科之后第二个应用数学归纳法的人.但同样令人遗憾地是，这种方法没有没有延续到现在就消失了。 1838年 英国的数学家摩尔根开始提出把这种方法称作“逐次归纳法”，而后又改做了“数学归纳法”。就这样慢慢地数学归纳法就开始得到了人们的认同和重视，并加之以应用。但是直到十九世纪末，意大利的皮亚诺得出了自然数公理，并和当时已存在的归纳公理联系起来，这一举使得数学归纳法数学界里得到普遍地认可,之后便被广泛地应用到了数学各种命题的证明之中.。 2.2 数学归纳法的理论基础—归纳与演绎 考虑问题，有两种不同的推理方式，一种是归纳法，一种是演绎法。我国著名翻译家严复曾将这两个词分别译为“内籀”和“外籀”，并对其进行了解释。 简单地说，归纳就是由特殊的例子归结出一般的结论；而演绎就是将一般的结论应用于特殊的例子中。归纳法可以产生新的结果。物理学，化学，生物学等学科往往通过实验，采用归纳法得出结论。但由于归纳法是以特殊的，有限多的事实为基础，得出的结论有可能并不全面。演绎法当然是可靠的（除非所依据的一般结论本身不正确），所以在数学中经常使用，但缺点是不能发现更一般的结果,所以归纳与演绎应当结合起来使用。 数学归纳法实际上就是归纳与演绎的无缝结合，也称做完全归纳法，简称为归纳法。但它与上面所说的归纳法（也称作不完全归纳法）是有区别的。因为数学归纳法不仅有归纳，而且有演绎。运用它而得到的结论是千真万确的真理。 一般来说，凡是遇到与自然有关的一些命题，就应当联想到数学归纳法。这是因为自然数是意大利数学家佩亚诺提出的佩亚诺公理数。佩亚诺公理一共有五条，其中最后一条被称为归纳公理，叙述如下： 设S是自然数集N的一个子集，满足条件： ； 如果,那么。 那么一定就是.或者换一种说法，也就是通常说的数学归纳法： 设是关于自然数的命题。如果 成立； 对一切,由成立可以推出成立。 那么对于，都成立。 因此数学归纳法分为两个部分： 通过实例，归纳出一个命题(或者是给出需要证明的命题),先验证成立（或对若干个特别的值成立）。这一步称为“奠基”。 假设成立，然后利用演绎的方法来证明命题成立。其中假设成立的,称为归纳假设，它往往是推出的重要依据。在不致混淆时，,也常常写成,,或,。 2.3 数学归纳法的适用范围 数学归纳法的作用是证明与自然数相关的数学命题, 但并不是说每一与自然数 相关的数学命题就必须采用数学归纳法来求证(例如“”，且并不是任意一个与自然数 相关的命题都可以用数学归纳法证明(如“时,无正整数解”这种题) 2.4 数学归纳法和发现法 数学归纳法是一种证明命题的方法，而发现法却是一种探求命题的方法。两者的运用范围是不同的。