圖論中數(shù)學歸納法的應用

金斯琴圖雅　任媛

[摘 要] 數(shù)學歸納法是數(shù)學中經(jīng)常用到的論證方法。這種論證方法在證明自然數(shù)不等式的關系、數(shù)列前n項和與通項公式是否成立等數(shù)學問題上都有應用。現(xiàn)階段，數(shù)學歸納法也在圖論中得到應用，對數(shù)學歸納法在圖論中的應用作進一步的闡述。

[關 鍵 詞] 圖論；數(shù)學歸納法；應用

[中圖分類號] G642 [文獻標志碼] A [文章編號] 2096-0603（2018）16-0182-01

圖論是數(shù)學的一個分支，很多的學科和領域都會涉及圖論，比如說物理學、化學、計算機科學、社會科學等。在對圖論進行證明的過程中，要對其點、邊、面以及連通分支等基本要素的個數(shù)進行歸納。在多數(shù)情況下，為了確保圖的相關性，我們要在整個證明過程中選擇最適合的基本要素進行歸納。一些證明題的論證方式不是單一的，可以選擇對一種要素或者多種要素的個數(shù)進行歸納。除此之外，也可以選擇使用第一種數(shù)學歸納法或者第二種數(shù)學歸納法分別對證明題進行論證。由此可見，數(shù)學歸納法的推導方式是十分靈活的。

一、數(shù)學歸納法

一個人如果想要在數(shù)學或者某個學科領域上做到精通，就要有相應的天分。當然，有一定的天分只是獲得成功的基礎，還需要利用自己的潛能提出合理的猜想和假設，然后將猜想的結(jié)果與客觀事實進行比較，通過探討分析驗證假設是否成立。不論猜想的結(jié)果是否符合客觀事實，在論證的過程中，人們都積累了經(jīng)驗。當機遇來臨時，前期所積累的經(jīng)驗可以幫助人們做出正確的判斷。

數(shù)學歸納法跟自然科學中的“經(jīng)驗歸納法”的規(guī)則是完全不同的，經(jīng)驗歸納法通過觀察一種現(xiàn)象并且對這種現(xiàn)象表現(xiàn)出來的情況進行歸納；而數(shù)學歸納法證明的是一些跟現(xiàn)象無關的數(shù)學定理的結(jié)果。通過以下的事實論證闡述數(shù)學歸納法的基本原理：比如說在某一個整數(shù)r的后面就是r+1，然后通過從整數(shù)1之后反復的驗證就可以達到隨意選定的整數(shù)n。所以，數(shù)學歸納法跟經(jīng)驗歸納法這兩種方法的原理是有很大區(qū)別的。在一般的定律中，不管這個定律經(jīng)過多少次的論證都只能將其稱作合理的假設而不能被當做嚴格的證明，但是極有可能在未來的論證中被修改證明。數(shù)學中的定律和定理的證明結(jié)果都是經(jīng)過無數(shù)次論證做出的邏輯推論。人們通常會將經(jīng)過數(shù)次論證后正確次數(shù)比較多的定理作為最正確的猜想結(jié)果，然后試著應用數(shù)學歸納法將這些結(jié)果進行論證，以驗明結(jié)論的真?zhèn)巍?/p>

二、數(shù)學歸納法的表現(xiàn)形式

歸納法包含完全歸納法和不完全歸納法兩種法則，數(shù)學歸納法是完全歸納法的其中一種。數(shù)學歸納法也包括了有限和超限兩種數(shù)學歸納法，超限的歸納法通過函數(shù)論學習，有限數(shù)學歸納法包含了兩種表現(xiàn)形式，具體表述如下：

第一種，數(shù)學歸納法：假設說性質(zhì)P（n）在n=1時是成立的，同時在假設了n=k時性質(zhì)P（k）的結(jié)果也是可以成立的之后，就可以推論出在n=k+1時性質(zhì)P（k+1）也是會成立的，就能判定出性質(zhì)P（n）對一切自然數(shù)n都是成立的。

第二種數(shù)學歸納法：假設說性質(zhì)P（n）在n=1時是成立的，同時假設了對所有小于或等于k的自然數(shù)n性質(zhì)P（n）的結(jié)果都是成立的以后，可以推論出在n=k+1時性質(zhì)P（k+1）也成立，所以性質(zhì)P（n）對一切自然數(shù)n也都成立。

數(shù)學歸納法中的第一種和第二種歸納法經(jīng)常在學習數(shù)學的證明中應用，是一種嚴謹?shù)耐普摲椒āＫ詫D論中需要證明的命題利用數(shù)學歸納法去論證就可以將這個過程簡化，保障科學嚴謹?shù)耐评斫Y(jié)果。而且在數(shù)學歸納法中步驟必須是完整的，以避免發(fā)生錯誤。

三、圖論中數(shù)學歸納法的應用

例題：假如p階圖G是一棵樹，證明G有p-1條邊。方法1（第一數(shù)學歸納法）：當p=2時，結(jié)論是對的。假如p=k時結(jié)果正確，當p=k+1時，因G沒有圈，所以收縮了G的一條邊以后，G的邊數(shù)和頂點數(shù)都少了一個，就變成了k個頂點的樹，根據(jù)歸納的假設邊有k-1條將之前的邊拿回來之后頂點數(shù)就變成了k+1邊數(shù)變成了k，結(jié)果得到了驗證。

圖論是一門涉及范圍十分廣泛以及內(nèi)容全面豐富的學科，在實際的工程中也常?？梢詰玫綀D論的基本知識理論。數(shù)學歸納法作為一種無法替代的證明方法在所有證明題的論證中都起到了十分關鍵的作用。

數(shù)學歸納法在圖論中的作用是無法替代的。如果沒有數(shù)學歸納法，與數(shù)字有關的證明題就難以論證。另外，不完全歸納法驗證的結(jié)論也不一定是完全正確的，所以數(shù)學歸納法是一種最有效的科學可靠的論證方法，而且對學生智力的開發(fā)很有幫助，所以數(shù)學歸納法在圖論中的應用具有非常重要的意義。

參考文獻：

[1]王萬禹，馬蓓蓓.數(shù)學歸納法在圖論題解中的典型應用[J].成都師范學院學報，2017（9）：98-101.

[2]方冬云.數(shù)學歸納法在圖論中的應用[J].莆田學院學報，2015（2）：40-42.

[3]王天成.數(shù)學歸納法的邏輯原理及其在圖論中的應用[J].青海師范大學民族師范學院學報，2014（1）：66-67.

[4]陳美珍.數(shù)學歸納法在離散數(shù)學中的應用[J].鄖陽師范高等?？茖W校學報，2014（3）：19-20.