幾類圖的控制參數(shù)的理論與算法.pdf

1、近三十多年來(lái)，隨著計(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ùn)籌學(xué)以及社會(huì)學(xué)等領(lǐng)域具有廣泛的應(yīng)用.目前，關(guān)于圖的控制數(shù)理論研究主要集中在四個(gè)方面：(1)各類控制參數(shù)的界的確定，相互之間關(guān)系的研究，以及控制參數(shù)與圖的其他參數(shù)，如色數(shù)的關(guān)系研究；(2)各類控制參數(shù)計(jì)算復(fù)雜性的研究及其算

2、法的設(shè)計(jì)；(3)函數(shù)控制數(shù)及其相關(guān)課題的研究；(4)控制數(shù)理論在相關(guān)學(xué)科中的應(yīng)用研究. 本文所做的工作主要包括以下五部分：第一，我們確定了一般連通圖及無(wú)爪立方圖上電力控制數(shù)的準(zhǔn)確上界，并對(duì)達(dá)到其上界的極值圖進(jìn)行了刻畫(huà)(有關(guān)結(jié)果已被《DiscreteMathematics》錄用)；并分別討論了外平面圖及一般平面圖上電力控制數(shù)的界(有關(guān)結(jié)果已被《JournalofShanghaiUniversity》錄用). 第二，我們研究

3、了兩類新的控制函數(shù)：負(fù)邊控制函數(shù)和負(fù)星控制函數(shù)；確定了負(fù)邊控制數(shù)的界，并對(duì)達(dá)到其上界的階數(shù)為偶數(shù)的極值圖進(jìn)行了刻畫(huà)；并且討論了這兩類控制參數(shù)與其他控制參數(shù)的關(guān)系(有關(guān)結(jié)果已被《ArsCombinatoria》錄用). 第三，我們對(duì)達(dá)到圖的2-距離控制數(shù)已知上界的極值圖進(jìn)行了完全刻畫(huà).第四，我們給出了二部置換圖上無(wú)圈控制集的線性時(shí)間算法，并研究了三種情況下直線簇上區(qū)間圖的最小連通控制集算法(有關(guān)結(jié)果已發(fā)表在《上海大學(xué)學(xué)報(bào)(自然科學(xué)