《羅馬控制數、彩虹控制數及相關問題的研究》是依託東南大學，由吳雲建擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：羅馬控制數、彩虹控制數及相關問題的研究
- 項目類別：青年科學基金項目
- 項目負責人：吳雲建
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
圖的控制理論是圖論的重要組成部分，也是圖論的難點之一，它被廣泛套用於計算機科學、通訊網路的設計和分析、算法複雜性等諸多領域。.羅馬控制數的研究來源於軍事策略，要求每個沒有軍團駐紮的堡壘需要與一個駐紮兩個軍團的堡壘相鄰，彩虹控制數的引進則是為了解決控制理論里的Vizing猜想。在本項目中，我們將做以下工作：(1)對於羅馬控制數問題，為了滿足網路戰需求，我們將考慮沒有軍團駐紮的堡壘同時受到攻擊的情形；(2)由於每個羅馬控制集能對應到一個2-彩虹控制集，因此我們將這兩個控制數結合起來考慮，在半徑、圍長和連通度等條件下，研究彩虹控制數的性質和上下界，並找到那些極圖，為Vizing猜想的解決提供更多的理論基礎和方法；(3)鑒於上述兩個控制數問題都是NP-完備的，我們將給出一些特殊圖類的線性算法或多項式近似算法。兩個控制參數的歷史背景和套用價值，已經吸引了國內外眾多著名學者的關注。
結題摘要
圖的控制理論是圖論的一個重要組成部分，它被廣泛套用於計算機科學、通訊網路的設計和分析、算法複雜性等諸多領域。1962年，數學家Ore引進並研究了圖的控制理論。之後，控制理論得到了廣泛的研究。隨著網路的發展、軍事部署的要求和科學研究的需要，出現了多種變形的控制參數。在本項目中，我們主要研究了羅馬控制數和彩虹控制數的一些相關問題。由於上述兩個控制數問題都是NP-完備的，因此我們嘗試得到了一些特殊圖類的多項式近似算法，並得到部分乘積圖的羅馬控制數的上界。 卷積是一個有趣的問題，很多學者給出了一些卷積的精確公式。本項目中，我們也得到部分卷積公式。最近Dai利用Hecke運算元證明了新的關於broken 11-diamond分拆函式模2的無窮族同餘關係。在本項目中，我們利用Newman的等式建立了新的關於broken 11-diamond分拆函式模2的無窮族同餘關係，推廣了Dai的結果。以外，我們還建立了關於broken 11-diamond分拆函式模2的奇異的同餘關係。
