孫 慧，姚 兵,2

(1.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070；2.蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

圖論中的圖可根據(jù)不同的依據(jù)分為不同的圖類。 比如, 根據(jù)圖是否有向, 可以分為有向圖和無(wú)向圖; 根據(jù)圖是否有環(huán)和重邊, 可以分為簡(jiǎn)單圖和非簡(jiǎn)單圖; 根據(jù)圖是否含圈, 可以分為無(wú)圈圖和非無(wú)圈圖; 根據(jù)圖是否連通, 可以分為連通圖和非連通圖等等。 已知, 圖論學(xué)科里的樹(shù)在復(fù)雜網(wǎng)絡(luò)研究中占有極其重要的地位, 樹(shù)的性質(zhì)、結(jié)構(gòu)、特點(diǎn)已經(jīng)被許多的學(xué)者深入研究過(guò)[1-6]。 例如:任何一顆對(duì)蝦樹(shù)都有一個(gè)奇優(yōu)美標(biāo)號(hào)和奇優(yōu)雅標(biāo)號(hào)[7-8]。 但是除樹(shù)以外, 圖論中其余的圖是否也有優(yōu)秀的結(jié)論呢? 將復(fù)雜轉(zhuǎn)化為簡(jiǎn)單, 從未知到已知, 是科學(xué)研究的主要思想方法之一。 已知, 網(wǎng)絡(luò)模型中的生成樹(shù)與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有著緊密的聯(lián)系[9-10]。 仙人掌圖被用于建立由環(huán)形局域網(wǎng)構(gòu)成的復(fù)雜網(wǎng)絡(luò)的模型, 刻畫(huà)這類網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)網(wǎng)絡(luò)的信息傳輸和安全起著重要的作用。因此, 許多學(xué)者都把仙人掌圖作為研究對(duì)象[11-16]。

1 定 義

在文獻(xiàn)[11]中, 王曉敏等人給出了樹(shù)的若干等價(jià)命題。 本文給出仙人掌圖的15種等價(jià)命題及其證明。 文中所考慮的圖均為有限、無(wú)向、簡(jiǎn)單圖。 一個(gè)圖稱為仙人掌圖, 也叫樹(shù)形圖, 是指它的任何2個(gè)圈最多有一個(gè)公共頂點(diǎn)。 換句話說(shuō), 該圖的每個(gè)塊要么是圈, 要么是完全圖K2。 為了給出仙人掌圖的等價(jià)命題, 必須先將仙人掌圖泛化成一棵樹(shù)。 反過(guò)來(lái), 也可以將任何一棵正常的樹(shù)轉(zhuǎn)化成仙人掌圖, 從而給出仙人掌圖的構(gòu)造及其拓?fù)湫再|(zhì), 為這種模型新描述的網(wǎng)絡(luò)提供了可靠、準(zhǔn)確的數(shù)學(xué)方法。 下面給出泛化方法和新概念。 泛化是指將仙人掌圖轉(zhuǎn)化為泛樹(shù)的過(guò)程, 細(xì)節(jié)如下。

1)對(duì)于仙人掌圖的任何一個(gè)有k個(gè)頂點(diǎn)和k條邊的圈, 去掉這k個(gè)頂點(diǎn),k條邊, 并用一個(gè)特殊的頂點(diǎn)——三角頂點(diǎn)(用一個(gè)小三角表示, 記為upc, 其中u是頂點(diǎn)，pc是pan-circle的縮寫(xiě))來(lái)代替這個(gè)圈。 如圖1所示。

圖1 一個(gè)泛化三角頂點(diǎn)Fig.1 A pan-triangular vertex

對(duì)仙人掌圖中只有兩個(gè)由一個(gè)公共頂點(diǎn)連接的圈, 除了要將這2個(gè)圈泛化為2個(gè)三角頂點(diǎn)外, 還要將公共頂點(diǎn)用一條特殊的邊——泛化邊(用兩條平行線段表示, 記為ep, 其中e是表示邊,p是pan的縮寫(xiě))來(lái)表示, 見(jiàn)圖2。

圖2 一條泛化邊Fig.2 A pan-edge

當(dāng)仙人掌圖中有3個(gè)及3個(gè)以上的k個(gè)圈由一個(gè)公共頂點(diǎn)連通時(shí), 除了要將k個(gè)圈泛化為k個(gè)三角頂點(diǎn), 還要將這個(gè)公共頂點(diǎn)用一個(gè)特殊的頂點(diǎn)——方頂點(diǎn)(用一個(gè)小正方形表示, 記為ups, 其中u是表示頂點(diǎn),ps是pan-square的縮寫(xiě))來(lái)表示, 再將表示k個(gè)圈的k個(gè)三角頂點(diǎn)用泛化邊與方頂點(diǎn)分別相連。 圖3給出一個(gè)例子。

圖3 一個(gè)泛化方頂點(diǎn)和四個(gè)三角頂點(diǎn)Fig.3 A pan-square vertex and four pan-triangular vertexs

本文在此規(guī)定: 因?yàn)槿琼旤c(diǎn)和方頂點(diǎn)都是仙人掌圖泛化后得到的, 所以將三角頂點(diǎn)、方頂點(diǎn)和正常頂點(diǎn)統(tǒng)稱為泛頂點(diǎn), 其中三角頂點(diǎn)、方頂點(diǎn)也稱為泛化點(diǎn)。 泛化邊和正常邊統(tǒng)稱為泛邊。

2)泛樹(shù)是指仙人掌圖通過(guò)泛化后得到的泛化圖, 記為Ptree。 泛樹(shù)一般有3種頂點(diǎn): 正常頂點(diǎn), 三角頂點(diǎn), 方頂點(diǎn); 泛樹(shù)包含2種邊: 正常邊, 泛化邊。 見(jiàn)圖4中的例子。 關(guān)于泛樹(shù)的基本參數(shù)有:

泛樹(shù)的頂點(diǎn)集Ptree=Vf∪Vp, 其中Vf表示正常的頂點(diǎn)的集合;Vp表示泛化點(diǎn)的集合。 泛樹(shù)的邊集E(Ptree)=Ef∪Ep, 其中Ef表示正常的邊的集合;Ep表示泛化邊的集合。 根據(jù)泛化的過(guò)程, 可計(jì)算在泛化過(guò)程中去掉的頂點(diǎn)個(gè)數(shù)M和邊數(shù)N: 泛樹(shù)的頂點(diǎn)個(gè)數(shù)|V(Ptree)|=|V(G)|-M; 泛樹(shù)的邊數(shù)|E(Ptree)|=|E(G)|-N, 其中G是泛化之前的仙人掌圖。

泛度是指泛樹(shù)中與某頂點(diǎn)v(這里的v可能是正常的頂點(diǎn), 也可能是泛化點(diǎn))關(guān)聯(lián)的邊(這里的邊可能有正常邊, 也可能有泛化邊)的數(shù)目, 例如, 泛頂點(diǎn)v與s條正常邊,t條泛邊關(guān)聯(lián), 則v的泛度為deg(v)=s+t。δ(Ptree) 和Δ(Ptree) 分別表示最小泛度和最大泛度。泛葉子是指泛度為1的泛頂點(diǎn)。 若v是正常的頂點(diǎn)且與之關(guān)聯(lián)的邊全是正常的邊, 則v的泛度與圖論中頂點(diǎn)度的定義完全相同。符號(hào)nd(G) 表示圖G中泛度為d的泛頂點(diǎn)的個(gè)數(shù)，見(jiàn)圖4。

圖4 泛樹(shù)Fig.4 Pan-trees

3)泛化圈是指含泛化點(diǎn)和泛化邊的圈。不含泛化點(diǎn)和泛化邊的泛化圈, 就是圖論中的圈; 泛路是指含泛化點(diǎn)和泛化邊的路。不包含泛化點(diǎn)和泛化邊的泛路, 就是圖論中的路。

4)泛縮邊圖G·e是刪去G的泛邊e, 重合e的2的個(gè)端點(diǎn)新得到的圖, 其中, 若泛邊e的2個(gè)端點(diǎn)都是正常頂點(diǎn), 則將泛邊e的2個(gè)端點(diǎn)重合為正常頂點(diǎn); 若泛邊e的2個(gè)端點(diǎn)都是三角頂點(diǎn), 則將泛邊e的2個(gè)端點(diǎn)重合為三角頂點(diǎn); 若泛邊e的2個(gè)端點(diǎn)一個(gè)是三角頂點(diǎn), 一個(gè)是方頂點(diǎn), 則將泛邊e的2個(gè)端點(diǎn)統(tǒng)一重合為方頂點(diǎn); 若泛邊e的2個(gè)端點(diǎn)一個(gè)是泛化點(diǎn), 一個(gè)是正常頂點(diǎn), 則將泛邊e的2個(gè)端點(diǎn)統(tǒng)一重合為泛化點(diǎn)。

5)給圖G的兩個(gè)不相鄰的泛頂點(diǎn)u和v之間添加泛邊。 在實(shí)際操作過(guò)程中, 具體添加哪種邊視具體情況而定, 若u和v中至少有一個(gè)是正常頂點(diǎn), 則添加一條正常邊; 若u和v都是泛化點(diǎn), 則添加一條泛化邊uv=e+, 再刪除G的一條不是e+的泛邊e-, 稱這種運(yùn)算為P(e+,e-)-運(yùn)算, 也說(shuō)對(duì)圖G實(shí)施了一次P(e+,e-)-運(yùn)算。

6)泛化圖G的泛割邊是指使得分支數(shù)目ω(G-e)>ω(G)的泛邊e; 泛化圖G的泛割點(diǎn)v使得分支數(shù)目ω(G-v)>ω(G)。

7) 生成泛樹(shù)是指泛化圖的生成樹(shù)。設(shè)泛化仙人掌圖得到的泛樹(shù)有n個(gè)泛頂點(diǎn), 且除泛頂點(diǎn)和泛邊這樣的符號(hào)不同外, 恰好形似n個(gè)頂點(diǎn)的完全圖, 則稱這樣的泛樹(shù)為仙完全圖。 記為Kn*。 只有一個(gè)泛頂點(diǎn)的仙完全圖記為K1*。

2 等價(jià)命題和證明

在無(wú)特殊說(shuō)明的情況下, 以下說(shuō)到的頂點(diǎn)是上一節(jié)定義的三種頂點(diǎn)的一種; 說(shuō)到的邊可能是正常邊, 也可能是泛化邊。沒(méi)有說(shuō)到的符號(hào)及術(shù)語(yǔ)均采用圖論的標(biāo)準(zhǔn)。

定理1設(shè)圖G是非平凡簡(jiǎn)單圖，H=Ptree是G的泛化圖, 則下面的命題兩兩相互等價(jià):

1)H是泛樹(shù)。

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

3)H的任意一對(duì)頂點(diǎn)由唯一的一條泛路連接。

4)H恰有|V(H)|·[|V(H)|-1]/2條泛路, 且任意一對(duì)頂點(diǎn)有泛路連通。

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

6)H連通, 且 |E(H)|=|V(H)|-1。

7)H無(wú)泛化圈, 且 |E(H)|=|V(H)|-1。

8)H連通,δ(H) ≥ 1,Σv∈V(H)deg (v)=2[|V(H)|-1]。

9)H滿足連通且n1(H)=2+Σ3≤d(d-2)nd(H)。

10) 令連通泛化圖H=H0, 則存在k≥ 1 ，使得圖Hi=Ptreei(i=1,2…，k)至少含有Δ(Hi)片泛葉子, 刪去圖Hi的Δ(Hi)片泛葉子得到圖Hi+1, 且Hk=K1*。

11) 圖H的每條泛邊都是圖H的泛割邊, 且 |E(H)|=|V(H)|-1。

12) 圖H的每個(gè)泛度不為1的泛頂點(diǎn)都是H的泛割點(diǎn), 且 |E(H)|=|V(H)|-1。

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

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

15) 設(shè)H≠K1*∪K3*或者H≠K2*∪K3*, 且 |E(H)|=|V(H)|-1, 對(duì)于圖H中任何兩個(gè)不相鄰的頂點(diǎn)u和v添加邊uv, 則圖H+uv含有唯一的泛化圈。

證明本證明用 “i) →j)” 表示根據(jù)命題i)來(lái)推證命題j), 其中1≤i,j≤ 15且i≠j。

1) →2): 因H是泛樹(shù), 故圖H無(wú)泛化圈。 若H為泛路, 證明完成。 若圖H不是泛路, 則圖H的泛葉子數(shù)目n1(H) ≥ 3, 其中有2片泛葉子x,y在圖H的一條泛路P=xu1u2…uky上, 另外一片泛葉子w與圖H的頂點(diǎn)w′ 相鄰。 對(duì)圖H實(shí)施一次P(e+,e-)-運(yùn)算, 其中e+=yw,e-=ww′, 得到新圖H1的一條泛路P+yw, 且有一度頂點(diǎn)的個(gè)數(shù)n1(H) ≥n1(H1)。 像這樣進(jìn)行下去, 一定存在k, 使得圖Hk是一條泛路。 命題2)得證。

2) →3): 因?yàn)閳DH是連通圖的, 所以H的任意一對(duì)頂點(diǎn)u和v之間至少由一條泛路P(u,v)連接。 假設(shè)連接頂點(diǎn)u和v之間的泛路不唯一, 存在不同于泛路P(u,v)的另外一條泛路Q(u,v), 這2條泛路必將導(dǎo)致圖H的一個(gè)泛化圈, 那么對(duì)圖H實(shí)施多少次P(e+,e-)-運(yùn)算都不能減少泛化圈的數(shù)目, 從而無(wú)法得到一條泛路, 這矛盾于命題2)。 換句話說(shuō), 圖H的任意一對(duì)頂點(diǎn)u和v之間有且僅有一條泛路P(u,v)。

4) →5): 假設(shè)命題5)不成立, 則存在圖H的一條邊e, 使得刪去邊e的余圖H-e是連通的, 可知圖H-e至少有|V(H-e)|·[|V(H-e)|-1]/2條不同的泛路。 因?yàn)閨V(H)|=|V(H-e)|, 說(shuō)明圖H的頂點(diǎn)之間至少存在1+|V(H)|·[|V(H)|-1]/2條不同的泛路, 這與命題4)矛盾, 命題5)得證。

5) →6): 可以用數(shù)學(xué)歸納法證明。 當(dāng)|V(H)|=2時(shí), 因?yàn)橐粭l邊僅能連2個(gè)分支H1和H2, 立得 |V(H1)|=|V(H2)|=1, 所以余圖H-e不連通, 從而算出|E(H)|=1=2-1=|V(H1)|+|V(H2)|-1=|V(H)|-1。 假設(shè)當(dāng)|V(H)|=k時(shí), 命題6)成立。 現(xiàn)證|V(H)|=k+1時(shí)的情形。 由于對(duì)任意一條邊e∈E(H), 命題5)保證圖H-e不連通, 且H-e只有2個(gè)分支L1和L2。 由數(shù)學(xué)歸納法, 知|E(Li)|=|V(Li)|-1,i=1,2。 故得

|E(H)|=|E(L1)|+|E(L2)|+1=|V(L1)|+|V(L2)|-2+1=|V(H)|-1。

正是因?yàn)閯h去泛化圈上的邊e后, 不能使圖H是圖H-e不連通的最小連通圖, 故H無(wú)泛化圈, 命題6)得證。

6) →7): 假設(shè)圖H含有泛化圈, 并且刪去泛化圈中的任意邊e后, 得到的圖H-e仍然連通, 如果H-e不含泛化圈C, 則停止; 反之, 則繼續(xù)刪除泛化圈C上的一條邊, 像這樣進(jìn)行下去, 直到所得到的圖不含泛化圈為止。 設(shè)全體刪除的泛邊集合為E1。 上述過(guò)程保證H-E1是不含圈的連通圖, 并有等式|E(H-E1)|=|V(H-E1)|-1成立。 注意到|V(H)|=|V(H-E1)|, 那么

|E(H)|=|E(H-E1)|+|E1|=

|V(H-E1)|-1+|E1|=

|V(H)|-1+|E1|≥ |V(H)|,

這與命題6)矛盾。 因此,H不含泛化圈。 用數(shù)學(xué)歸納法易證得 |E(H)|=|V(H)|-1。

7) →8): 假設(shè)圖H有m個(gè)分支H1,H2,…,Hm, 其中m≥ 2。 由命題7), 得每個(gè)分支Hi都滿足等式 |E(Hi)|=|V(Hi)|-1(i=1,2,…,m)。 又因?yàn)閳DH的邊數(shù)目, 有下面的等式

成立。 再結(jié)合命題7), 得到m=1, 這與m≥ 2矛盾。 從而圖H是連通的。 需注意H≠K2*∪K3*, 又因?yàn)椤苬∈V(H)deg (v)=2|E(H)|, 立得命題8)。

8) →9): 假定圖H不連通。 一般地,H有m個(gè)分支H1,H2,…,Hm, 其中m≥ 2。 由命題 (8) 知, 每個(gè)分支Hi滿足

(i=1,2,…,m),

即

由命題8)保證等式∑v∈V(H)deg (v)=

2[|V(H)|-1]成立, 從而解出m=1。 因此, 假設(shè)圖H不連通是錯(cuò)誤的。 容易算出

以及|V(H)|=n1(H)+n2(H)+∑3≤dnd(H), 解得n1(H)=2+∑3≤d(d-2)nd(H)。

9) →10): 假設(shè)圖H有m個(gè)分支H1,H2,…,Hm, 其中m≥ 2。 由命題9), 得每個(gè)分支Hi滿足等式n1(H)=2+∑3≤d(d-2)nd(H) (i=1,2,…,m), 并得到

這與命題9)矛盾, 也就是說(shuō)圖H連通。又因?yàn)?/p>

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

且Δ(H)>0, 這意味著圖H至少有Δ(H)片泛葉子, 則可以刪去圖H的這Δ(H)片泛葉子, 得到一個(gè)連通圖H1; 又因H1連通, 命題9)保證H1至少有Δ(H1)>0片泛葉子, 刪去它的Δ(H1)片泛葉子后, 得到圖H2; 如此進(jìn)行下去, 由于圖H的頂點(diǎn)數(shù)目有限, 依次可得圖H0,H1, …,Hk, 其中H0=H和Hk=K1*, 且每個(gè)圖Hi至少有Δ(Hi)片泛葉子, 刪去圖Hi的Δ(Hi)片泛葉子就得到Hi+1(i=0, 1,…,k-1)。

10) →11): 若圖H有一條非(泛)割邊xy, 那么邊xy一定在圖H的一個(gè)泛化圈C上。 由于泛化圈C上的頂點(diǎn)不是泛葉子, 也就是說(shuō), 依次刪去泛葉子最后所得到的圖Hk一定含泛化圈C, 即Hk≠K1*, 這與命題10)矛盾。 若圖H不連通, 設(shè)它有分支H1,H2,…,Hm(m≥ 2)。 由命題10), 得到每個(gè)分支Hi所對(duì)應(yīng)的圖Hi,1,Hi,2, …,Hi,mi, 其中Hi,mi=K1*, 刪去圖Hi,j的Δ(Hi,j)片泛葉子可得圖Hi,j+1(j=0, 1,…,mi-1)。 當(dāng)m≥ 2時(shí), 像上面那樣刪去泛葉子, 最后得到m個(gè)K1*, 與命題10)矛盾, 只有圖H不含泛化圈且連通, 這說(shuō)明|E(H)|=|V(H)|-1。

11) →12): 假設(shè)圖H有一個(gè)泛度不為1的頂點(diǎn)w, 使得H-w的分支數(shù)目ω(H-w)與圖H的分支數(shù)目ω(H)相等, 也就是說(shuō), 與頂點(diǎn)w相鄰的每一個(gè)頂點(diǎn)都不是泛葉子。 任取頂點(diǎn)w的鄰點(diǎn)z, 刪去邊wz所得的余圖H-wz的分支數(shù)目與圖H的分支數(shù)目相等, 即邊wz不是圖H的泛割邊, 這與命題 11)矛盾, 由此可知圖H的每一個(gè)泛度大于1的頂點(diǎn)均為圖H的泛割點(diǎn)。 由命題11)的結(jié)論|E(H)|=|V(H)|-1, 命題12)得證。

12) →13): 設(shè)e=uv是圖H的任意一條邊。H·e是收縮邊e=uv后得到泛縮邊圖, 記頂點(diǎn)u與頂點(diǎn)v重合后的頂點(diǎn)為w*。 命題12)要求圖H無(wú)泛化圈, 并滿足等式|E(H)|=|V(H)|-1。 由7) →8), 得到圖H和泛縮邊圖H·e都有各自的生成泛樹(shù)。 若圖H的生成泛樹(shù)的個(gè)數(shù)與泛縮邊圖H·e的生成泛樹(shù)的個(gè)數(shù)不相等, 那么圖H含有不通過(guò)邊e的生成泛樹(shù), 這意味著, 圖H有一個(gè)泛化圈含邊e, 對(duì)應(yīng)地, 可以在泛縮邊圖H·e里找到一個(gè)泛化圈包含頂點(diǎn)w*。 從而證明了|E(H)| ≥ |V(H)|, 這與命題12)沖突。

13) →14): 根據(jù)命題13), 圖H有生成泛樹(shù), 也就是說(shuō), 圖H連通。 圖H的生成泛樹(shù)的個(gè)數(shù)與泛縮邊圖H·e的生成泛樹(shù)的個(gè)數(shù)相等, 從而保證圖H不含泛化圈。 由圖H不是仙完全圖Km*(m≥ 3), 又因圖H至少包含一對(duì)不相鄰的頂點(diǎn)u和v, 則可給圖H添加邊uv, 得到圖H+uv。 若圖H+uv包含2個(gè)泛化圈C和C′, 必須是泛化圈C和C′有且僅有公共邊uv。 刪去邊uv, 泛化圈C和C′合并成圖H的一個(gè)泛化圈, 這矛盾于圖H不含泛化圈, 也矛盾于命題13)。 這就證得命題14)。

14) →15): 當(dāng)H只有2個(gè)頂點(diǎn)時(shí), 是平凡情形, 故設(shè) |V(H)| ≥ 3。 由命題 (14) 的條件, 知圖H連通, 且不是仙完全圖Km*(m≥ 3)。 按照命題15)的條件, 圖H滿足|E(H)|=|V(H)|-1 ≠ |V(H)|·[|V(H)|-1]/2, 這也說(shuō)明圖H不是仙完全圖。 因?yàn)镠≠K1*∪K3*或者H≠K2*∪K3*, 按照命題14), 給連通圖H的2個(gè)不相鄰的頂點(diǎn)u和v添加邊uv, 使得圖H+uv僅含唯一的泛化圈, 命題15)得證。

15) →1): 假設(shè)圖H不連通, 也就是說(shuō), 圖H至少有2個(gè)分支H1和H2。 當(dāng)|V(H1)|+|V(H2)|=4時(shí), 命題15)的條件使得H≠K1*∪K3*, 故對(duì)于圖H的2個(gè)不相鄰的頂點(diǎn)u和v, 連接u和v所得到的加邊圖H+uv不含泛化圈, 這抵觸于命題15)。 當(dāng)|V(H1)|=2和|V(H2)|=3時(shí), 命題15)的條件使得H≠K2*∪K3*, 故對(duì)于圖H的2個(gè)不相鄰的頂點(diǎn)u和v, 連接u和v所得到的加邊圖H+uv不含泛化圈, 這與命題15)沖突。 當(dāng)|V(H1)|=1和|V(H2)|=4時(shí), 命題15)的條件|E(H)|=|V(H)|-1說(shuō)明H2等于4個(gè)頂點(diǎn)的泛化圈, 對(duì)于這個(gè)泛化圈上的2個(gè)不相鄰的頂點(diǎn)x和y進(jìn)行連邊xy, 則圖H+xy含2個(gè)泛化圈, 矛盾于命題15)。 當(dāng) |V(H1)|+

|V(H2)| ≥ 6時(shí), 若|V(H1)| ≤ 2和|V(H2)| ≥ 4, 易得出矛盾; 若|V(H1)| ≥ 3和|V(H2)| ≥ 3, 命題15)的條件|E(H)|=|V(H)|-1約束分支H1和H2中至多一個(gè)有泛化圈, 不妨設(shè)H2含泛化圈。 然而, 對(duì)于分支H1的2個(gè)不相鄰的頂點(diǎn)s和t, 用邊連接s和t, 那么圖H+st至少含2個(gè)泛化圈, 矛盾于命題15)。 當(dāng)圖H有3個(gè)以上的分支時(shí), 令H1和H2是最大分支或次最大分支, 其余論證與上面的證明類同, 不再贅述。 注意到, 當(dāng)圖H有3個(gè)以上的分支時(shí), 分別取前面2個(gè)分支H1和H2的頂點(diǎn)u和頂點(diǎn)v, 用新邊連接這2個(gè)頂點(diǎn), 所得到的加邊圖H+uv就不含唯一泛化圈, 又矛盾于命題15)。 這說(shuō)明, 假設(shè)圖H不連通是錯(cuò)誤的。 圖H的連通性與命題15)結(jié)合, 即可推證出命題1)。

對(duì)1≤i,j≤ 15且i≠j, 以上過(guò)程證明了命題i)成立的充要條件是命題j)成立。 本定理得證。

推論1設(shè)圖G是非平凡簡(jiǎn)單圖,H=Ptree是G的泛化圖。 若泛化圖H的2個(gè)正常頂點(diǎn)u和v之間的路上有k個(gè)三角頂點(diǎn), 則在圖G中, 頂點(diǎn)u和v由2k條不同的路連接。

證明用數(shù)學(xué)歸納法證。 當(dāng)k=0時(shí), 即u和v之間無(wú)三角頂點(diǎn), 則u和v之間由唯一的路連接。

當(dāng)k=1時(shí), 即u和v之間有一個(gè)三角頂點(diǎn), 由于三角頂點(diǎn)在仙人掌圖G中是一個(gè)圈, 顯然一個(gè)圈中度大于等于3的頂點(diǎn)之間路僅有兩條, 則u和v之間由2條不同的路連接。

假設(shè)k=i-1時(shí), 即u和v之間有i-1個(gè)三角頂點(diǎn),u和v之間由2i-1條不同的路連接。

則當(dāng)k=i時(shí), 即u和v之間有i個(gè)三角頂點(diǎn), 有歸納假設(shè)知, 若先將第i個(gè)三角頂點(diǎn)當(dāng)成正常頂點(diǎn), 前i-1個(gè)三角頂點(diǎn), 使得u和v之間由2i-1條不同的路連接, 而加入第i個(gè)三角頂點(diǎn)的事件, 它與前i-1個(gè)三角頂點(diǎn)之間是相互獨(dú)立事件, 因此u和v之間由2i條不同的路連接。 依據(jù)數(shù)學(xué)歸納法, 推論得證。

3 總結(jié)與問(wèn)題

在類似仙人掌圖的研究問(wèn)題中, 今后可以運(yùn)用本文的泛化方法。 顯然, 本文為圖論學(xué)科提供了一個(gè)新的圖類, 同時(shí), 也為網(wǎng)絡(luò)研究提供了新的網(wǎng)絡(luò)模型。 反過(guò)來(lái)看, 可以將一棵樹(shù)的若干個(gè)頂點(diǎn)改為本文的泛化頂點(diǎn), 將一些邊改為泛邊, 就得到一棵泛樹(shù)。 然后, 將這棵泛樹(shù)反轉(zhuǎn)出一個(gè)仙人掌圖。 本文的研究表明, 仙人掌圖可通過(guò)泛化后研究其拓?fù)浣Y(jié)構(gòu)。 那么, 其他復(fù)雜的圖如何進(jìn)行泛化達(dá)到簡(jiǎn)化呢?這是今后要研究的課題。 需要指出, 本文的泛化圖不是圖論中的超圖。 從應(yīng)用的角度上看, 構(gòu)造優(yōu)秀的網(wǎng)絡(luò)模型對(duì)理解、認(rèn)識(shí)、研究現(xiàn)實(shí)世界的諸多網(wǎng)絡(luò)有著重要而積極的作用。