《圖的平均距離及相關問題研究》是依託蘭州大學，由徐守軍擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的平均距離及相關問題研究
- 依託單位：蘭州大學
- 項目負責人：徐守軍
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
本項目研究圖的平均距離及與之相關問題，主要包括圖的平均距離與其他參數關係、算法問題以及Hosoya多項式、距離嵌入問題。 首先，探討連通圖中平均距離與圖中諸如連通控制數、（連通）樞紐（hub）數、圖的階、半徑、直徑等參數之間關係，並決定極值圖； 第二，分別探討弦圖的平均距離及構造最小平均距離支撐樹和團樹的線性算法；第三，研究Hosoya多項式，包括典型圖上的計算，Hosoya多項式的單峰性和遞推公式等數學性質；最後，為了更有效地計算距離，研究圖的距離嵌入到超立方體圖。圖的平均距離是圖緊湊性的一個自然度量，在通訊網路的設計和分析、化合物物理化學性質研究中扮演重要角色，是該領域一個持續關注方向； 一些挑戰性問題相繼被提出，許多基本問題亟待解決。通過本項目的研究提出有價值的研究方法，解決若干重要問題， 推動平均距離理論和套用的進一步發展。
結題摘要
本課題主要研究是關於圖中基於距離的參數之間關係，極值圖刻畫，參數計算和算法複雜性以及與之相關Hosoya多項式計算及性質等。在四年的資助期， 取得預期成果。 第一，建立參數之間大小關係，並刻畫極值圖及Hosoya多項式計算； 目前建立了平均距離（等價於理論化學中維納指標）和連通樞紐數、連通控制數之間關係， 給出了一般圖上平均距離關於這兩個參數的緊上界，並刻畫達到緊上界的極值圖；把關於離心距離和（另一個重要拓撲指標）的一個猜想推進一步； 另外，分別給出了原冠狀苯系統的完全強迫數和典型圖類上全局強迫數的分析表達式、一般圖上全局強迫數的緊上下界、幾類典型圖類上的Hosoya多項式的具體分析表達式、隨機亞苯基鏈的Hosoya多項式期望值的分析表達式；第二，研究了關於一般序列單峰性的問題，證明了沒有W_5-e作為導出子圖的余可比圖循環數為2， 部分解決了猜想；證明了典型凱萊圖的可擴數。 第三，關於重要參數：控制數及變形參數的研究，並取得較好科研成果。主要有3個方面：1. 關於點控制參數，統一了經典控制參數和羅馬控制參數並建立之間大小關係， 刻畫極值樹，證明了對於任意k， 羅馬{k}-控制數問題分別在二部平面圖和二部弦圖上都是NP-完全的，刻畫了2-控制數與羅馬{2}-控制數相等的樹，給出了有限非阿貝爾群上定義的半凱萊圖中存在獨立完美控制集的充要條件; 2. 邊控制參數，證明了全邊控制數問題在度小於4的二部圖上是NP-困難的，通過邊控制數給出樹的全邊控制數的上下緊界，證明了判斷圖的邊控制數和半全邊控制數相等、邊控制數和全邊控制數相等問題都是NP-困難的，分別刻畫了滿足邊控制數和半全邊控制數相等、邊控制數和全邊控制數相等的樹，證明了樹上2-彩虹邊控制數和羅馬{2}-邊控制數相等，刻畫2-彩虹邊控制邊和邊控制數相等的樹；3.控制臨界圖性質方面，證明了，對於任意整數t＞2,如果3-連通的3-連通控制臨界圖G最小度大於t-2, 沒有K_{1, t}作為導出子圖，那么，G是雙臨界的；給出了k-全控制臨界圖G的一些性質，例如，diam(G)＜ 2k-2, 刻畫了2-全控制臨界圖和3-全控制臨界圖， 刻畫了不是雙臨界的3-連通、3-控制臨界圖。培養的畢業生7名，在讀博士6名、碩士9名；完成24篇論文，發表11 篇，投稿8篇，正在準備5篇。舉辦會議1次，參加會議20餘人次，邀請專家近40人。
