图论中数学归纳法的应用

金斯琴图雅　任媛

[摘 要] 数学归纳法是数学中经常用到的论证方法。这种论证方法在证明自然数不等式的关系、数列前n项和与通项公式是否成立等数学问题上都有应用。现阶段，数学归纳法也在图论中得到应用，对数学归纳法在图论中的应用作进一步的阐述。

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

[中图分类号] G642 [文献标志码] A [文章编号] 2096-0603（2018）16-0182-01

图论是数学的一个分支，很多的学科和领域都会涉及图论，比如说物理学、化学、计算机科学、社会科学等。在对图论进行证明的过程中，要对其点、边、面以及连通分支等基本要素的个数进行归纳。在多数情况下，为了确保图的相关性，我们要在整个证明过程中选择最适合的基本要素进行归纳。一些证明题的论证方式不是单一的，可以选择对一种要素或者多种要素的个数进行归纳。除此之外，也可以选择使用第一种数学归纳法或者第二种数学归纳法分别对证明题进行论证。由此可见，数学归纳法的推导方式是十分灵活的。

一、数学归纳法

一个人如果想要在数学或者某个学科领域上做到精通，就要有相应的天分。当然，有一定的天分只是获得成功的基础，还需要利用自己的潜能提出合理的猜想和假设，然后将猜想的结果与客观事实进行比较，通过探讨分析验证假设是否成立。不论猜想的结果是否符合客观事实，在论证的过程中，人们都积累了经验。当机遇来临时，前期所积累的经验可以帮助人们做出正确的判断。

数学归纳法跟自然科学中的“经验归纳法”的规则是完全不同的，经验归纳法通过观察一种现象并且对这种现象表现出来的情况进行归纳；而数学归纳法证明的是一些跟现象无关的数学定理的结果。通过以下的事实论证阐述数学归纳法的基本原理：比如说在某一个整数r的后面就是r+1，然后通过从整数1之后反复的验证就可以达到随意选定的整数n。所以，数学归纳法跟经验归纳法这两种方法的原理是有很大区别的。在一般的定律中，不管这个定律经过多少次的论证都只能将其称作合理的假设而不能被当做严格的证明，但是极有可能在未来的论证中被修改证明。数学中的定律和定理的证明结果都是经过无数次论证做出的逻辑推论。人们通常会将经过数次论证后正确次数比较多的定理作为最正确的猜想结果，然后试着应用数学归纳法将这些结果进行论证，以验明结论的真伪。

二、数学归纳法的表现形式

归纳法包含完全归纳法和不完全归纳法两种法则，数学归纳法是完全归纳法的其中一种。数学归纳法也包括了有限和超限两种数学归纳法，超限的归纳法通过函数论学习，有限数学归纳法包含了两种表现形式，具体表述如下：

第一种，数学归纳法：假设说性质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也都成立。

数学归纳法中的第一种和第二种归纳法经常在学习数学的证明中应用，是一种严谨的推论方法。所以将图论中需要证明的命题利用数学归纳法去論证就可以将这个过程简化，保障科学严谨的推理结果。而且在数学归纳法中步骤必须是完整的，以避免发生错误。

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

例题：假如p阶图G是一棵树，证明G有p-1条边。方法1（第一数学归纳法）：当p=2时，结论是对的。假如p=k时结果正确，当p=k+1时，因G没有圈，所以收缩了G的一条边以后，G的边数和顶点数都少了一个，就变成了k个顶点的树，根据归纳的假设边有k-1条将之前的边拿回来之后顶点数就变成了k+1边数变成了k，结果得到了验证。

图论是一门涉及范围十分广泛以及内容全面丰富的学科，在实际的工程中也常常可以应用到图论的基本知识理论。数学归纳法作为一种无法替代的证明方法在所有证明题的论证中都起到了十分关键的作用。

数学归纳法在图论中的作用是无法替代的。如果没有数学归纳法，与数字有关的证明题就难以论证。另外，不完全归纳法验证的结论也不一定是完全正确的，所以数学归纳法是一种最有效的科学可靠的论证方法，而且对学生智力的开发很有帮助，所以数学归纳法在图论中的应用具有非常重要的意义。

参考文献：

[1]王万禹，马蓓蓓.数学归纳法在图论题解中的典型应用[J].成都师范学院学报，2017（9）：98-101.

[2]方冬云.数学归纳法在图论中的应用[J].莆田学院学报，2015（2）：40-42.

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

[4]陈美珍.数学归纳法在离散数学中的应用[J].郧阳师范高等专科学校学报，2014（3）：19-20.