《彩虹連通數的算法複雜性和極圖問題的若干研究》是依託華僑大學，由陳莉莉擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：彩虹連通數的算法複雜性和極圖問題的若干研究
- 項目類別：青年科學基金項目
- 項目負責人：陳莉莉
- 依託單位：華僑大學
項目摘要,結題摘要,
項目摘要
彩虹連通數的概念是由Chartrand等學者於2008年提出來的，它是經典連通度的加強，在信息傳輸和網路安全中有非常重要的作用。Chakraborty等學者證明確定一般圖的彩虹連通數是NP-困難的，因此從上界、近似算法等角度研究圖的彩虹連通數是非常有意義的，也吸引了許多國內外圖論專家的關注和研究，如Caro，Tuza，Frieze等。雖然彩虹連通數的研究取得了豐富的結果，但還有眾多重要問題亟待解決，這一課題仍將是圖論學者研究的熱點問題之一。. 本項目主要從以下三個方面研究圖的彩虹連通數：1. 從特殊圖入手，考慮特殊圖的彩虹連通數的算法複雜性；2. 從算法角度考慮一般圖，探索求解一般圖的彩虹連通數的好的近似算法；3. 借鑑極值圖論中極圖的刻畫方法，研究極小彩虹連通圖的性質，並探索其結構特點，力爭給出其結構刻畫。
結題摘要
圖染色問題是圖論研究的熱點問題之一，具有重要的理論價值和實際意義。彩虹連通數是經典連通度的加強，在信息傳輸和網路安全中有非常重要的作用。強邊染色和DP-染色分別是經典邊染色和列表染色的推廣，在實際生活中也有廣泛套用。因此對這些圖染色的研究是非常有意義的。 本項目在國家自然科學基金委的資助及項目成員的共同努力下，完成了項目的主要目標，但在研究內容上略有調整。目前，項目組得到的主要結果有： （1）我們研究了廣義 Petersen 圖P(n,k)的結構，給出P(n,1)的彩虹（頂點）連通數的精確值以及P(n,1)，P(n,2)，P(n,3)的[1,2]-控制數； （2）我們解決了李莎莎等關於廣義連通度的算法複雜性的一個猜想，同時給出一個求廣義邊連通度的多項式時間算法； （3）我們研究了圍長較大的平面圖及邊權較小的圖的強邊色數的界；給出了DP-4-可染圖的兩個充分條件。
