弱羅馬圖和圖的弱羅馬控制的一些性質(zhì)

楊 劍, 李志強(qiáng)

(1. 河南交通職業(yè)技術(shù)學(xué)院公共基礎(chǔ)教學(xué)部，鄭州 450000;2. 河南財(cái)經(jīng)政法大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，鄭州 450002)

0 引言

設(shè)G=(V,E)是一個(gè)頂點(diǎn)集為V，邊集為E的圖，定義實(shí)值函數(shù)f:0,1,2}，即對(duì)任意的v ∈V，則f(v) = 0 或1 或2。設(shè)V0、V1和V2分別表示在上述f定義下取值分別為0、1 和2 的頂點(diǎn)集，即Vi={v ∈V|f(v) =i}，其中i= 0,1,2。注意到，函數(shù)f:0,1,2}和頂點(diǎn)集V的劃分(V0,V1,V2)是一一對(duì)應(yīng)關(guān)系。因此，為了方便亦記函數(shù)f=(V0,V1,V2)。

羅馬控制理論首先是由Stewart[1]提出的，在此基礎(chǔ)上，Cockayne 等[2]給出了羅馬控制函數(shù)的定義。設(shè)圖G= (V,E)，令函數(shù)f= (V0,V1,V2)，若V0中的每一個(gè)頂點(diǎn)都至少與V2中的一個(gè)頂點(diǎn)相鄰，則稱(chēng)f為圖G的羅馬控制函數(shù)(簡(jiǎn)稱(chēng)RDF)。函數(shù)f=(V0,V1,V2)的權(quán)記為

圖G的羅馬控制函數(shù)的最小權(quán)稱(chēng)為羅馬控制數(shù)，記為γR(G)，即

例如，2×5 格子圖G2,5的羅馬控制數(shù)為6，如圖1(a)，其中空心圈代表V1中的點(diǎn)，實(shí)心圈代表V2中的點(diǎn)，其他為V0中的點(diǎn)。一個(gè)權(quán)為γR(G)的RDF 稱(chēng)為γR(G)-函數(shù)。

羅馬控制函數(shù)的概念來(lái)源于下面的實(shí)際問(wèn)題。設(shè)圖中的每一頂點(diǎn)代表羅馬帝國(guó)的一個(gè)地區(qū)，如果一個(gè)地區(qū)(頂點(diǎn)v)沒(méi)有軍團(tuán)駐扎，即f(v) = 0，則稱(chēng)該地區(qū)是不安全的，否則(即該地區(qū)有一個(gè)軍團(tuán)駐扎(f(v) = 1)，或有兩個(gè)軍團(tuán)駐扎(f(v) = 2))稱(chēng)該地區(qū)是安全的。一個(gè)不安全的地區(qū)(頂點(diǎn)v)能夠被安全防御，如果能夠從相鄰的地區(qū)(v的一個(gè)鄰點(diǎn)u)派一個(gè)軍團(tuán)到達(dá)該地區(qū)。但是在公元4 世紀(jì)最高統(tǒng)治者頒布法令：若從一個(gè)安全地區(qū)派遣一個(gè)軍團(tuán)到一個(gè)不安全地區(qū)使得原地區(qū)不安全，則不允許派遣。因此，在派出其中一個(gè)軍團(tuán)到相鄰地區(qū)之前必須在該地區(qū)駐扎兩個(gè)軍團(tuán)(f(v) = 2)。最高統(tǒng)治者利用這種方式能夠防御羅馬帝國(guó)。為了節(jié)約軍費(fèi)，統(tǒng)治者想用盡可能少的軍團(tuán)防御羅馬帝國(guó)。因此，一個(gè)權(quán)為γR(G)的羅馬控制函數(shù)就對(duì)應(yīng)著一個(gè)最優(yōu)派遣軍團(tuán)駐扎的方案。

為了進(jìn)一步探索節(jié)約軍費(fèi)開(kāi)支的方法，同時(shí)仍然能夠防御羅馬帝國(guó)，Henning 和Hedetniemi[3]提出了新的策略，給出了弱羅馬控制函數(shù)的定義。設(shè)圖G= (V,E)，令函數(shù)f=(V0,V1,V2)，若V0中的頂點(diǎn)u不與V1或V2中的任何頂點(diǎn)相鄰，則稱(chēng)它是未被防御點(diǎn)。如果函數(shù)f=(V0,V1,V2)滿(mǎn)足：若V0中的每一個(gè)頂點(diǎn)u都至少與V1∪V2中的一個(gè)頂點(diǎn)v相鄰，并且fu:0,1,2}(fu(u)=1,fu(v)=f(v)?1 且fu(w)=f(w),?w ∈V ?{u,v})沒(méi)有未防御點(diǎn)，則稱(chēng)f為圖G的弱羅馬控制函數(shù)(簡(jiǎn)稱(chēng)WRDF)。圖G的弱羅馬控制函數(shù)的最小權(quán)稱(chēng)為弱羅馬控制數(shù)，記為γr(G)，即

例如，2×5 格子圖G2,5的弱羅馬控制數(shù)為4，如圖1(b)。一個(gè)權(quán)為γr(G)的WRDF 稱(chēng)為γr(G)-函數(shù)。

圖1 對(duì)2×5 格子圖G2,5 的構(gòu)造

Henning 和Hedetniemi[3]基于下面的思想給出了WRDF 的定義。如果一個(gè)地區(qū)是不安全的(即沒(méi)有軍團(tuán)駐扎)，且與之相鄰的地區(qū)也都是不安全的，則稱(chēng)這個(gè)地區(qū)是未防御的。由于不安全地區(qū)是薄弱可擊的，所以要求每一個(gè)不安全地區(qū)都與一個(gè)安全地區(qū)相鄰，并且當(dāng)這個(gè)地區(qū)遭到攻擊時(shí)，從相鄰地區(qū)派遣軍團(tuán)到此防御，不會(huì)產(chǎn)生未防御地區(qū)，故每一個(gè)不安全地區(qū)同樣能夠進(jìn)行防御。統(tǒng)治者通過(guò)這種方法仍然能夠保衛(wèi)羅馬帝國(guó)，而這種派遣軍團(tuán)保衛(wèi)帝國(guó)的方案恰好對(duì)應(yīng)著一個(gè)WRDF，并且最少軍團(tuán)數(shù)目恰好對(duì)應(yīng)著WRDF 的最小權(quán)，這種方案既能節(jié)約軍費(fèi)又能保衛(wèi)帝國(guó)。因此，弱羅馬控制更加重要和實(shí)用。

羅馬控制是一個(gè)有豐富歷史背景和數(shù)學(xué)背景的典型控制問(wèn)題[1–16]，它與計(jì)算機(jī)科學(xué)、交通安全監(jiān)管控制、企業(yè)安全生產(chǎn)監(jiān)管控制、組合優(yōu)化、監(jiān)視系統(tǒng)和社會(huì)網(wǎng)絡(luò)等領(lǐng)域密切相關(guān)，具有重要的理論意義和應(yīng)用價(jià)值。Cockayne 等[2]研究了圖的羅馬控制，其中包括確定了路、圈、完全n部圖和2×n格子圖等的羅馬控制數(shù)，給出了羅馬控制數(shù)的上、下界，刻畫(huà)了γR(G) =γ(G),γR(G) =γ(G)+1 和γR(G) =γ(G)+2 的圖G的特征，以及γR(T)=γ(T)+1 和γR(T)=γ(T)+2 的樹(shù)T的特征等。Henning 和Hedetniemi[3]研究了圖的弱羅馬控制，其中包括確定了路和圈等的弱羅馬控制數(shù)，刻畫(huà)了γr(G) =γ(G)的圖G的特征等。本文作者也曾研究了圖的弱羅馬控制，其中包括確定了完全n部圖的弱羅馬控制數(shù)和弱羅馬控制數(shù)的下界，給出了弱羅馬控制數(shù)的上界等[5]，刻畫(huà)了γr(T) =γ(T)的樹(shù)T的特征[6]以及γr(G) =γ(G)+1 的圖G的特征[7]，在文獻(xiàn)[8]中確定了2×n格子圖的弱羅馬控制數(shù)，宋曉新等[9]確定了3×n格子圖的弱羅馬控制數(shù)。本文用構(gòu)造法確定了路P3，星K1,t(t ≥2)，由星K1,t1,K1,t2,···,K1,tn(ti ≥3,i=1,2,···,n)的中心點(diǎn)依次連接成一條路所構(gòu)成的樹(shù)T，或由它們的外點(diǎn)連接構(gòu)成的樹(shù)T是弱羅馬圖，并給出了弱羅馬圖和圖的弱羅馬控制的一些性質(zhì)。本文所考慮的圖均為有限的非平凡簡(jiǎn)單圖。

1 概念和已知結(jié)論

設(shè)G=(V,E)是一個(gè)頂點(diǎn)集為V、邊集為E，且階數(shù)為n的圖，v是V的任意一個(gè)頂點(diǎn)，頂點(diǎn)v的度記為d(v)。頂點(diǎn)v的開(kāi)鄰域記為N(v) ={u ∈V|uv ∈E}，且閉鄰域記為N[v] ={v}∪N(v)。對(duì)一個(gè)集合S ?V，它的開(kāi)鄰域記為N(S) =∪v∈SN(v)?S，且它的閉鄰域記為N[S] =S ∪N(S)。設(shè)u ∈V,S ?V，若N[u]∩S={v}，則稱(chēng)頂點(diǎn)u為v關(guān)于S的私有鄰點(diǎn)，或簡(jiǎn)稱(chēng)v的一個(gè)S ?pn。頂點(diǎn)v的所有S ?pn的集合記為pn(v,S) =N[v]?N[S ?{v}]，被稱(chēng)為v關(guān)于S的私有鄰集[4]。我們定義v關(guān)于S的外私有鄰集為epn(v,S) =pn(v,S)?{v}，簡(jiǎn)稱(chēng)v關(guān)于S的外私有鄰點(diǎn)為S ?epn，則集合epn(v,S)?V ?S。如果對(duì)于任意的u,v ∈S，使得N[u]∩N[v] =?，則稱(chēng)S是2-分離集。

設(shè)G=(V,E),S ?V，若U中的每一個(gè)頂點(diǎn)都至少與S中的一個(gè)頂點(diǎn)相鄰，則稱(chēng)集合S控制集合U，記為S ?U。如果S ?V ?S，或者N[S]=V，則稱(chēng)S為圖G的一個(gè)控制集[4]。圖G的控制集的最小基數(shù)稱(chēng)為最小控制數(shù)，記為γ(G)，即

一個(gè)基數(shù)為γ(G)的控制集稱(chēng)為γ(G)-集。

設(shè)T= (V,E)是一個(gè)頂點(diǎn)集為V、邊集為E，且階數(shù)為n的樹(shù)，一個(gè)度為1 的頂點(diǎn)稱(chēng)為樹(shù)T的一片葉子(又稱(chēng)為懸掛點(diǎn))，與葉子相鄰的頂點(diǎn)稱(chēng)為樹(shù)T的支撐點(diǎn)，與至少兩片葉子相鄰的頂點(diǎn)稱(chēng)為強(qiáng)支撐點(diǎn)。在本文中，記所有支撐點(diǎn)集合為S(T)，所有強(qiáng)支撐點(diǎn)的集合為SS(T)，所有葉子集合為L(zhǎng)(T)。若S ?V，則以S為點(diǎn)集、S中各點(diǎn)之間的邊還保留原樹(shù)T的邊構(gòu)成的子樹(shù)，記為T(mén)[S]。對(duì)于任給的正整數(shù)t，完全二部圖K1,t稱(chēng)為星，并且稱(chēng)度為t(t ≥2)的頂點(diǎn)為中心點(diǎn)，度為1 的頂點(diǎn)為外點(diǎn)。特別地，在P2中，稱(chēng)兩個(gè)頂點(diǎn)都為中心點(diǎn)。若圖G滿(mǎn)足γR(G) = 2γ(G)，則稱(chēng)圖G是羅馬圖。若圖G滿(mǎn)足γr(G)=2γ(G)，則稱(chēng)圖G是弱羅馬圖。

為了研究問(wèn)題的方便，下面把與本文有關(guān)的已有結(jié)論列出來(lái)，以便后面使用。

引理1[3]對(duì)任意圖G，γ(G)≤γr(G)≤γR(G)≤2γ(G)。

引理2[2]圖G是羅馬圖，當(dāng)且僅當(dāng)它有一個(gè)γR-函數(shù)f=(V0,V1,V2)，使得V1=?。

引理3[2]圖G是羅馬圖，當(dāng)且僅當(dāng)

對(duì)每一個(gè)2-分離集S ?V。

引理4[3]如果圖G滿(mǎn)足γr(G)=2γ(G)，則對(duì)每一個(gè)γ(G)-集S和每一個(gè)v ∈S，外私有鄰集epn(v,S)包含兩個(gè)不相鄰的點(diǎn)。

引理5[5]如果圖G= (V,E)的階數(shù)為n且包含一個(gè)度為n ?1 的頂點(diǎn)，則γ(G) =1，并且如果G=Kn，則γr(G)=γ(G)=1；否則γr(G)=γR(G)=2。

引理6[3]對(duì)任意的n≥1，有γr(Pn)=「?；對(duì)任意的n ≥4，有γr(Cn)=「?。

引理7[16]對(duì)任意的n≥1，有γ(Pn)=「?。

2 弱羅馬圖

在文獻(xiàn)[2]中給出了羅馬圖的兩個(gè)特征，如引理2 和引理3，在文獻(xiàn)[3]中給出了弱羅馬圖的一個(gè)特征，如引理4。下面我們給出弱羅馬圖的一些性質(zhì)，對(duì)刻畫(huà)弱羅馬圖的特征具有重要意義。

定理1對(duì)任意的圖G= (V,E)，γr(G) = 2γ(G)，當(dāng)且僅當(dāng)存在一個(gè)γr(G)-函數(shù)f=(V0,V1,V2)，使得V1=?。

證明 (?) 若γr(G) = 2γ(G)，設(shè)S是G的一個(gè)γ(G)-集，則令f= (V0,V1,V2) =(V ?S,?,S)是G的一個(gè)WRDF。又

所以f是一個(gè)γr(G)-函數(shù)，并且V1=?。

(?) 設(shè)f=(V0,V1,V2)是一個(gè)γr(G)-函數(shù)，使得V1=?。因此γr(G)=2|V2|，又由定義知V1∪V2?V，所以V2是G的一個(gè)控制集。從而γ(G)≤|V2|，即2γ(G)≤2|V2|=γr(G)。又由引理1 知γr(G)≤2γ(G)，故γr(G)=2γ(G)。

推論1對(duì)任意的圖G= (V,E)，則γr(G) =γR(G) = 2γ(G)，當(dāng)且僅當(dāng)存在一個(gè)γr(G)-函數(shù)f=(V0,V1,V2)，使得V1=?。

推論2對(duì)任意的圖G=(V,E)，如果γr(G)為奇數(shù)，則圖G不是弱羅馬圖。

定理2如果圖G=(V,E)的階數(shù)為n且包含一個(gè)度為n?1 的頂點(diǎn)，并且G ?=Kn，則圖G既是羅馬圖也是弱羅馬圖。

證明 由于G ?=Kn，由引理5 可知γ(G) = 1，并且γr(G) =γR(G) = 2，故γr(G)=γR(G)=2=2γ(G)，即圖G既是羅馬圖也是弱羅馬圖。

定理3設(shè)樹(shù)T的強(qiáng)支撐點(diǎn)集合為SS(T)，如果γr(T) = 2γ(T)，則存在一個(gè)γr(T)-函數(shù)f=(V0,V1,V2)，使SS(T)?V2。

證明 由于γr(T) = 2γ(T)，由定理1 可知，存在一個(gè)γr(T)-函數(shù)f= (V0,V1,V2)，使得V1=?。假設(shè)存在v ∈SS(T)V2，則v ∈V0。又由于v是樹(shù)T的強(qiáng)支撐點(diǎn)，則至少存在兩片葉子，不妨設(shè)u和w是它的葉子，則uv,wv ∈E，并且uw/∈E。因此u,w ∈V1矛盾，故SS(T)?V2。

定理4對(duì)任意的路Pn，只有路P3是弱羅馬圖。

證明 對(duì)任意的n ≥1，由引理6 知γr(Pn) =「?，又由引理7 知γ(Pn) =「?，我們有：

1) 當(dāng)n= 1,2 時(shí)，γr(P1) =γr(P2) = 1,γ(P1) =γ(P2) = 1，顯然γr(P1)?=2γ(P1),γr(P2)?=2γ(P2)，故路P1和P2不是弱羅馬圖；

2) 當(dāng)n= 3 時(shí)，如圖2 所示，其中空心圈代表V0中的點(diǎn)，實(shí)心圈代表V2中的點(diǎn)。γr(P3)=2，并且γ(P3)=1，即γr(P3)=2γ(P3)，故路P3是弱羅馬圖；

圖2 對(duì)路P3 的構(gòu)造

3) 當(dāng)n ≥4 時(shí)，γr(Pn)=「?＜2「?=2γ(Pn)，故路Pn(n ≥4)不是弱羅馬圖。

綜上，對(duì)任意的路Pn，只有路P3是弱羅馬圖。

定理5星K1,t(t ≥2)是弱羅馬圖。

證明 對(duì)于星K1,t(t ≥2)，如圖3 的構(gòu)造，其中空心圈代表V0中的點(diǎn)，實(shí)心圈代表V2中的點(diǎn)。顯然γ(G) = 1，并且γr(G) = 2，即γr(G) = 2γ(G)，故星K1,t(t ≥2)是弱羅馬圖。

圖3 對(duì)星K1,t(t ≥2)的構(gòu)造

定理6設(shè)星K1,t1,K1,t2,···,K1,tn(ti ≥3,i=1,2,···,n)的中心點(diǎn)分別記為v1,v2,···,vn，并記vi1,vi2∈V(K1,ti)(i= 1,2,···,n)為星K1,ti(i= 1,2,···,n)的任意兩個(gè)外點(diǎn)，則：

(a) 由中心點(diǎn)v1,v2,···,vn依次用邊連接成一條路，所構(gòu)成的樹(shù)T1是弱羅馬圖，如圖4 上圖，其中空心圈代表V0中的點(diǎn)，實(shí)心圈代表V2中的點(diǎn)；

(b) 讓外點(diǎn)vi2與vi+1,1(i= 1,2,···,n ?1)用邊連接，使v1,v12,v21,v2,v22,···,vn?1,2,vn1,vn成一條路，所構(gòu)成的樹(shù)T2是弱羅馬圖，如圖4 下圖。

證明 (a) 由于星K1,t1,K1,t2,···,K1,tn(ti ≥3,i= 1,2,···,n)的中心點(diǎn)分別為v1,v2,···,vn，如圖4 上圖的構(gòu)造，則顯然S={v1,v2,···,vn}是 樹(shù)T1的一個(gè)γ(T1)-集，并且γ(T1) =|S| =n。令函數(shù)f= (V0,V1,V2) = (V ?S,?,S)，顯然f是樹(shù)T1的一個(gè)γr(T1)-函數(shù)，并且

故樹(shù)T1是弱羅馬圖。

(b) 如圖4 下圖的構(gòu)造，顯然S={v1,v2,···,vn}是樹(shù)T2的一個(gè)γ(T2)-集，并且γ(T2) =|S| =n。令函數(shù)f= (V0,V1,V2) = (V ?S,?,S)，顯然f是樹(shù)T2的一個(gè)γr(T2)-函數(shù)，并且

圖4 對(duì)樹(shù)T1 和T2 的構(gòu)造

故樹(shù)T2是弱羅馬圖。

由引理1 可知，對(duì)任意圖G，γ(G)≤γr(G)≤2γ(G)，我們有下面的觀察。

觀察1γr(G)與2γ(G)的差距可以無(wú)限大。

例如，把星K1,t(t ≥2)的每一條邊一分為二得到的圖，稱(chēng)為細(xì)分星圖，記為S(K1,t)(t ≥2)，如圖5，其中圖5(a)空心圈代表V0中的點(diǎn)，實(shí)心圈代表V1中的點(diǎn)，圖5(b)實(shí)心圈代表控制集中的點(diǎn)，則由圖5(a)的構(gòu)造不難看出γr(S(K1,t))=t+1，而由圖5(b)的構(gòu)造不難看出γ(S(K1,t))=t。因此2γ(S(K1,t))?γr(S(K1,t))=t ?1(t ≥2)可以無(wú)限大。

圖5 對(duì)細(xì)分星圖S(K1,t)(t ≥2)的構(gòu)造

3 圖的弱羅馬控制的一些性質(zhì)

在文獻(xiàn)[3]中給出了圖的弱羅馬控制的一些性質(zhì)，下面我們給出圖的弱羅馬控制的另外幾個(gè)性質(zhì)，對(duì)進(jìn)一步研究圖的弱羅馬控制具有重要意義。

定理7設(shè)f=(V0,V1,V2)是圖G的一個(gè)γr(G)-函數(shù)，S=V1∪V2，則：

(a) 對(duì)任意的v ∈V1，pn(v,S)構(gòu)成一個(gè)團(tuán)；

(b) 若存在v0∈V0,d(v0) = 2，不妨設(shè)u1,u2∈N(v0),u1v0,u2v0∈E(G)，使得u1和u2都含有至少一個(gè)S ?epn，并且N[u1]?{v0}和N[u2]?{v0}構(gòu)成一個(gè)團(tuán)，則f(u1)?=f(u2)。

證明 (a) 設(shè)f= (V0,V1,V2)是圖G的一個(gè)γr(G)-函數(shù)。對(duì)任意的v ∈V1，設(shè)u,w∈epn(v,S)，則u,w ∈V ?S=V0。因?yàn)関是S中唯一與u相鄰的頂點(diǎn)，所以調(diào)動(dòng)一個(gè)軍團(tuán)從v到u不會(huì)產(chǎn)生未防御點(diǎn)，即函數(shù)

沒(méi)有未防御點(diǎn)。但是由于N(w)∩(S?{v})=?，則必有uw ∈E(G)。因此，epn(v,S)構(gòu)成一個(gè)團(tuán)，從而pn(v,S)構(gòu)成一個(gè)團(tuán)。

(b) 設(shè)f= (V0,V1,V2)是圖G的一個(gè)γr(G)-函數(shù)。顯然f(u1)和f(u2)不能同時(shí)為0。假設(shè)f(u1) =f(u2) = 1，設(shè)w ∈epn(u1,S)，由于d(v0) = 2，并且u1v0,u2v0∈E(G)。令

則w不與任何V1∪V2中的點(diǎn)相鄰，因而為未防御點(diǎn)，與已知矛盾。若令

同理導(dǎo)出矛盾。假設(shè)f(u1)=f(u2)=2，令fu1=(V0,V1∪{u1},V2{u1})。由于N[u1]?{v0}構(gòu)成一個(gè)團(tuán)，則pn(u1,S)?N[u1]?{v0}，易見(jiàn)fu1是圖G的一個(gè)WRDF。但是fu1(V)=f(V)?1，與已知矛盾。

綜上可得f(u1)?=f(u2)。

定理8設(shè)f=(V0,V1,V2)是圖G的一個(gè)γr(G)-函數(shù)，則：

(a) 若u ∈V2,v ∈V1，并且uv ∈E(G)，則N(u)∩V0?=?；

(b) 對(duì)任意的v ∈V2,|N(v)∩V0|≥2。

證明 (a) 假設(shè)N(u)∩V0=?，由于u ∈V2,v ∈V1，則令fu=(V0,V1∪{u},V2{u})，即fu(u) = 1 且fu(w) =f(w),?w ∈V ?{u}，則頂點(diǎn)u仍然能夠被防御，又其他防御體系未變，且N(u)∩V0=?，即N(u)?V1∪V2，故對(duì)任意的w ∈V ?{u}仍然能夠被防御。因此，fu沒(méi)有未防御點(diǎn)，即fu是圖G的一個(gè)WRDF。但是

與已知矛盾，故N(u)∩V0?=?。

(b) 假設(shè)存在v ∈V2，使得|N(v)∩V0|≤1，即N(v)∩V0=?或{v0}，則令fv=(V0,V1∪{v},V2{v})，即fv(v) = 1 且fv(w) =f(w),?w ∈V ?{v}，則頂點(diǎn)v仍然能夠被防御，又其他防御體系未變，若N(v)∩V0=?，即N(v)?V1∪V2，則對(duì)任意的w ∈V ?{v}仍然能夠被防御，若N(v)∩V0={v0}，則調(diào)動(dòng)一個(gè)軍團(tuán)從v到v0不會(huì)產(chǎn)生未防御點(diǎn)，從而對(duì)任意的w ∈V ?{v}仍然能夠被防御。因此，fv沒(méi)有未防御點(diǎn)，即fv是圖G的一個(gè)WRDF。但是

與已知矛盾，故對(duì)任意的v ∈V2,|N(v)∩V0|≥2。

注1定理8(a)中的條件u ∈V2不可減少，否則結(jié)論不一定成立。例如，設(shè)由P3=v0v1v2兩端點(diǎn)v0和v2分別生成完全圖K3所構(gòu)成的圖記為G，如圖6，其中空心圈代表V0中的點(diǎn)，實(shí)心圈代表V1中的點(diǎn)。令

圖6 對(duì)圖G 的構(gòu)造

則顯然f是一個(gè)γr(G)-函數(shù)，而N(v1)∩V0=?。