圖的若干參數及算法研究

《圖的若干參數及算法研究》是依託浙江師範大學，由呂新忠擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的若干參數及算法研究
• 項目類別：面上項目
• 項目負責人：呂新忠
• 依託單位：浙江師範大學

項目摘要

圖的控制數與染色數是圖的兩個重要參數，在現代計算機科學、信息科學、管理科學等領域有著十分廣泛的套用，得到了國內外同行的極大關注。本項目研究圖的各種控制數、染色數及其算法，如圖的控制數、符號控制數、減符號控制數、圖的平方染色、Harmonious染色等。圍繞著名的Vizing's猜想和Haynes猜想展開對圖的控制數、Harmonious染色的重點研究，力爭完全解決Haynes猜想，擴展滿足Vizing猜想的圖類。給出圖的控制數、平方色數、Harmonious色數一些可達的界，對於一些特殊圖類計算出符號控制數、平方色數、Harmonious色數的精確值，並設計高效可行的近似多項式時間算法。給出圖與其補圖的全符號控制數、減符號控制數、Harmonious色數的Nordaus-Gaddum不等式。擬四年內完成論文至少20篇.

結題摘要

圖的控制數與標號是圖的重要參數，在現代計算機科學、信息科學、管理科學等領域有著十分廣泛的套用。本項目基本上按原項目計畫執行，四年來，項目組成員主要研究圖的控制數、圖的符號控制數、圖的減符號控制數、圖的邊符號控制數、圖的團符號控制數、圖的L（p,q）-標號、圖的L（2,1）-標號、圖論算法及其套用等問題。證明了四正則圖、五正則圖和K正則圖的Upper減控制數的下界，且這些界是可達的，構造出了滿足下界的圖類；定義了圖的團符號控制數，構造出了一般圖的團符號控制函式，證明了一般圖的團符號控制函式的界，並對一些特殊圖類，得到了它們的團符號控制數的精確值，這些結果豐富改進了圖的控制理論現有的研究結果，拓展了圖的控制理論的研究範圍。以G.Wenger 猜想為主要目標，研究圖的L（p,q）-標號，力求改進M.Molloy 和 M.R.Salavatipour 給出的上界，擴展滿足G.Wenger 猜想的圖類，得到了不含4-9圈的平面圖的L（p,q）-標號、圍長至少為6的平面圖的L（p,q）-標號、最大度至多為6的的平面圖的L（2,1）-標號，證明了不含4、5、6 圈且無兩個相交三角形的平面圖滿足Wenger 猜想，證明了不含4圈的平面圖滿足Wenger 猜想。利用圖的控制理論和染色理論，研究了交巡警台最佳化設定問題、社會複雜網路成員影響力評價、破損檔案的拼接復原等具有較大社會意義和經濟意義的實際問題。利用圖論最短路算法和和控制數最佳化算法給出了交巡警台的最佳化設定方案，基於圖的TSP算法的改進，給出了一種高效可行的破損檔案的拼接復原的新算法，基於圖的控制理論，研究社會複雜網路成員影響力測量問題，設計了一種快速可行的算法並且在Erdos合作網路上得到了實現。這些算法不但從理論上豐富了理論計算機研究領域的研究內容，有一定的理論意義，而且能夠在實踐中套用，有一定的社會價值和經濟價值。