雙羅馬控制數(shù)的界

張 寧，葉淼林，肖鳳茹①

（安慶師范大學 數(shù)理學院，安徽 安慶 246133）

0 引言

近年來，隨著應(yīng)用數(shù)學廣泛發(fā)展，控制的實際應(yīng)用問題備受關(guān)注，如國際象棋問題、軍事防御問題等［1-2］?？刂评碚撟鳛閳D論研究的一個重要領(lǐng)域，可用來刻畫圖的若干性質(zhì)，在不同條件下，控制衍生出的形式各有不同，如：符號控制［3］、意大利控制［4］、羅馬控制［5］、雙羅馬控制［6］等。圖的雙羅馬控制是圖論研究領(lǐng)域的熱點話題之一，涌現(xiàn)出許多豐富的結(jié)論和成果［7-10］，使控制領(lǐng)域逐步成為體系完整、內(nèi)容充實的重要分支。

雙羅馬控制是在羅馬控制的基礎(chǔ)上進一步完善得到。羅馬帝國的城市中，如果一個沒有軍團保護的城市被攻擊，則該城市必須在至少一個駐扎著2個軍團的城市附近，這樣2個軍團中一個可以被派去保衛(wèi)被攻擊的城市，受保衛(wèi)羅馬帝國的防御策略影響，在文獻［2］中，Stewart最先定義和討論羅馬控制，該控制嚴重增加國防開支，故需要一個更有效精簡的控制策略，隨即引入雙羅馬控制。文獻［6］通過改進羅馬防御戰(zhàn)略，首次給出雙羅馬控制數(shù)學定義，建立雙羅馬控制數(shù)與控制數(shù)、羅馬控制數(shù)之間的關(guān)系，并根據(jù)圖G的階數(shù)，給出連通圖G的雙羅馬控制數(shù)的上界，刻畫達到這個上界的圖類。文獻［11］計算出路和圈的雙羅馬控制數(shù)的精確值，證明二部圖和弦圖相關(guān)的決策問題是np完備的，部分回答文獻［6］中的開放問題。文獻［12］給出的上下界。文獻［13］確定一些特殊圖的雙羅馬控制數(shù)，描述具有特定雙羅馬控制數(shù)的圖。文獻［14］繼續(xù)討論得出的上界和下界。文獻［15］利用最小度、頂點數(shù)、周長及圍長等圖論參數(shù)，研究給出雙羅馬控制數(shù)的若干上下界。

在此基礎(chǔ)上，本文繼續(xù)研究雙羅馬控制數(shù)的相關(guān)性質(zhì)與結(jié)論。首先考慮具有函數(shù)的圖G，給出賦值為2的頂點個數(shù)滿足的條件，并得到樹T中葉子點和支撐點的1個賦值特點。隨后引入?yún)?shù)：最大度、意大利控制數(shù)、最小覆蓋數(shù)、打包數(shù)、3-彩虹控制數(shù)［16］，將參數(shù)的特性與雙羅馬控制結(jié)合，給出雙羅馬控制數(shù)的幾個界限，拓展雙羅馬控制的結(jié)論，完善控制理論結(jié)構(gòu)體系，豐富代數(shù)圖論中對于雙羅馬控制研究。

1 預(yù)備知識

本文研究有限無向的簡單圖，設(shè)G的頂點集為V(G)，邊集為E(G)，簡記為G=(V,E)。G的階 |V|和邊數(shù) |E|分別用n和m表示。對于頂點v∈V，開鄰域N(v)={u∈V:uv∈E} ，閉鄰域N[v]=N(v)?{v} 。頂點v的度degG(v)=|N(v)|，圖G的最大度為Δ(G)，最小度為δ(G)，度為0的點稱為孤立點。圖G的分支數(shù)用w(G)表示，若G的分支數(shù)只有1個，即w(G)=1，則稱圖G是連通的，否則稱G是不連通的。度為1的點稱為葉子點，與葉子點相鄰的點稱為支撐點，記L(G)為G中所有葉子點構(gòu)成的集合，記S(G)為G中所有支撐點構(gòu)成的集合。如果V(H)?V(G)，E(H)?E(G)，則稱H是G的子圖，滿足V(H)=V(G)的子圖H稱為G的生成子圖。無圈的連通圖稱為樹，若G的生成子圖是樹TG，則稱TG為G的生成樹。頂點數(shù)為n的路記作Pn，長為n的圈記作Cn。

設(shè)M?E(G)，對任意的e1,e2∈M，均有e1和e2不相鄰，則稱M為圖G的匹配。若G不存在匹配M′，使得 |M′|＞|M|，則稱M為G的最大匹配。最大匹配的基數(shù)稱為最大匹配數(shù)，記作α(G)。設(shè)K?V(G)，若G的每條邊都至少有1 個頂點在K中，則稱K為圖G的1 個覆蓋。若G不存在覆蓋K′，使得|K′|＜|K|，則稱K為G的最小覆蓋。最小覆蓋的基數(shù)稱為最小覆蓋數(shù)，記作β(G)。設(shè)R?V(G)，如果對于任意不同的2個頂點x,y∈R，均有N[x] ?N[y] =?，則稱R是圖G的1個打包集。若G不存在打包集R′，使得 |R′|＞|R|，則稱R為G的最大打包集。最大打包集的基數(shù)稱為打包數(shù)，記作ρ(G)。

本文主要運用幾個控制函數(shù)及與之對應(yīng)的控制數(shù)概念，定義如下：

定義1［3］設(shè)S?V是G的1個頂點子集，如果S的閉鄰域滿足N[S]=V，則S中的點控制G，稱S為G的控制集。進一步，如果不存在G的控制集S′，使得 |S′|＜|S|，則S是圖G的最小控制集，S中的頂點個數(shù)稱為控制數(shù)，記作γ(G)，S稱為G的γ-集。

定義2［4］設(shè)函數(shù)f:V(G)→{0 ,1,2} ，Vi={v∈V|f(v)=i} ，i=0,1,2 ，對于任意的v∈V，使得如果f(v)=0，則v必須有1個鄰點在V2中，或者至少有2個鄰點在V1中，則稱f是V到{0 ,1,2} 的意大利控制函數(shù)或者羅馬{2 }-控制函數(shù)，簡記為IDFf。函數(shù)f:V(G)→{0, 1,2} 和頂點V的劃分(V0,V1,V2)間存在一個一一對應(yīng)關(guān)系，記作。意大利控制函數(shù)f的權(quán)表示所有頂點的賦值之和，即，如果不存在G的意大利控制函數(shù)f′，使得ω(f′)＜ω(f)，則ω(f)稱為圖G的意大利控制數(shù)，記作γ{R2}(G)，f稱為G的γ{R2}(G)-函數(shù)。

定義3［6］設(shè)函數(shù)f:V(G)→{0 ,1,2,3} ，Vi={v∈V|f(v)=i}，i=0,1,2,3，對于任意的v∈V，使得：

（1）如果f(v)=0，則頂點v必須至少存在2個鄰點在V2中，或者存在1個鄰點在V3中；

（2）如果f(v)=1，則頂點v必須至少存在1個鄰點在V2?V3中。

則f稱為圖G的雙羅馬控制函數(shù)，簡記為DRDFf。f:V→{0 ,1,2,3} 和頂點V的劃分(V0,V1,V2,V3)間存在一個一一對應(yīng)關(guān)系，記作。雙羅馬控制函數(shù)的權(quán)，如果不存在G的雙羅馬控制函數(shù)f′，使得ω(f′)＜ω(f)，則ω(f)稱為圖G的雙羅馬控制數(shù)，記作γdR(G)，f稱為G的γdR(G)-函數(shù)。

引理1［6］圖G中，存在1個權(quán)為γdR(G)的雙羅馬控制函數(shù)f，使得賦值為1的頂點集為空集。

2 主要結(jié)果

首先給出具有γdR(G)-函數(shù)的圖G中頂點集的性質(zhì)，并給出樹T中葉子點和支撐點的一個賦值特點。

性質(zhì)1 設(shè)G是1個圖，對于任意的γdR(G)-函數(shù)

證明 由定義得：V2f?V3f是G的1個控制集，且V2f?V3f=?，則

性質(zhì)2 設(shè)T是n階樹，n≥3，則：

證明 （1）Δ≤2，此時圖G為路或者圈。

情況1G=Pn

恰好有1個鄰點在R中，R中的每個點至少有δ個鄰點在A中，因此δ|R|≤ |A|，則

定義f:V(G)→{0 ,1,2,3} ，使得

顯然f是G的DRDF，所以

定理4 設(shè)G是一個連通圖，階數(shù)為n，邊數(shù)為m，則對于G的生成樹TG有γdR(G)≥γdR(TG)-m+n-1。

證明 如果G是一棵樹，m=n-1，結(jié)論顯然成立。如果G不是一棵樹，設(shè)C是G中的一個圈，f是G的γdR(G)-函數(shù)，因為在C中至少有1個點賦值為0，記作v，即f(v)=0，考慮以下2種情況：

情況1 在C中，記與v相鄰的其中1 點為w，且f(w)=0，此時設(shè)G′=G-vw，定義G′的DRDFg:V(G)→{0 ,1,2,3} ，g(x)=f(x)，?x∈V。

情況2 在C中，記與v相鄰的2 個點為w,z，且w,z賦值為2 或3，此時設(shè)G′=G-vz，定義G′的DRDFg:V(G)→{0 ,1,2,3} ，使得

因 此 構(gòu) 造 出1 個 圖G′ ，令G′ 中 包 含 圈 的 個 數(shù) 為|C(G′) |，G中 包 含 圈 的 個 數(shù) 為|C(G)|，則|C(G′) |≤|C(G)|-1，且對于情況1、情況2 均有ω(g)≤ω(f)+1，重復(fù)上述構(gòu)造G′的步驟，可得到圖G的一個生成樹TG，使得

化簡得γdR(G)≥γdR(TG)-m+n-1。

根據(jù)3-彩虹控制函數(shù)的定義，g是圖G的3RDF，則

證明 設(shè)Hf的頂點劃分π(Hf)={S1,S2,…,St} ，如果Hf是二部圖，則 |Xf|=0，由斷言1知結(jié)論成立。

假設(shè)Hf不是二部圖，則t≥3。定義函數(shù)g:V(G)→2{1,2,3}，使得：

顯然g是圖G的3RDF，且

3 結(jié)語

雙羅馬控制在刻畫圖的性質(zhì)方面存在重要研究意義和價值，文章依據(jù)雙羅馬控制數(shù)的定義，描述其與圖論幾個重要參數(shù)之間的關(guān)系，比較雙羅馬控制數(shù)與這些參數(shù)之間的大小，充實圖的雙羅馬控制理論，如何說明這些界在什么條件達到等號成立的情況，需要繼續(xù)深入探索，對研究極圖方面有推廣作用。