圖的幾類全控制參數(shù).pdf

1、在過去近四十年里，隨著計算機科學和網(wǎng)絡通訊技術的飛速發(fā)展，圖論研究也呈現(xiàn)出異?；钴S的趨勢，而控制數(shù)理論的研究是其中發(fā)展最快的領域之一。圖的控制數(shù)理論作為圖論的一個重要研究方向，在相關學科領域，例如計算機科學、通信網(wǎng)絡、組合優(yōu)化、編碼理論、監(jiān)視系統(tǒng)以及運籌學等領域具有廣泛的應用。隨著研究的深入，各種新的控制參數(shù)不斷提出和研究，而且與圖論的經(jīng)典理論相互交融，精彩紛呈。 圖的(全)控制函數(shù)就是圖的經(jīng)典(全)控制數(shù)的一類自然推廣。由于圖

2、的(全)控制函數(shù)的引入，致使利用函數(shù)性質(zhì)來研究各類(全)控制數(shù)成為可能。目前，各類全控制函數(shù)已成為圖的控制理論中一個嶄新的研究方向。關于全控制函數(shù)的研究主要集中在四個方面：(1)確定各種控制參數(shù)的上下界，在一些特殊圖上計算它們的值；(2)尋找各種控制參數(shù)之間的關系；(3)給出極端圖類的結構性質(zhì)的刻畫；(4)各種控制參數(shù)計算復雜性的研究及其算法的設計。 本文所做的工作主要包括以下兩大部分： 第一部分，首先給出了負全k-控制