復雜網絡中k-單圈圖的若干性質

姚 明，蘇 靜，姚 兵

(1.蘭州石化職業技術學院信息處理與控制工程學院，甘肅 蘭州 730060；2.北京大學信息科學技術學院，北京 100871；3.北京大學高可信軟件技術教育部重點實驗室，北京 100871；4.西北師范大學數學與統計學院，甘肅 蘭州 730070)

1 預備知識

在當今的網絡世界里，無標度網絡幾乎處處可見，如演員網絡、語言網絡、萬維網等[1].Genio等[2]已經證明所有無標度網絡都是稀疏的.因此，通過構造方法可以得到對于任意實數M>0，存在一個無標度圖N(t)和一個數β≥M，使得|E(N(t))|～β·|N(t)|.本文研究k-單圈圖變量的動機來自許多仍待解決的猜想[3]，圖的許多來自Graffiti猜想[4]的不變量，以及實際應用中需要大量的優質網絡模型.

設k為非負整數，G是連通圖.如果G中恰好包含k個圈，且這k個圈的任何兩個圈之間沒有公共邊，那么稱圖G為k-單圈圖.特別地，樹是0-單圈圖.k-單圈圖也叫仙人掌圖，仙人掌圖的每個塊是一個圈或是一條路，或者說，仙人掌圖的每條邊都包含在至多一個圈中.如果k-單圈圖G含有不在圈上的邊，則G不是歐拉圖.

本文考慮沒有自環和重邊的有限無向圖.文中未定義的術語均來自文獻[5].對整數n>m≥0，約定[m，n]={m，m+1，…，n}.在圖G中與頂點u相鄰的點的集合記為N(u)，因此，頂點u的度數degG(u)等于基數|N(u)|.稱N(u)和N[u]=N(u)∪{u}分別為頂點u的鄰集和閉鄰集.類似地，一個頂點子集S?V(G)的鄰集N(S)是集合V(G)的子集，使得每一個x∈N(S)頂點都與S中的一個頂點相鄰.度數為1的頂點稱為葉子.符號L(G)表示圖G的葉子集，nd(G)表示G中度為d的頂點的數目.特別地，nd(G)=0表示G是一個孤立點或者G中沒有度為d的頂點.

設P=u1u2…um是圖G的一條路.若degG(u1)≥3，degG(um)≥3，且degG(ui)=2(i∈[2，m-1])，則稱P是一條純路.若degG(u1)≥3，degG(um)=1，且degG(ui)=2(i∈[2，m-1])，則P被稱為懸掛路.類似地，如果一個圈G中的|V(C)|-1個頂點在圖G中的度均為2，則稱它為懸掛圈.本文將用到以下三類連通圖的2個引理：

圖1 三類連通圖

上式指明，樹中每一個2度頂點與樹的葉子數量無關.

引理2[6-7]設T是一棵n個頂點的樹，則Diam(T)≤n-n1(T)+1.

定理1 設G是一個含有p個點q條邊的連通圖，其中p≥3，q≥2.那么

(1)

證明如果連通圖G是樹，則它滿足引理1中的公式，且q=p-1，可得到公式(1).設連通圖G含圈，取它的某個圈上的一條邊u1u2，給連通圖G添加2個新頂點v1，v2，將頂點vi分別與頂點ui(i=1，2)用邊連接，然后刪去邊u1u2，得到的圖記為G1，得到圖G1的過程稱為減圈運算.不難看到，圖G1是連通的，它的圈數目比圖G的圈數目少1，且有

n1(G1)=n1(G)+2，nd(G1)=nd(G)(d≥3)，

|V(G1)|=p+2，|E(G1)|=q+1.

若圖G1仍然含有圈，進行上述減圈運算，得到連通圖G2，使得

n1(G2)=n1(G1)+2=n1(G)+4，nd(G2)=nd(G)(d≥3)，

|V(G2)|=|V(G1)|+2=p+4，|E(G2)|=|E(G1)|+1=q+2.

如此進行下去，直到連通圖Gk不再含有圈，即它是樹.注意到

n1(Gk)=n1(G)+2k，nd(Gk)=nd(G)(d≥3)，

|V(Gk)|=p+2k，|E(Gk)|=q+k.

根據引理1的公式得

進一步，有

由于q=p-1+k，結論得證.

根據平面圖的歐拉公式和定理1的公式(1)，可得下面推論：

推論1 設φ(H)是連通平面圖H的面數，則H滿足

(2)

2 主要結論及其證明

k-單圈連通圖G的點路圈圖H為頂點集V(H)中的每一個頂點對應G中的一個圈，或者一條懸掛路，或者一條純路，或一個大割點u(割點u使得不連通圖G-u至少包含3個分支).2個頂點X，Y∈V(H)在點路圈圖H中是相鄰的，如果它們對應的圈X=Cm，Y=Ct(或者路X=Pm，Y=Pt，或一個圈X=Cm和一條路Y=Pt，或一個割點X=u和一個圈Y=Cm，或一個割點X=u和一條路Y=Pt)在G中總有|V(X)∩V(Y)|=1.圖2給出連通圖Gi的點路圈圖Hi(i=1，2，3).

圖2 連通圖Gi的點路圈圖Hi(i=1，2，3)

定理2 設G是一個連通圖，整數k≥0，則：

(ⅰ)G是k-單圈圖的充分必要條件為

(3)

(ⅱ)G是k-單圈圖，當且僅當它的點路圈圖是一棵樹.

證明(ⅰ) 令ni=ni(G)，i=1，2.假設G是一個k-單圈圖，根據k-單圈圖的定義，存在邊uivi(i∈[1，k])，使得G-{uivi|i∈[1，k]}是一棵樹.構造一棵樹：給圖G添加新的頂點xi，yi(i∈[1，k])，分別用邊連接頂點xi與ui，連接頂點yi與vi；然后刪除邊uivi(i∈[1，k])，所得的圖記為H.顯然，H是一棵樹，且有Δ(H)=Δ(G).注意到

|V(H)|=|V(G)|+2k，n1(H)=n1+2k，nd(H)=nd(G)，d∈[2，Δ(T)].

根據引理1，有

(4)

這意味著公式(3)成立.

假設G滿足公式(3)，如果G是樹，使得

因此，有2=2(1-k)≤0，矛盾.假設G包含m≥1個圈，用上面的方法可以構造一棵樹，使得

因此，2(1-m)=2(1-k)，從而m=k.

根據公式(2)和(3)，得到下面的結論：

定理3 設G是一個含有n≥3個頂點的k-單圈圖，φ(G)是圖G的面數，則φ(G)=k+1.

定理4 設G是一個n≥4個頂點的連通k-單圈圖.對d∈[δ(G)，Δ(G)]，nd=nd(G)，則有k=|E(G)|-n+1以及下列性質：

(ⅰ) 2|E(G)|≤3(n-1).

(ⅲ)n≤2(k-1)+2n1+n2.

(ⅳ) 若對d∈[2，s]有nd=0，s≥2，則

sn≤2(k-1)+(s+1)n1+ns+1.

(5)

證明(ⅰ) 因為G的生成樹有n-1條邊，則k=|E(G)|-n+1.三角形是最小的圈，從而有

3k≤|E(G)|=k+(n-1)，

解得

2k≤n-1，2|E(G)|=2(k+(n-1))≤3(n-1).

(ⅱ) 利用定理1證明中的減圈運算以及

由平面圖的性質得

再根據公式(3)，有2(1-k)+(n-n1-n2)≤n1.結論(ⅲ)的界由圈或者圈的每個頂點都有葉子的k-單圈圖而獲得.

(ⅳ) 設對d∈[2，s](s≥2)，有nd=0.使用公式(3)，可以得到

S={(vi，mi，vi+1，1)|i∈[1，k-1]}，

將(s-3)個新頂點與S中的每個頂點連接起來，得到圖H.顯然，

其中d∈[2，s].從而，H是一個k-單圈圖并且滿足不等式(5).

(1) 若n1(G)=0和|V(H*)|=k成立，H*的每個葉子都至少貢獻兩個G中度為2的頂點，因而得n2(G)≥2n1(H*)+n2(H*).更精確地，因為n1(H*)≥2和n2(H*)≥k成立.則有n2(G)≥k+2.