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

1、近三十多年來，隨著計算機科學和網(wǎng)絡通訊技術的飛速發(fā)展，圖論研究也呈現(xiàn)出異?；钴S的趨勢，而控制數(shù)理論也許是其中發(fā)展最快的領域.圖的控制數(shù)理論作為圖論的一個重要研究方向，在相關學科領域，例如計算機科學、通訊網(wǎng)絡、編碼理論、運籌學以及社會學等領域具有廣泛的應用.目前，關于圖的控制數(shù)理論研究主要集中在四個方面：(1)各類控制參數(shù)的界的確定，相互之間關系的研究，以及控制參數(shù)與圖的其他參數(shù)，如色數(shù)的關系研究；(2)各類控制參數(shù)計算復雜性的研究及其算

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

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