超圖的橫貫、控制集和匹配研究

《超圖的橫貫、控制集和匹配研究》是依託上海大學，由單而芳擔任項目負責人的面上項目。

基本介紹

• 中文名：超圖的橫貫、控制集和匹配研究
• 項目類別：面上項目
• 項目負責人：單而芳
• 依託單位：上海大學

中文摘要

自從1989年Berge關於超圖的專著問世以來，超圖逐漸成為圖論與組合研究的熱點問題，這是因為超圖在理論上更具有一般意義，同時它在通訊網路、生物網路、數據結構、張量以及各種複雜系統中具有廣泛的套用。而圖的控制集是圖論發展最快的領域之一。本項目研究超圖的控制集、橫貫和匹配以及它們之間的關係。Ryser猜想、Jones猜想和Henning-Yeo猜想是涉及超圖的橫貫數、匹配數和全控制數之間關係的三個重要猜想。本項目將以這幾個猜想為研究目標。從超圖的結構特點出發，藉助超圖與圖之間的相互轉換，利用超圖的控制參數與超圖染色之間的關係，運用組合、機率和線性規劃等方法，給出超圖的橫貫數、全橫貫數、控制數和全控制數的界，確定這些參數之間的內在聯繫，刻畫相應的極值超圖，並分析這些問題在特殊超圖類上的計算複雜性。力爭在這幾個猜想上取得實質性突破。本項目的研究對推動超圖理論發展和在相關領域的套用具有重要意義。

結題摘要

超圖理論在通訊網路，計算機科學，張量理論和博弈論等領域具有廣泛的套用，近年來成為圖論和組合研究的重要內容之一。本課題對超圖的控制集、橫貫、匹配和譜理論進行了研究，涉及超圖中的Ryser猜想等重要問題。證明了秩為r的超圖其控制數不超過它匹配數的(r-1)倍。作為推論，證明了當超圖的控制數和橫貫數相等時，Ryser猜想是成立的。對秩不超圖5的極值超圖給出了刻畫。證明了每個一致的無橋偶度超圖一定存在圈分解，而且每個無橋超圖存在總長度至多為邊數與點數之和減1的圈覆蓋。建立了p-部超圖為極大點連通和極大邊連通的充分條件。這些結論推廣了文獻中關於圖上的相關結論。證明了最大1-邊臨界超圖和最大1-點臨界超圖具有相同的階數。2016年， Katona和Szabo證明了n階k-一致超樹的最大邊數上界，並猜想這個上界是最好可能的，本課題證明了這個猜想是成立的。此外，給出了超樹的匹配多項式的表達式，以此作為工具，對給定直徑和邊數的超樹，對具有較大譜半徑的和較小的兩個譜半徑的超樹給出了刻畫。建立了一致超圖的α-譜半徑按照控制數的下界，並刻畫了達到界的極值超圖。給出了超圖的鄰接張量、Laplacian張量和無符號Laplacian張量的譜半徑的界，這些結論推廣了原來在圖上的相關結論。研究了超圖與合作博弈的交叉研究領域，並取得一些突破性進展，給出了以超圖結構為合作結構的合作博弈的幾個重要分配規則，並對這些分配規則給出了公理化刻畫。