数学归纳法在图论中的应用

《数学归纳法在图论中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1引言12数学归纳法概论12.1数学归纳法简史12.2数学归纳法的理论基础—归纳与演绎22.3数学归纳法的适用范围32.4数学归纳法和发现法32.5数学归纳法和最小数原理32.6数学归纳法的类型43图论中的数学归纳法73.1图论的定义73.2图论的分类83.3哈密顿回路93.4图论的应用4结束语11参考文献12致谢13ii数学归纳法在图论中的应用数学系本1102班指导老师：摘要：本文首先介绍了数学归纳法的历史来源，理论基础，适用范围等一些数学归纳法的知识，紧接着又详细的介绍了数学归纳法的种类，比如说我们常说的第一数学归纳法和第二数学

2、归纳法，还有一些我们不熟知的，像反归纳法，跳跃归纳法，双重归纳法等等。他们在图论的证明中都有很大的应用。因此说明数学归纳法在解决图论问题时是一种不错的方法。最后列举了一些图论中用到归纳法的例子，使得文章的论证更具有说服力。关键词：数学归纳法，图论，反归纳法，跳跃归纳法，双重归纳法。ApplicationofmathematicalinductioningraphtheoryZhangNaDepartmentofMathematicsofthe1102classTutor:ChenJinMeiAbstract：Thispaperintro

3、ducestheknowledgeofhistoricalsources,rationale,scopeandsomemathematicalinductionmathematicalinduction,followedbyanotherdetaileddescriptionofthetypesofmathematicalinduction,forexample,weoftensaythatthefirstmathematicalinductionandtwomathematicalinduction,wearenotfamiliarw

4、ithsome,liketheanti-induction,inductionjumping,dualinduction,andsoon.TheyallhavegreatapplicationingraphtheoryProof.Soexplainmathematicalinductioninsolvingproblemsingraphtheoryisagoodway.Finally,citedanumberofgraphtheoryusedininductionexample,thearticlemakestheargumentmor

5、epersuasive.Keywords:mathematicalinduction,graphtheory,anti-induction,inductionjumping,doubleinduction.ii1引言谈到数学归纳法，也许我们每个人对它都不陌生。记得高中学习数列时老师用数学归纳法给我们解决一道道证明题吗？那时我们对这种方法也许并没有太多的认知。但是，今天我们就来深入的研究和探讨下数学归纳法。在数学证明当中我们经常用到的一种方法就是数学归纳法，它经常被用来证明一些与自然数有关的命题。数学归纳法可具体分为一下几种：第一数学归纳

6、法，第二数学归纳法，反向归纳法，跳跃归纳法，双重归纳法等等。大多数人只知道有第一数学归纳法和第二数学归纳法，对其他的方法是闻所未闻。这就使得数学归纳法的历史来源，理论基础和运用技巧等不被人们所熟知。再谈图论，它已经拥有300多年的历史了,但一直以来解决好图论的相关问题始终是人们关注的焦点。然而伴随着信息技术的发展，图论又重新回到了人们的视野当中，又便成了人们研究和讨论的热点问题，下面我就来简单的一一介绍一下这些问题。2数学归纳法概论2.1数学归纳法简史归纳思想是这样产生的：我们都知道数学归纳法中有两个非常重要的基础推理归纳推理和演绎推理

7、，它们大概是在公元前六世纪出现的。到了公元前三世纪的时候，著名数学家欧几里德在证明“质数的个数是无穷的’时候指出:如果有个质数,就必定会有个质数”,这实际上就渗透了数学归纳法的思想。.但是到了近代，数学归纳法才被真正意义上地应用到数学证明当中。十六世纪时,意大利非常有名的数学家莫洛里科就证明了“前个奇数的和等于”这一重要结论。他通过推理得到：第一个平方数加第二个奇数等于第二个平方数,第二个平方数加第三个奇数等于第三个平方数,…因此，他成为历史上第一位应用数学归纳法的数学家。但他所用的这种证明方法却因风格比较随便而没能让世人得到认可。到了

8、十七世纪,法国的数学家帕斯卡又运用数学归纳法证明了二项式系数公式=。此举使他成为继莫洛里科之后第二个应用数学归纳法的人.但同样令人遗憾地是，这种方法没有没有延续到现在就消失了。131838年英国的数学家摩尔