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

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

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