郭紀(jì)云

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

每棵非平凡樹至少有兩片葉子的證法研究*

郭紀(jì)云

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

采用七種方法證明了每棵非平凡樹至少有兩片葉子，從而為相關(guān)內(nèi)容的研究提供了很好的理論參考.

圖;樹;葉子;度

樹是無圈的連通圖，葉子(或1度點)是指度為1的頂點.只有一個頂點的圖稱為平凡圖，其他所有的圖都稱為非平凡圖.既沒有環(huán)也沒有重邊的圖稱為簡單圖，也叫單圖.本文所涉及到的圖都是非平凡圖，并且都是有限的簡單圖.

引理 1［1，2］若 δ(G) ≥ 2，則 G 中含有圈.

證 設(shè)P是圖G中的一條最長路，u是P的一個端點.由于d(u)≥δ≥2，故存在一頂點w∈V，使得邊uw與P相交，不然P就不是最長路了.故圖G中含有圈.

引理2［3，4］若圖 G是 Δ ≥ k的樹，則 G至少有 k片葉子.

定理［5，6］每棵非平凡樹至少有兩片葉子.

這是一個較為簡單的命題，其證法頗多，現(xiàn)將它們詳細地總結(jié)出來，以期對讀者有所幫助.

證法1 設(shè)G是任意一棵非平凡樹，則對?v∈V，有d(v) ≥1，由度和公式得若 ?v∈ V，有d(v) ≥2，則矛盾.若存在唯一的頂點 v∈ V，使得 d(v)=1，則1=2V－1，也矛盾.故每棵非平凡樹至少有兩片葉子.

證法2 設(shè)G是任意一棵非平凡樹，并設(shè)G中共有x片葉子，則 2ε =又因為ε=V－1，從而可得x≥2.故G中至少有兩片葉子.

證法3 若對?u∈V，d(u)=2，則G是Euler圖，從而含有Euler閉跡.由于Euler閉跡可以表示成若干個圈的并，故G中有圈，這與樹的定義相矛盾.現(xiàn)設(shè)G中僅有一個1度點，有k個度大于等于3的奇度點，則2(V－1)=1+2(V－k－1)+3k，得到k≤－1＜0.由于奇度點的個數(shù)必為偶數(shù)，所以k必為正奇數(shù)，矛盾.假設(shè)不成立，故G中至少有2個1度點.

以上三種證法雖然思路各不相同，但都基于同一個重要定理──握手定理(即度和公式).由此可見，握手定理作為圖論第一定理，其地位和作用更加凸顯.

證法4 事實上，若非平凡樹的(u，v)－路的起點或終點的度大于1，這時因樹無圈，易知(u，v)－路可繼續(xù)延長.故非平凡樹中的最長路的起點和終點的度必為1.

證法5 若δ(G)≥2，由引理1知G中含有圈，這和G是樹不含圈矛盾.故G中至少存在一個頂點u，使得d(u)=1，在G中由u出發(fā)的(u，v) －路，若d(v)＞1，顯然(u，v) －路可繼續(xù)延伸，由于G中不含圈，這種路的延伸永遠不會停止，但這又和G是有限圖相矛盾，故G中除u外至少還存在一個頂點的度亦為1.

證法6 對V使用數(shù)學(xué)歸納法.當(dāng)V=2時，G=K2，結(jié)論顯然成立.假設(shè)V≤k－1時結(jié)論成立，則當(dāng)V=k(＞2)時，由于Δ≥2，所以由引理2知，頂點數(shù)V=k(＞2)的圖至少有2片葉子.故命題成立.

證法7 對V使用數(shù)學(xué)歸納法.當(dāng)V=2時，由證法6知結(jié)論已成立.假設(shè)V≤k－1時結(jié)論成立.現(xiàn)設(shè)G是任意一棵具有k(＞2)個頂點的樹，由證法5知G中至少存在一個頂點u，使得d(u)=1，下證G'=G－u是一棵具有V－1個頂點的樹.由于一個度為1的頂點不屬于任何一條連接其他兩個頂點的路.因此，對于w，v∈V(G')，G中每條 (w，v) －路都是G'中的路.因此G'亦是連通的，由于刪除一個頂點不會產(chǎn)生一個圈，因此G'亦是無圈的.所以G'是一棵具有V－1個頂點的樹，從而G中至少有2片葉子.

“數(shù)學(xué)是思維的體操.”發(fā)展思維是提高學(xué)生素質(zhì)的重要方面.而一題多解可以啟動學(xué)生的求異思維，加深學(xué)生對所學(xué)知識的深刻理解，訓(xùn)練學(xué)生對數(shù)學(xué)思維和數(shù)學(xué)方法的嫻熟運用，鍛煉學(xué)生思維的廣闊性和深刻性、靈活性和獨創(chuàng)性，從而培養(yǎng)學(xué)生的思維品質(zhì)，發(fā)展學(xué)生的創(chuàng)造性思維.

［1］Bondy J，Murty U S R.Graph Theory with Applications［M］.New York:Elsevier North Holl，Inc，1979.

［2］Bollobas B.Graph Theory:An Introductory Course［M］.New York:Springer－ verlag，Inc，1979.

［3］張先迪，李正良.圖論及其應(yīng)用［M］.北京:高等教育出版社，2005.

［4］孫惠泉.圖論及其應(yīng)用［M］.北京:科學(xué)出版社，2008.

［5］盧開澄，盧華明.圖論及其應(yīng)用［M］.北京:清華大學(xué)出版社，1995.

［6］王朝瑞.圖論［M］.北京:北京理工大學(xué)出版社，2001.

(責(zé)任編校:晴川)

O157.5

A

1008－4681(2011)05－0006－01

2011－07－14

郭紀(jì)云(1984－)，女，山東菏澤人，海南大學(xué)信息科學(xué)技術(shù)學(xué)院講師，碩士.研究方向∶圖論及其應(yīng)用.