圖中k-控制參數(shù)之間的一些關系.pdf

1、計算機科學和網(wǎng)絡通訊技術的飛速發(fā)展，帶動了組合數(shù)學研熱潮，尤其是圖論，而控制數(shù)理論也是圖論中發(fā)展最快的一個分支。目前，關于圖的控制數(shù)理論研究主要集中在以下四個方面： (1)各種控制參數(shù)的界的確定，相互之間關系的研究，以及控制參數(shù)與圖的其他參數(shù)之間關系的研究(2)各種控制參數(shù)計算復雜性的研究及其算法的設計；(3)函數(shù)控制數(shù)及其相關課題的研究；(4)控制數(shù)理論在相關學科中的應用研究。S()V(G)，S稱為G的控制集，如果對任意點v∈

2、V＼S，v至少鄰接S的一個點，即V[S]=V(G)．圖G的控制數(shù)，γ(G)定義為G的最小控制集的頂點數(shù)，即γ(G)=min｛｜S｜：S為G的控制集｝．基數(shù)恰為γ(G)的控制集稱為G的一個γ-集．如果S是G的控制集，則稱S控制G．如果對任意的v∈V(G)＼S，存在u∈S，使得d(u，v)≤k，則稱集合S()V(G)為圖G的k-控制集，稱uk-控制v． 本文所做的工作主要包括以下幾個方面： (1)我們研究了k-控制數(shù)的上界，

3、并得到對于每一個連通分支都含有至少k+1個頂點的n階圖G，有γk(G)≤「n/k+1」，并證明了它是最優(yōu)的；其次證明了對于一個n(n≥k+1)階，最大度為△的連通圖G，有γk(G)≤「n-△+k-1/k」，其中k為任意正整數(shù)； (2)對于任意連通圖G：證明了diam(G)-2k+1≤γck(G)≤n-△k；并且當k≥1時，有γck(G)≤(2k+k+1/2)ir(G)-2k． (3)應用概率方法給出連通k-控制數(shù)的上界：