若干圖類的全符號控制數(shù)的研究.pdf

1、圖的符號控制是圖論的一個重要的研究方向，不僅僅在實際生活中有著非常廣泛的應(yīng)用，例如，發(fā)射基站的選址、計算機(jī)通訊網(wǎng)絡(luò)和群決策等，而且人們也可以在計算的復(fù)雜性和算法設(shè)計、優(yōu)化理論、通訊網(wǎng)絡(luò)設(shè)計與分析等方面應(yīng)用圖的控制理論。我們研究圖的符號控制尤其是一些特殊圖的符號控制問題可以為解決一般的NP-困難問題提供重要的借鑒，具有較為重要的意義，圖的控制數(shù)的研究也因此一直受到廣大學(xué)者的關(guān)注。
　　本文主要研究路徑圖Pm與圈圖Cn的交圖的全符號控

2、制數(shù)。本文考慮的圖G均為有限簡單連通圖，根據(jù)Pm□Cn的點和邊鄰域的特點（在全符號控制研究中，頂點的鄰域中包含邊，邊的鄰域中也包含頂點），給出圖Pm□Cn的全符號控制數(shù)較好的上下界。
　　首先，根據(jù)前人的重要結(jié)論，對于任意圖G，如果圖G頂點的最小度為δ(G)，最大度為△(G)，頂點數(shù)為|V(G)|，邊數(shù)為|E(G)|，那么G的全符號控制數(shù)為:γ*s(G)≥([)δ(G)-△(G)+1/δ(G)+△(G)+1(|E(G)|+|V(G

3、)|)(])ρ(|E(G)|+|V'(G)|),
　　并且這個下界是可達(dá)的，其中ρ(s)表示s的奇偶性，即如果s是奇數(shù)時，則ρ(s)=奇數(shù)，如果s是偶數(shù)時，則ρ(s)=偶數(shù)。
　　對于Pm□Cn，根據(jù)上式可以得到γ*s（Pm□Cn）≥0，由于Pm□Cn的點和邊鄰域的特性，我們可知其全符號控制數(shù)γ*s（Pm□Cm）的下界可以比零更大一些。利用解析法證明Pm□Cn的全符號控制數(shù)γ*s（Pm□Cn）的下界，該下界比一般圖G的全符號