本文關鍵詞：基于矩陣半張量積方法的幾類圖著色問題研究及應用

  更多相關文章： 魯棒圖著色 列表著色 T-著色 conflict-free著色 頻率分配 矩陣半張量積

【摘要】：圖著色問題是圖論中經(jīng)典的研究課題,在上個世紀70年代首次被證明為NP-hard問題.圖著色問題不僅在圖論發(fā)展中發(fā)揮了重要作用,而且廣泛應用于現(xiàn)實生活中,如航空流量管理、時間表安排、任務調(diào)度、頻率分配等.因此對其進行研究具有非常重要的理論和現(xiàn)實意義.鑒于圖著色問題的多樣性,其相關研究多以某些特定形式的著色問題為研究對象.本課題利用矩陣的半張量積方法,進一步深入研究圖著色問題中的魯棒圖著色、T-著色、列表著色、超圖的Conflict-free著色以及模糊圖的著色等問題.對這些特定形式的著色問題,給出若干新的代數(shù)結果和算法,并將研究結果應用于考試時間表問題和無線通訊中的頻率分配問題.主要包含如下研究內(nèi)容：1.研究魯棒圖著色問題及其在考試時間表中的應用,提出一些新的結果和算法.運用矩陣半張量積將魯棒圖著色問題表示成一類矩陣代數(shù)形式的優(yōu)化問題,并設計一個新的算法以尋找魯棒性最好的所有著色方案.進一步,研究魯棒圖著色問題的等價問題,給出一個充要條件,由此建立一個新的算法尋找魯棒性最好的所有著色方案.另外作為應用,討論一類考試時間表問題,得到一個設計切實可行的時間表方案的方法.兩個例子的計算結果說明新結論和算法的有效性.2.運用矩陣半張量積,研究簡單圖的T-著色和列表著色及其在頻率分配中的應用.首先,運用矩陣半張量積研究T-著色問題,得到可T-著色的兩個充要條件,并在此基礎上,建立一個新的算法以尋找T-著色方案.其次,運用半張量積研究列表著色問題,得到列表著色的充要條件,并由此得到列表T-著色的充要條件.最后,將所得的結果應用于頻率分配問題,以證明所得結果的有效性和應用性.3.運用矩陣半張量積,研究超圖的Conflict-free著色問題,得到幾個新的結果和算法.通過超圖的勢矩陣和特征邏輯向量,得到Conflict-free著色的兩個充要條件,在此基礎上,建立一個可以確定Conflict-free著色方案的新算法.最后，，將理論結果應用于頻率分配問題,說明所得結果的有效性和應用性.4.研究模糊圖的穩(wěn)定點集和著色問題.首先,通過定義特征邏輯變量,利用邏輯函數(shù)的矩陣表示,得到模糊穩(wěn)定點集的代數(shù)描述.基于此,建立一個新的算法以尋找模糊圖的所有穩(wěn)定點集.其次,利用矩陣半張量研究模糊圖的著色問題,對于模糊圖的可著色性給出兩個充要條件,在此基礎上建立一個新的算法,確定所有模糊著色方案及模糊圖的色數(shù).最后,舉例說明結論的有效性.
【關鍵詞】：魯棒圖著色 列表著色 T-著色 conflict-free著色 頻率分配 矩陣半張量積
【學位授予單位】：山東大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要9-11
• ABSTRACT11-14
• 第一章 緒論14-24
• 1.1 圖著色理論的研究背景及現(xiàn)狀14-20
• 1.2 矩陣半張量積的研究現(xiàn)狀20-21
• 1.3 本文的主要內(nèi)容21-24
• 第二章 預備知識24-36
• 2.1 矩陣半張量積的基本概念及性質(zhì)25-30
• 2.2 邏輯函數(shù)的矩陣表示30-33
• 2.3 圖論的基本概念及性質(zhì)33-35
• 2.4 小結35-36
• 第三章 魯棒圖著色及其在考試時間表中的應用36-54
• 3.1 引言36-37
• 3.2 魯棒圖著色37-47
• 3.2.1 等罰值的魯棒圖著色39-46
• 3.2.2 不等罰值的魯棒圖著色46-47
• 3.3 考試時間表中的應用47-49
• 3.4 例子49-52
• 3.5 小結52-54
• 第四章 T-著色和列表著色及其在頻率分配中的應用54-72
• 4.1 引言54-55
• 4.2 T-著色55-59
• 4.3 列表著色59-63
• 4.4 列表T-著色63
• 4.5 頻率分配中的應用63-65
• 4.6 例子65-69
• 4.7 小結69-72
• 第五章 Conflict-free著色及其在頻率分配中的應用72-80
• 5.1 引言72-73
• 5.2 Conflict-free著色73-77
• 5.3 頻率分配中的應用77-79
• 5.4 小結79-80
• 第六章 模糊穩(wěn)定點集和模糊圖著色80-98
• 6.1 引言80-81
• 6.2 模糊穩(wěn)定點集81-85
• 6.3 模糊圖著色85-93
• 6.3.1 交通信號燈問題85-87
• 6.3.2 模糊圖著色87-93
• 6.4 例子93-96
• 6.5 小結96-98
• 第七章 結論與展望98-100
• 7.1 結論98
• 7.2 展望98-100
• 參考文獻100-112
• 致謝112-114
• 攻讀博士學位期間完成的論文及參與的科研項目114-116
• 附件（文章）116-133
• 附件（表）133

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前4條

1 ;Logic and logic-based control[J];Journal of Control Theory and Applications;2008年01期

2 LIU ZhenBin;WANG YuZhen;LI HaiTao;;Two kinds of optimal controls for probabilistic mix-valued logical dynamic networks[J];Science China(Information Sciences);2014年05期

3 李志強;宋金利;;布爾控制網(wǎng)絡的能控性與能觀性(英文)[J];控制理論與應用;2013年06期

4 葛愛冬;王玉振;魏愛榮;;基于矩陣半張量積方法的隨機模糊系統(tǒng)控制器設計[J];山東大學學報(工學版);2013年03期

本文編號：590563