圖的結構性質、參數及參數化複雜性問題研究

《圖的結構性質、參數及參數化複雜性問題研究》是依託湖北大學，由劉慧清擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的結構性質、參數及參數化複雜性問題研究
• 項目類別：面上項目
• 項目負責人：劉慧清
• 依託單位：湖北大學

項目摘要

結構圖論、極值圖論是圖論及其套用中重要的研究方向，對圖的結構問題的研究不但有重要的理論意義，而且在計算機科學、生命科學、管理科學和運籌學等學科中有很強的套用背景。本項目擬在我們長期從事結構圖論、極值圖論研究的基礎上，對圖中某些特定結構子圖的存在性以及與之相關的有實際套用背景的問題進行研究，探討圖G在滿足一定條件下周長和差數diff的下界和具有某些稀有性質的圖，如含禁用minor圖或者有界度的連通圖的周長和差數；通過研究參數和圖的結構性質之間的關係，發現一些新的結構性定理；通過研究具有某些特定結構子圖的圖的性質，獲得某些具有套用背景的參數的極值；研究圖的參數化複雜性（parameterized complexity）問題及其在網路中的套用。本項目是對圖論問題及其套用之間的交叉研究,該項目的研究將推動這些領域理論研究的發展和加深對一些NP-完全問題的理解和實現。

結題摘要

本項目研究了圖的結構性質，圖的若干參數及相關的極值問題和構造性問題。通過對圖的結構性質的刻畫，運用圖譜分析的方法，給出一個圖具有Hamilton圈的譜條件；結合研究圖的圈結構和路系統的方法, 給出了一個連通圖包含支撐掃帚的度條件；針對網路編碼圖的結構的關係，研究了無向圖的線性guessing number的性質以及某些具有套用背景的網路的容錯性和匹配性；結合極值圖論和代數圖論的方法，研究圖譜與圖的結構參數之間的關係，在圖的鄰接譜以及（無符號）拉普拉斯譜與圖的邊連通度、圍長、直徑、半徑、獨立數以及控制數等參數之間建立了聯繫，進而給出了圖的譜參數和圖論的一些經典參數的關係；也刻畫了一些圖類中圖的鄰接矩陣或無符號拉普拉斯矩陣的特徵值達到最大或最小時的極圖。通過引進一些新的圖類運算，探討了圖的結構的變化對參數以及參數之間的變化影響，結合代數方法，給出了賦權圖和一致超圖的譜參數和一些有套用背景的參數的新的界；提出一種一致性方法來處理不同格圖的漸進拓撲指標問題，證明了格圖的點拓撲指標、點平均關聯能量的大小和點平均擬拉普拉斯能量的大小都是獨立於它們的環形、柱形、自由邊界條件的。這些研究推動了結構圖論和極值圖論以及與其他學科的交叉研究的發展。