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

摘要：数学归纳法是一种论证方法，这种方法作为工具总是很有用的通常用在证明数学上的猜想，因为它容许我们跨越我们所希望的那么多的阶梯，使我们省去冗长的、使人厌烦和单调的核验，而这种核验虽则可以不断地接近目的，却永远无法使我们达到它。图论中的许多命题的证明，都广泛地运用了数学归纳法。本文主要探讨图论中数学归纳法的应用。

关键词：图论；数学归纳法；应用

中图分类号：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，其中前一种可吞食后一种。用（ak>ak+1表示可吞食a+1）

下面考虑n=k+1时的情形，即在上面情形里加进一种害虫ak+1（当然，我们还可以将k+1种害虫分为两组，一组k，一组一种，由归纳假设第一组k种可排成a1，a2，…ak，使前一种可吞食后一种，再将第二组的一种记为ak+1加入），将有面两种情形：

（1）若ak+1>a，则可将ak+1置a1前，则有ak+1>a1>a2>…ak。命题为真；（2）若a1>ak+1，再将ak+1与a2放在一起试验，若ak+1>a，可将ak+1置a1后a2前即可，这时有a1>ak+1>a2>Λ>ak，命题为真。否则可重复往下试验，经过有限次（≤k次），必有下列情形之一：ai-1>ak+1>ai，问题解决。否则ak>ak+1，则可置ak+1于ak之后。此时有a1>a2>…>ak>ak+1，命题亦成立。

综上，命题对k+1成立，从而对任意自然数（n≥2）成立。

第二数学归纳法的应用

例2：证明（1）当n=1时，D1=cosθ，猜想成立。（2）假设n≤k-1时，Dk=coskθ，当n=k时，由式（1），有Dn=2cosθcos（n-1）θ-cos（n-2）θ=cosnθ+cos（n-2）θ-cos（n-2）θ=cosnθ，故k=n时，有Dk=coskθ，归纳法完成，故对一切n∈N*，都有Dn=cosnθ。总之，数学归纳法的两个步骤，缺一不可。即都是必须的，否则将不完整，甚至导出错误的结果。

三、图论中数学归纳法中的应用

例3：设A是G的邻接矩阵，证明Ak的（i，j）元素a（k）ij等于G中联结vi和vj的长为k的途径的数目[3]。

证明：对k用归纳法。当k=0时A0=I为p价单位矩阵。从任一顶点vi到自身有一条长为0的途径，任何两个不同的顶点间没有长为0途径，故当k=0时结论成立。

今设结构对k成立，由Ak+1=AAk，故有

a（k+1）ij=∑p12l=1aijalj（k）

由于aij同是联结vi与vl的长为1的途径的数目，alj（k）是联结vl与vj长为k的途径的数目，所以ailalj（k）表示由vi经过一条到vl，再经过一条长为k的途径为vj的总长为k+1的途径的数目，对所有的l求和，即得a（k+1）ij是所有联结vi与vj长为k+1的途径的数目，由归纳法原理，结论得证。

例4：p阶图G是一棵树，证明G有p-1条边。方法1（第一数学归纳法）：当p=2时，结论显然成立。假设p=k时结论为真，当p=k+1时，因为G没有圈，当把G中的一条边收缩后，G的边数和顶点数均少1，变成k个顶点的树，由归纳假设，应有k-1条边，再把去掉的边放回，则顶点数为k+1而边数为k，于是结论得证。

图论这门学科的内容十分丰富，涉及的面也比较广，图论中的基础知识，又是工程实际中经常用到的。数学归纳法在结论以及命题的证明过程中起了画龙点睛的作用，是其它证明方法所不可代替的。

四、结论

数学归纳法是一种常用的不可缺少的推理论证方法，没有它，在图论中很多与自然数有关的命题难以证明；同时对于与自然数有关的命题，把n所取的无穷多个值一一加以验证是不可能的，用不完全归纳法验证其中一部分又很不可靠，数学归纳法则是一种用有限步骤证明与自然数有关的命题的可靠方法，其思维方式对于开发学生的智力有重要价值。在图论学习中，掌握并应用好这一方法有十分重要的意义。

参考文献：

[1]华罗庚.数学归纳法[M].上海：上海教育出版社，1963.

[2]王天成.数学归纳法的逻辑原理及其在图论中的应用[J].青海师范大学民族师范学院学报，2008，19（1）：66-67.

[3]王淑栋，庞善臣.系列平行图的边色数[J].山东科技大学学报（自然科学版），2002，21（2）：7-10.