谈图论中数学归纳法应用.docVIP

谈图论中数学归纳法应用 　　摘要：数学归纳法是一种论证方法，这种方法作为工具总是很有用的通常用在证明数学上的猜想，因为它容许我们跨越我们所希望的那么多的阶梯，使我们省去冗长的、使人厌烦和单调的核验，而这种核验虽则可以不断地接近目的，却永远无法使我们达到它。图论中的许多命题的证明，都广泛地运用了数学归纳法。本文主要探讨图论中数学归纳法的应用。 　　关键词：图论；数学归纳法；应用 　　中图分类号：G712文献标识码：A文章编号：1009-0118（2012）12-0129-02 　　图论是一个应用比较广泛的数学分支，在许多领域，诸如物理学、化学、运筹学、计算机科学、网络理论、社会科学以及经济管理等方面都有广泛的应用。点、边（或弧）、面、连通分支等是图的基本要素，在图论的证明中经常用数学归纳法对点的个数、边的个数及连通分支个数等进行归纳。一般情况下，由于证明过程中需保持图的相关性质，因而需要选择合适的要素进行归纳。有些结论的证明既可以对一种要素的个数进行归纳，也可以对另一种要素的个数进行归纳；既可以用第一数学归纳法证明，也可以用第二数学归纳法证明，其中数学归纳法的运用既体现了严谨性的要求，又体现了灵活性，表现手法多样[1]。 　　一、数学归纳法 　　作为一个好的数学家，或者一个优秀的博弈者，或者要精通别的什么事情，你必须首先是一个好的猜想家，而要成为一个好的猜想家，我想，你首先是天资聪慧的。但天资聪慧当然还不够，你应当考察你的一些猜想，把它与事实进行比较，如果有必要，就对你的猜想进行修正，从而获得猜想失败与成功的广泛经验。在你的经历中如果具备这样一种经验，你就能够判断得比较适当，碰到一种机遇，就能大致预知它的是非结果。 　　自然科学中的“经验归纳法”，是从某一现象的一系列特定的观察出发，归纳出支配该现象所有情况的一般规律，而数学归纳法则是迥然不同的另种手段，它用来证实有关无限序列（第一个，第二个，第三个，等等，没有一个情况例外）的数学定理的正确性。数学归纳法的原理是奠基在下属事实的基础上：在任一整数r之后接着便有下一个r+1，从而从??数1出发，通过有限多次这种步骤，便能达到任意选定的整数n。数学归纳法原理与经验归纳法是完全不同的，一般的定律如果被证实了任意有限次，那么不论次数多么多，甚至至今尚未发现例外，都不能说该定律在严格的数学意义下被证明了，这种定律只能算作十分合理的假设，它容易为未来的经验结果所修正。在数学中，一条定律或一个定理所谓被证明了，指它是从若干作为真理接受的假设出发而得到的逻辑推论。人们考察一个定理，如果它在许多实例中是正确的，那么就可猜想定理在普遍意义下将是真的；然后人们尝试用数学归纳法以证明之。如果尝试成功，定理被证明为真；如果尝试失败，则定理的真伪未定，有待以后用其他方法予以证明或者推翻[2]。 　　二、数学归纳法的具体表现形式 　　归纳法分为完全归纳法和不完全归纳法，而数学归纳法属于完全归纳法，它又分为有限数学归纳法和超限数学归纳法，对于后者，在实变函数论中会学到；前者有两种不同的形式，它们分别叙述为： 　　第一数学归纳法：如果性质P（n）在n=1时成立，而且在假设了n=k时性质P（k）成立后，可以推出在n=k+1时性质P（k+1）也成立，那么我们可以断定性质P（n）对一切自然数n都成立。 　　第二数学归纳法：如果性质P（n）在n=1时成立，而且在假设了对所有小于或等于k的自然数n性质P（n）都成立后，可以推出在n=k+1时性质P（k+1）也成立，那么性质P（n）对一切自然数n都成立。 　　数学归纳法是一种常用的不可缺少的推理论证方法，第一数学归纳法与第二数学归纳法在数学的证明中经常用到，而反归纳法、跳跃归纳法与双重归纳法在数学的证明中不是很常见的。然而如上所述，利用数学归纳法证明与图论有关的命题，可降低证明过程的复杂性，使推理过程简单、清晰，也保证了推理的严谨性。 　　例1：某生产队科学实验小组决定研究n（n≥2）种害虫之间的关系，然后想法消灭它们，经实验，他们发现，其中任意两种总有一种可吞食另一种。试证明可把此几种害虫排成一行，使得前一种可吞食后一种。证明⑴n=2时，命题显然成立。⑵设n=k时（k≥2），结论成立。我们不妨以ai（i=1，2，…，k）表示第i种害虫，记这时可将它们排成a1a2，…ak，其中前一种可吞食后一种。用（akak+1表示可吞食a+1） 　　下面考虑n=k+1时的情形，即在上面情形里加进一种害虫ak+1（当然，我们还可以将k+1种害虫分为两组，一组k，一组一种，由归纳假设第一组k种可排成a1，a2，…ak，使前一种可吞食后一种，再将第二组的一种记为ak+1加入），将有面两种情形： 　　（1）若ak+1a，则可将ak+1置a1前，则有ak+1a1a2…ak。命题为真；（2）若a1