關(guān)于圖的幾類控制數(shù)的下界的研究.pdf

1、對于圖G=(V,E)，子集S包含于V，稱點集S為圖G的控制集，若對于任意的y∈V-S，都存在x∈S，使xy∈E(G)。
　　由于控制理論的研究越來越引起人們的重視，人們對控制數(shù)有了更深的了解，提出了不同的控制數(shù)。例如：符號控制數(shù)，符號邊控制數(shù)，符號全控制數(shù)等。這些控制數(shù)在圖的結(jié)構(gòu)中起了重要的作用。
　　本論文主要討論了圖的幾類控制數(shù)的下界。在[3]中，魯進(jìn)步，劉林中給出了全符號控制函數(shù)的定義，并給出了一些特殊圖的全符號控制數(shù)

2、的上界。本文繼續(xù)研究圖的全符號控制數(shù)，并且得到一些特殊圖的全符號控制數(shù)的下界，接著又給出了一般圖的全符號控制數(shù)的下界。
　　本文還給出了圖的負(fù)邊控制的定義：設(shè)為一個圖，一個函數(shù)f:E→{-1, 0,1}被稱為圖G的一個負(fù)邊控制函數(shù)，如果G f[e]=f(N[e])=∑x∈N[e]f(x)≥1對所有的邊e∈E成立。圖的負(fù)邊控制數(shù)定義為：γ-e(G)=min{f(E)｜f為圖G的負(fù)邊控制函數(shù)}。并討論了圖的負(fù)邊控制數(shù)的下界，還刻畫了γ