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

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

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