關于仙人掌圖的等價命題

孫 慧，姚 兵,2

(1.西北師范大學 數學與統計學院, 甘肅 蘭州 730070；2.蘭州交通大學 電子與信息工程學院，甘肅 蘭州 730070)

圖論中的圖可根據不同的依據分為不同的圖類。 比如, 根據圖是否有向, 可以分為有向圖和無向圖; 根據圖是否有環和重邊, 可以分為簡單圖和非簡單圖; 根據圖是否含圈, 可以分為無圈圖和非無圈圖; 根據圖是否連通, 可以分為連通圖和非連通圖等等。 已知, 圖論學科里的樹在復雜網絡研究中占有極其重要的地位, 樹的性質、結構、特點已經被許多的學者深入研究過[1-6]。 例如:任何一顆對蝦樹都有一個奇優美標號和奇優雅標號[7-8]。 但是除樹以外, 圖論中其余的圖是否也有優秀的結論呢? 將復雜轉化為簡單, 從未知到已知, 是科學研究的主要思想方法之一。 已知, 網絡模型中的生成樹與網絡的拓撲結構有著緊密的聯系[9-10]。 仙人掌圖被用于建立由環形局域網構成的復雜網絡的模型, 刻畫這類網絡的拓撲結構對網絡的信息傳輸和安全起著重要的作用。因此, 許多學者都把仙人掌圖作為研究對象[11-16]。

1 定 義

在文獻[11]中, 王曉敏等人給出了樹的若干等價命題。 本文給出仙人掌圖的15種等價命題及其證明。 文中所考慮的圖均為有限、無向、簡單圖。 一個圖稱為仙人掌圖, 也叫樹形圖, 是指它的任何2個圈最多有一個公共頂點。 換句話說, 該圖的每個塊要么是圈, 要么是完全圖K2。 為了給出仙人掌圖的等價命題, 必須先將仙人掌圖泛化成一棵樹。 反過來, 也可以將任何一棵正常的樹轉化成仙人掌圖, 從而給出仙人掌圖的構造及其拓撲性質, 為這種模型新描述的網絡提供了可靠、準確的數學方法。 下面給出泛化方法和新概念。 泛化是指將仙人掌圖轉化為泛樹的過程, 細節如下。

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

圖1 一個泛化三角頂點Fig.1 A pan-triangular vertex

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

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

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

圖3 一個泛化方頂點和四個三角頂點Fig.3 A pan-square vertex and four pan-triangular vertexs

本文在此規定: 因為三角頂點和方頂點都是仙人掌圖泛化后得到的, 所以將三角頂點、方頂點和正常頂點統稱為泛頂點, 其中三角頂點、方頂點也稱為泛化點。 泛化邊和正常邊統稱為泛邊。

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

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

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

圖4 泛樹Fig.4 Pan-trees

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

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

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

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

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

2 等價命題和證明

在無特殊說明的情況下, 以下說到的頂點是上一節定義的三種頂點的一種; 說到的邊可能是正常邊, 也可能是泛化邊。沒有說到的符號及術語均采用圖論的標準。

定理1設圖G是非平凡簡單圖，H=Ptree是G的泛化圖, 則下面的命題兩兩相互等價:

1)H是泛樹。

2) 對p個頂點的連通泛圖H實施一系列P(e+,e-)-運算后, 總可以得到一條p個頂點的泛路。

3)H的任意一對頂點由唯一的一條泛路連接。

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

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

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

7)H無泛化圈, 且 |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的每個泛度不為1的泛頂點都是H的泛割點, 且 |E(H)|=|V(H)|-1。

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

14) 當m≥ 3時, 連通圖H不是仙完全圖Km*, 且對圖H的任何2個不相鄰的頂點u和v添加邊uv, 則圖H+uv含有唯一的泛化圈。

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

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

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

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

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

5) →6): 可以用數學歸納法證明。 當|V(H)|=2時, 因為一條邊僅能連2個分支H1和H2, 立得 |V(H1)|=|V(H2)|=1, 所以余圖H-e不連通, 從而算出|E(H)|=1=2-1=|V(H1)|+|V(H2)|-1=|V(H)|-1。 假設當|V(H)|=k時, 命題6)成立。 現證|V(H)|=k+1時的情形。 由于對任意一條邊e∈E(H), 命題5)保證圖H-e不連通, 且H-e只有2個分支L1和L2。 由數學歸納法, 知|E(Li)|=|V(Li)|-1,i=1,2。 故得

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

正是因為刪去泛化圈上的邊e后, 不能使圖H是圖H-e不連通的最小連通圖, 故H無泛化圈, 命題6)得證。

6) →7): 假設圖H含有泛化圈, 并且刪去泛化圈中的任意邊e后, 得到的圖H-e仍然連通, 如果H-e不含泛化圈C, 則停止; 反之, 則繼續刪除泛化圈C上的一條邊, 像這樣進行下去, 直到所得到的圖不含泛化圈為止。 設全體刪除的泛邊集合為E1。 上述過程保證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不含泛化圈。 用數學歸納法易證得 |E(H)|=|V(H)|-1。

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

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

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

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

即

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

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

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

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

這與命題9)矛盾, 也就是說圖H連通。又因為

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

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

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

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

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

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

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

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

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

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

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

證明用數學歸納法證。 當k=0時, 即u和v之間無三角頂點, 則u和v之間由唯一的路連接。

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

假設k=i-1時, 即u和v之間有i-1個三角頂點,u和v之間由2i-1條不同的路連接。

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

3 總結與問題

在類似仙人掌圖的研究問題中, 今后可以運用本文的泛化方法。 顯然, 本文為圖論學科提供了一個新的圖類, 同時, 也為網絡研究提供了新的網絡模型。 反過來看, 可以將一棵樹的若干個頂點改為本文的泛化頂點, 將一些邊改為泛邊, 就得到一棵泛樹。 然后, 將這棵泛樹反轉出一個仙人掌圖。 本文的研究表明, 仙人掌圖可通過泛化后研究其拓撲結構。 那么, 其他復雜的圖如何進行泛化達到簡化呢?這是今后要研究的課題。 需要指出, 本文的泛化圖不是圖論中的超圖。 從應用的角度上看, 構造優秀的網絡模型對理解、認識、研究現實世界的諸多網絡有著重要而積極的作用。