姚 明，蘇 靜，姚 兵

(1.蘭州石化職業(yè)技術(shù)學(xué)院信息處理與控制工程學(xué)院，甘肅 蘭州 730060；2.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京 100871；3.北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871；4.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070)

1 預(yù)備知識(shí)

在當(dāng)今的網(wǎng)絡(luò)世界里，無(wú)標(biāo)度網(wǎng)絡(luò)幾乎處處可見(jiàn)，如演員網(wǎng)絡(luò)、語(yǔ)言網(wǎng)絡(luò)、萬(wàn)維網(wǎng)等[1].Genio等[2]已經(jīng)證明所有無(wú)標(biāo)度網(wǎng)絡(luò)都是稀疏的.因此，通過(guò)構(gòu)造方法可以得到對(duì)于任意實(shí)數(shù)M>0，存在一個(gè)無(wú)標(biāo)度圖N(t)和一個(gè)數(shù)β≥M，使得|E(N(t))|～β·|N(t)|.本文研究k-單圈圖變量的動(dòng)機(jī)來(lái)自許多仍待解決的猜想[3]，圖的許多來(lái)自Graffiti猜想[4]的不變量，以及實(shí)際應(yīng)用中需要大量的優(yōu)質(zhì)網(wǎng)絡(luò)模型.

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

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

設(shè)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è)圈G中的|V(C)|-1個(gè)頂點(diǎn)在圖G中的度均為2，則稱它為懸掛圈.本文將用到以下三類連通圖的2個(gè)引理：

圖1 三類連通圖

上式指明，樹(shù)中每一個(gè)2度頂點(diǎn)與樹(shù)的葉子數(shù)量無(wú)關(guān).

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

定理1 設(shè)G是一個(gè)含有p個(gè)點(diǎn)q條邊的連通圖，其中p≥3，q≥2.那么

(1)

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

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

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

若圖G1仍然含有圈，進(jìn)行上述減圈運(yùn)算，得到連通圖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.

如此進(jìn)行下去，直到連通圖Gk不再含有圈，即它是樹(shù).注意到

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

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

根據(jù)引理1的公式得

進(jìn)一步，有

由于q=p-1+k，結(jié)論得證.

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

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

(2)

2 主要結(jié)論及其證明

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

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

定理2 設(shè)G是一個(gè)連通圖，整數(shù)k≥0，則：

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

(3)

(ⅱ)G是k-單圈圖，當(dāng)且僅當(dāng)它的點(diǎn)路圈圖是一棵樹(shù).

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

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

根據(jù)引理1，有

(4)

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

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

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

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

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

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

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

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

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

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

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

(5)

證明(ⅰ) 因?yàn)镚的生成樹(shù)有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證明中的減圈運(yùn)算以及

由平面圖的性質(zhì)得

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

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

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

將(s-3)個(gè)新頂點(diǎn)與S中的每個(gè)頂點(diǎn)連接起來(lái)，得到圖H.顯然，

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

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