關(guān)于樹的若干等價(jià)性命題

王曉敏, 趙喜楊, 姚　兵

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070)

?

關(guān)于樹的若干等價(jià)性命題

王曉敏, 趙喜楊, 姚兵*

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070)

摘要：給出15種關(guān)于樹的等價(jià)性命題, 為更好地發(fā)揮樹在網(wǎng)絡(luò)研究中的作用提供依據(jù)，為這15個(gè)等價(jià)命題提供了簡(jiǎn)單而新的證明。

關(guān)鍵詞:樹；生成樹；圈；路；度數(shù)

MR subject classification: 05C05, 05C69, 05C82

樹在各種網(wǎng)絡(luò)、程序設(shè)計(jì)、物流運(yùn)輸、電路設(shè)計(jì)、化學(xué)結(jié)構(gòu)等領(lǐng)域有著廣泛的應(yīng)用。例如, 利用生成樹來尋找無標(biāo)度網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)以及用樹來確定網(wǎng)絡(luò)的控制集等, 還可以利用無標(biāo)度生成樹來確定動(dòng)態(tài)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu), 揭示現(xiàn)實(shí)網(wǎng)絡(luò)存在的規(guī)律性。在數(shù)學(xué)的分支圖論中, 樹是除路和圈之外最簡(jiǎn)單的圖類, 人們用它來刻畫許多的圖類以及圖的性質(zhì)。最典型的是, 有關(guān)樹的數(shù)學(xué)猜想非常多[1]。例如, 著名的優(yōu)美樹猜想[2], 這個(gè)猜想的解決就可以導(dǎo)致諸如Ringle猜想[3]等若干猜想的解決。此外, 在研究一些懸而未決的問題往往從樹這種情形開始著手[4-5], 如直徑為4的優(yōu)美樹[6]、 最優(yōu)樹的若干問題[7]、 弱優(yōu)美樹及其應(yīng)用[8]。因此, 對(duì)樹的深入研究不僅是數(shù)學(xué)理論的需要, 更重要的是為研究實(shí)際網(wǎng)絡(luò)提供可靠的理論依據(jù)和可行的技術(shù)手段。

文中所考慮的圖均為有限、無向、簡(jiǎn)單圖, 沒有定義的術(shù)語和符號(hào)參考文獻(xiàn)[12]。我們把度數(shù)為1的頂點(diǎn)稱為葉子。用p(G)和q(G)分別表示圖G的頂點(diǎn)個(gè)數(shù)和邊的數(shù)目。n個(gè)頂點(diǎn)的完全圖記為Kn, 只有一個(gè)頂點(diǎn)的圖記為K1。符號(hào)nd(G)表示圖G中度數(shù)為d的頂點(diǎn)的個(gè)數(shù)。縮邊圖G·e是刪去圖G的邊e并將邊e的2個(gè)端點(diǎn)重合所得到的圖。對(duì)圖G的2個(gè)不相鄰的頂點(diǎn)u和v添加邊uv=e+, 再刪除圖G的一條不是邊e+的邊e-, 稱這種運(yùn)算為(e+,e-)-運(yùn)算, 也說對(duì)圖G實(shí)施了一次(e+,e-)-運(yùn)算。

1結(jié)論及其證明

定理設(shè)圖G是非平凡簡(jiǎn)單圖, 下面的命題兩兩等價(jià):

(1) 圖G連通且無圈[9]。

(2) 對(duì)p個(gè)頂點(diǎn)的連通圖G實(shí)施一系列(e+,e-)-運(yùn)算后, 總可以得到一條p個(gè)頂點(diǎn)的路。

(3) 圖G的任意一對(duì)頂點(diǎn)由唯一的一條路連接[9]。

(4)G恰有p(G)[p(G)-1]/2條路, 且任意一對(duì)頂點(diǎn)至少由一條路連通[12]。

(5) 對(duì)于任意的邊e∈E(G),G是使得圖G-e不連通的最小連通圖[12]。

(6)G是連通圖, 且q(G)=p(G)-1[9]。

(7)G是無圈圖, 且q(G)=p(G)-1[9]。

(10) 令連通圖G=G0, 則存在k≥1, 使得圖Gi(i=1、2、…、k)至少含有Δ(Gi)片葉子, 刪去圖Gi的Δ(Gi)片葉子得到圖Gi+1, 且Gk=K1。

(11) 圖G的每條邊都是圖G的割邊, 且q(G)=p(G)-1[12]。

(12) 圖G的每個(gè)度數(shù)不為1的頂點(diǎn)都是圖G的割點(diǎn), 且q(G)=p(G)-1[12]。

(13) 圖G連通, 對(duì)于任意的邊e∈E(G), 圖G的生成樹的個(gè)數(shù)等于縮邊圖G·e的生成樹的個(gè)數(shù)。

(14) 當(dāng)m≥3時(shí), 連通圖G不是完全圖Km, 且對(duì)圖G的任何2個(gè)不相鄰的頂點(diǎn)u和頂點(diǎn)v添加邊uv, 則圖G+uv含有唯一的圈[9]。

(15) 設(shè)G≠K1∪K3或G≠K2∪K3, 且q(G)=p(G)-1,對(duì)于圖G中任何2個(gè)不相鄰的頂點(diǎn)u和頂點(diǎn)v添加邊uv, 則圖G+uv包含唯一的圈[9]。

證明以下用符號(hào)(i)?(k)表示從命題(i)來證明命題(k), 1≤i,k≤15以及i≠k。

(1)?(2)，因p個(gè)頂點(diǎn)的圖G連通, 如果圖G有圈, 則對(duì)圖G實(shí)施一次(e+,e-)-運(yùn)算不能減少圈的數(shù)目,即無論實(shí)施多少次(e+,e-)-運(yùn)算, 都得不到一條路, 矛盾。從而, 圖G無圈。若圖G為路, 證明完成。如果圖G不是路, 則圖G的葉子數(shù)目n1(G)≥3,其中有2片葉子x、y在圖G的路P=xu1u2…uky上, 另外一片葉子w與圖G的頂點(diǎn)w′ 相鄰。對(duì)圖G實(shí)施一次(e+,e-)-運(yùn)算, 其中e+=yw,e-=ww′, 得新圖G1的路P+yw。易知,n1(G)≥n1(G1)。如此進(jìn)行下去，存在k使得Gk是一條p個(gè)頂點(diǎn)的路。命題(2)得證。

(2)?(3)，由于圖G的任何一對(duì)頂點(diǎn)u和頂點(diǎn)v之間至少有一條路P(u,v)，則G是連通圖。反設(shè)頂點(diǎn)u和頂點(diǎn)v之間的路不唯一, 假設(shè)頂點(diǎn)u和頂點(diǎn)v之間存在另外一條不同于路P(u,v)的路Q(u,v)，說明圖G含圈, 則對(duì)圖G實(shí)施多少次(e+,e-)-運(yùn)算不能減少圈的數(shù)目, 即得不到一條路，矛盾于命題(2)。

(3)?(4)，考慮到圖G的任何一對(duì)頂點(diǎn)之間都有一條路, 故圖G是連通的, 這導(dǎo)致圖G至少有p(G)[p(G)-1]/2條不同的路。如果圖G有多于p(G)[p(G)-1]/2條路, 將產(chǎn)生一對(duì)頂點(diǎn)至少有2條路, 這冒犯命題(3)。

(4)?(5)，反設(shè)命題(5)不成立, 即圖G有一條邊e, 使得刪去邊e的余圖G-e是連通的, 可導(dǎo)出圖G-e至少有p(G-e)[p(G-e)-1]/2條不同的路。注意到,p(G)=p(G-e), 推出圖G至少有1+p(G)[p(G)-1]/2條不同的路, 與命題(4)沖突。

(5)?(6)，對(duì)圖G的頂點(diǎn)數(shù)目p(G) 使用歸納法。當(dāng)p(G)=2時(shí)，余圖G-e不連通，又一條邊僅能連2個(gè)分支G1、G2。得 |V(G1)|=|V(G2)|=1, 可算出q(G)=1=2-1=|V(G1)|+|V(G2)|-1=p(G)-1。設(shè)當(dāng)p(G)=k時(shí)，命題(6)成立?？紤]p(G)=k+1時(shí)的情形。由于對(duì)任意一條邊e∈E(G)，圖G-e不連通，且G-e有2個(gè)分支H1、H2。由歸納法，知q(Hi)=p(Hi)-1,i=1、2。從而，有q(G)=q(H1)+q(H2)+1=p(H1)+p(H2)-2+1=p(G)-1。由于圈上的邊e皆不能使得G是圖G-e不連通的最小連通圖，故G無圈。命題(6)獲證。

(6)?(7)，反設(shè)圖G含圈, 則刪去圈中的任意一條邊e, 得到的圖G-e仍連通, 若G-e含圈C, 則繼續(xù)刪除圈C上的一條邊, 如此下去, 直到所得到的圖不含圈。設(shè)這樣刪除的邊的集合為E1, 顯然G-E1是連通圖且不含圈, 并有q(G-E1)=p(G-E1)-1, 注意到p(G-E1)=p(G), 則有

q(G)=q(G-E1)+|E1|=

p(G-E1)-1+|E1|=

p(G)+|E1|-1≥p(G),

矛盾于命題(7)。

(7)?(8)，反設(shè)圖G有m(m≥1) 個(gè)分支G1、G2、…、Gm, 其中m≥2。根據(jù)命題(7), 每個(gè)分支Gi滿足q(Gi)=p(Gi)-1(i=1、2、…、m)。由于圖G的邊數(shù)目

p(G)-m,

2p(G)-2m。

這與命題(9)沖突, 亦即圖G是連通圖。由于

2+[Δ(G)-2]nΔ(G)(G) ≥Δ(G),

且Δ(G)>0 (圖G是非平凡圖), 說明圖G至少有Δ(G)片葉子, 則可以刪去圖G的Δ(G)片葉子, 得到一個(gè)連通圖G1；又因G1連通，命題(9)保證

Δ(G1)>0,

所以圖G1至少有Δ(G1)片葉子, 刪去它的Δ(G1)片葉子后, 得到圖G2；如此進(jìn)行下去, 由于圖G的頂點(diǎn)數(shù)目有限, 依次可得圖G0、G1、…、Gk, 其中G=G0和Gk=K1, 且每個(gè)圖Gi至少有Δ(Gi)片葉子, 刪去圖Gi的Δ(Gi)片葉子就得到圖Gi+1(i=0、1、2、…、k-1)。

(10)?(11)，如果圖G有一條非割邊xy, 則邊xy在圖G的一個(gè)圈C上。由于圈C上的頂點(diǎn)不是葉子, 亦即, 依次刪去葉子最后所得到的圖Gk總含圈C, 即Gk≠K1, 與命題(10)矛盾。圖G的每一條邊都是割邊，說明圖G不含圈。如果圖G不連通, 設(shè)它有分支G1、G2、…、Gm(m≥2)。根據(jù)命題(10)，每個(gè)Gi對(duì)應(yīng)圖Gi,1、Gi,2、…、Gi,mi, 其中Gi,mi=K1, 刪去圖Gi,j的Δ(Gi)片葉子就得到圖Gi,j+1(j=0、1、2、…、mi-1)。當(dāng)m≥2時(shí)，進(jìn)行刪去葉子運(yùn)算，最后得到m個(gè)K1，與命題(10)矛盾，只有圖G不含圈且連通，這導(dǎo)致q(G)=p(G)-1。

(11)?(12)，假定圖G有一個(gè)度數(shù)不為1的頂點(diǎn)w是圖G的割點(diǎn),即圖G-w的分支數(shù)目與圖G的分支數(shù)目相同, 則與頂點(diǎn)w相鄰的每一個(gè)頂點(diǎn)都不是葉子。任取頂點(diǎn)w的鄰點(diǎn)z, 刪去邊wz所得的余圖G-wz的分支數(shù)目與圖G的分支數(shù)目相等, 即邊wz不是圖G的割邊, 這與命題(11)相悖, 說明圖G的每一個(gè)度數(shù)大于1的頂點(diǎn)均為圖G的割點(diǎn)。由q(G)=p(G)-1立得命題(12)。

(12)?(13)，設(shè)e=uv是圖G的任意一條邊。收縮邊e=uv后得到縮邊圖G·e, 記頂點(diǎn)u與頂點(diǎn)v重合后的頂點(diǎn)為w*。命題(12)指出圖G無圈, 且q(G)=p(G)-1。由(7)?(8), 從而圖G和縮邊圖G·e均有生成樹。如果圖G的生成樹的個(gè)數(shù)不等于縮邊圖G·e的生成樹的個(gè)數(shù), 則圖G含有不通過邊e的生成樹,亦即, 圖G有一個(gè)包含邊e的圈, 相應(yīng)地, 在縮邊圖G·e里可以找到一個(gè)包含頂點(diǎn)w*的圈。以上事實(shí)推出q(G)≥p(G), 但這與命題(12)沖突。

(13)?(14)， 在命題(13)下, 圖G有生成樹, 則圖G連通；并且, 圖G的生成樹的個(gè)數(shù)等于縮邊圖G·e的生成樹的個(gè)數(shù), 保證圖G不含圈，自然有圖G不是完全圖Km(m≥3)。因?yàn)閳DG至少包含一對(duì)不相鄰的頂點(diǎn)u和頂點(diǎn)v, 給圖G添加邊uv后, 得到圖G+uv。如果圖G+uv包含2個(gè)圈C和C′, 則圈C和C′有且僅有一條公共邊uv。那么, 刪去邊uv, 圈C和C′合并成圖G的一個(gè)圈, 矛盾于圖G不含圈，即矛盾于命題(13)。故命題(14)得證。

(14)?(15)，當(dāng)p(G)=2時(shí), 無意義, 以下設(shè)p(G)≥3。由命題(14)的條件, 圖G連通且不是完全圖Km(m≥3)。注意到，命題(15)的條件q(G)=p(G)-1≠p(G)[p(G)-1]/2,也說明圖G不是完全圖。如果G≠K1∪K3或G≠K2∪K3, 這與命題(14)沖突。按照命題(14), 連接圖G的2個(gè)不相鄰的頂點(diǎn)u和v, 加邊圖G+uv僅含唯一的圈, 命題(15)得證。

(15)?(1)，假定圖G不連通, 即圖G至少含有2個(gè)分支G1和G2。當(dāng)|G1|+|G2|=4時(shí), 命題(15)保證G≠K1∪K3, 故連接圖G的2個(gè)不相鄰的頂點(diǎn)u和v所得到的加邊圖G+uv不含圈, 矛盾于命題(15)。當(dāng)|G1|=2和|G2|=3時(shí), 命題(15)保證G≠K2∪K3,連接圖G的2個(gè)不相鄰的頂點(diǎn)u和v, 則圖G+uv不含圈, 矛盾；當(dāng)|G1|=1和|G2|=4時(shí), 命題(15)條件q(G)=p(G)-1意味著G2等于4個(gè)頂點(diǎn)的圈, 連接這個(gè)圈上的2個(gè)不相鄰的頂點(diǎn)x和y, 則圖G+xy含2個(gè)圈, 與命題(15)沖突。當(dāng)|G1|+ |G2|≥6時(shí), 如果|G1|≤2和|G2|≥4, 容易找到矛盾點(diǎn)；如果|G1|≥3和|G2|≥3, 命題(15)條件q(G)=p(G)-1約束分支G1和G2中至多一個(gè)有圈, 不失一般性,G2含圈。但是, 連接分支G1的2個(gè)不相鄰的頂點(diǎn)s和t, 則圖G+st至少含2個(gè)圈, 與命題(15)矛盾。當(dāng)圖G有3個(gè)以上的分支時(shí), 選取G1和G2是最大或次最大的分支, 其余論證相同于上面的論證。注意, 當(dāng)圖G有3個(gè)以上的分支時(shí), 取前面2個(gè)分支的頂點(diǎn)u∈G1和頂點(diǎn)v∈G2, 給頂點(diǎn)u和頂點(diǎn)v連上一條邊uv, 所得到的加邊圖G+uv不含唯一圈, 矛盾。說明假設(shè)圖G不連通是錯(cuò)誤的。圖G連通結(jié)合命題(15)條件立得命題(1)。

上述證明過程表明：對(duì)1≤i,k≤15, 且i≠k時(shí), 命(i)成立的充要條件是命題(k)成立, 定理得證。

2結(jié)語

以上等價(jià)命題各有利弊, 但是從多個(gè)角度、寬領(lǐng)域地刻畫了樹。不難看到：命題(1)不僅是樹的定義最常用的方式, 而且容易在實(shí)際當(dāng)中使用。命題(3)和命題(4)分別從路的唯一性和路的數(shù)目的方向進(jìn)行論證，實(shí)際網(wǎng)絡(luò)研究中不易運(yùn)用。命題(5)較為抽象，屬于極值類刻畫。命題(6)和命題(7)由頂點(diǎn)數(shù)和邊數(shù)的關(guān)系分別引出了無圈和連通的結(jié)論。命題(9)給出了葉子頂點(diǎn)的數(shù)目, 可以用命題(9)的方式來建立平面圖的面數(shù)目與度為d的頂點(diǎn)個(gè)數(shù)之間的關(guān)系式。反復(fù)使用命題(10), 最終使得圖收縮到一個(gè)頂點(diǎn)的完全圖K1, 可以用來尋找網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。命題(11)和命題(12) 從割邊和割點(diǎn)的角度闡述了有關(guān)圖的連通性, 命題(13)是比較隱晦的有關(guān)樹的命題，適用于歸納法討論的情形。命題(14)的條件弱于命題(15)。再有, 我們認(rèn)為“連通圖G任何一個(gè)連通子圖皆是樹”是一個(gè)平凡的等價(jià)性命題, 因而沒有將它放進(jìn)前面的定理中。

本文中舉例給出的等價(jià)性命題可以平行地建立圖論中“森林”概念的等價(jià)性命題。

后續(xù)研究中，以下問題值得注意：是否存在不同于本文的其他非平凡的樹的等價(jià)命題？

致謝感謝審稿人對(duì)本文提出的寶貴意見和指導(dǎo)性建議, 使得本文趨于嚴(yán)謹(jǐn)和完善, 并激發(fā)作者又找到樹的一個(gè)等價(jià)命題。

參考文獻(xiàn):

[1] JOSEPH A G. A dynamic survey of graph labelling [J].The Electronic Journal of Combinatorics,2009,14:6.

[2] ROSA A．On certain valuations of the vertices of a graph[C]∥Theory of Graphs, International Symposium.New York: Gordon and Breach, 1967: 349-355．

[3] RINGEL G．Problem 25 in theory of graphs and its applications[C]∥FIEDLER M．Proceeding of the 4th international symposium smolenice．Prague: Czech Academy of Science, 1963: 162-167．

[4] 程世輝, 高景麗.樹的等價(jià)定義及其證明[J]. 河南教育學(xué)院學(xué)報(bào)(自然科學(xué)版), 2003, 12(2):65.

[5] 田有先.關(guān)于樹圖的四個(gè)等價(jià)概念[J].達(dá)縣師范?？茖W(xué)校學(xué)報(bào)(自然科學(xué)版), 1999, 9(2):23.

[6] 呂雪征.直徑為四的優(yōu)美樹[J]. 華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2000, 34(2):144-149.

[7] 羅強(qiáng), 宋朝紅.最優(yōu)樹的若干問題[J].華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 1997, 31(2):145-147.

[8] LI S C, MAO J Z, FENG Y Q. The weakly graceful tree with application [J].華中師范大大學(xué)學(xué)報(bào) (自然科學(xué)版), 1998, 32(4):269-272.

[9] HARARY F. Graph theory[M].New York:Addison-Wesley, 1969.

[10] 郝玲.關(guān)于樹的等價(jià)定義的證明[J]. 承德民族師專學(xué)報(bào), 2004, 24(2):14.

[11] YAO B, ZHANG Z F, WANG J F. Some results on spanning trees[J]. Acta Mathematicae Applicatae Sinica: English Series, 2010, 26(5).607-616.

[12] BONDY J A, MURTY U S R. Graph theory with applications[M].New York:The MaCmillan Press Ltd, 1976.

〔責(zé)任編輯宋軼文〕

On equivalent definitions of trees

WANG Xiaomin, ZHAO Xiyang, YAO Bing*

(College of Mathematics and Statistics, Northwest Normal University,Lanzhou 730070, Gansu, China)

Abstract:15 proposition of trees that are equivalent to each other are obtained to deeply understand trees and dig more properties of trees in order to provide useful bases for network study. It is shown that simple and new proofs for the equivalencies of theses 15 propositions.

Keywords:tree; spanning tree; cycle; path; degree.

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)志碼：A

*通信作者：姚兵, 男,教授。 E-mail: yybb918@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61163054, 61163037, 61363060)

收稿日期：2015-06-16

doi:10.15983/j.cnki.jsnu.2016.02.123

文章編號(hào)：1672-4291(2016)02-0011-04

第一作者： 王曉敏, 女,碩士研究生, 研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)。E-mail: 704944897@qq.com