郭紀(jì)云

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

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

郭紀(jì)云

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

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

圖;樹;葉子;度

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

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

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

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

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

這是一個(gè)較為簡(jiǎn)單的命題，其證法頗多，現(xiàn)將它們?cè)敿?xì)地總結(jié)出來，以期對(duì)讀者有所幫助.

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

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

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

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

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

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

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

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

“數(shù)學(xué)是思維的體操.”發(fā)展思維是提高學(xué)生素質(zhì)的重要方面.而一題多解可以啟動(dòng)學(xué)生的求異思維，加深學(xué)生對(duì)所學(xué)知識(shí)的深刻理解，訓(xùn)練學(xué)生對(duì)數(shù)學(xué)思維和數(shù)學(xué)方法的嫻熟運(yùn)用，鍛煉學(xué)生思維的廣闊性和深刻性、靈活性和獨(dú)創(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)用.