《圖的染色問題及其在網路中的套用》是依託中國海洋大學，由劉彬擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的染色問題及其在網路中的套用
- 項目類別：青年科學基金項目
- 項目負責人：劉彬
- 依託單位：中國海洋大學
中文摘要,結題摘要,
中文摘要
圖的染色理論是圖論中一個經典且新問題不斷湧現的分支，它有著深刻而豐富的理論成果和廣泛的套用背景。複雜網路是一個新興的熱門研究領域，而圖論是其研究所依賴的主要數學基礎理論之一。本項目將研究圖的染色理論中的幾個經典問題，首次提出並研究圖的無圈點蔭度和無圈蔭度，探索圖的染色理論與方法在網路研究中的套用。我們力求確定一些大的圖類的全色數、列表邊（或全）色數、線性蔭度、無圈（點）蔭度等，解決或部分解決相關的幾個著名猜想，設計出好的算法並套用於複雜網路的結構分析中。本項目所研究的內容一部分是經典的染色問題，一部分是我們提出的新問題，還有一部分是上述理論在複雜網路中的套用，內容涉及圖論、矩陣論、規劃論、機率論、組合拓樸、複雜網路等領域，問題的解決對圖的染色理論、網路最佳化等有較大的促進作用。
結題摘要
在本項目三年的執行期內，項目組成員按照項目書中的計畫，主要圍繞幾個著名的猜想研究了圖的全染色、列表染色、線性蔭度等問題，刻畫了圖的結構性質，並利用圖論的思想方法對複雜網路進行了研究。項目組成員共發表了與本項目相關的SCI論文23篇，成功申請國家級及省部級科研項目5項，取得了項目的預期研究成果，超額完成了預期的研究任務。 (1) 在全染色方面，我們主要圍繞全染色猜想展開研究，證明了除了最大度Δ=6的情形以外，全染色猜想對於可嵌入到歐拉示性數為非負的曲面上的圖是成立的。更進一步，對於其他一些有最大度和圈長限制的圖類，我們還得到了其全染色數。(2) 在列表染色方面，我們主要圍繞列表染色猜想和列表全染色猜想展開研究，得到了一些較大圖類的列表邊色數和列表全色數。(3) 在蔭度方面，我們主要圍繞線性蔭度猜想展開研究。對於可嵌入到歐拉示性數為非負的曲面上的圖，我們徹底解決了線性蔭度猜想。另外，在一定限制條件下，我們還確定了圖的線性蔭度。（4）在複雜網路方面，項目組成員基於圖論的理論方法對社區網路、社會網路等實際網路進行了研究。對於社區網路，我們提出了一個有效的雙最短路策略去避免信號擁堵，計算機模擬的結果顯示我們的算法要優於幾個主要的已知方法並且用時較少。另外，我們還研究了社會網路，我們提出了一個模型強調了人的異質性對於信息傳播的影響。
