圖與地圖的對稱性研究

《圖與地圖的對稱性研究》是依託北京交通大學，由馮衍全擔任項目負責人的面上項目。

基本介紹

• 中文名：圖與地圖的對稱性研究
• 項目類別：面上項目
• 項目負責人：馮衍全
• 依託單位：北京交通大學

項目摘要

利用有限群理論，結合拓撲、組合和圖論方法研究組合結構的對稱性已經成為國際學術界一個非常活躍的研究領域，在信息科學、計算機科學和通信領域有著廣泛的套用。本項目側重研究圖和地圖的對稱性，研究它們的代數性質和結構性質。具體內容如下：本原圖研究，包括點本原圖、點雙本原圖和邊本原圖，特別是長期未解決的四度、五度邊本原圖分類；對稱圖研究，包括給定階的對稱圖分類和自同構群構造，重點是基礎圖和五度對稱圖；半弧傳遞圖研究，包括具有特殊性質的半弧傳遞圖構造與分類，特別是4倍素數階半弧傳遞圖分類等未解決的公開問題；圖的地圖同構類和等價類研究，重點是著名圖類的一般地圖、reflexible地圖和自Petie對偶地圖的同構類計數及正則圖類的地圖等價類泛函方程建立與求解；圖在曲面上嵌入研究，重點是嵌入的最小、最大虧格及虧格分布；網路設計與最佳化研究，重點是凱萊圖網路和陪集圖網路的設計及相關網路參數研究。

結題摘要

本項目致力於群論在圖論中套用，取得了系列創新成果。在邊本原圖分類方面獲得突破，完成4度和5度邊本原圖分類，它是自1973年著名代數圖論專家Weiss完成三度邊本原圖分類以來首次取得的實質性進展，分別發表在組合界頂級雜誌JCTB和代數組合界頂級雜誌JACO。確定圖的全自同構群是代數圖論基礎性研究，其成果被廣泛套用於其它研究領域，本項目研究了弧傳遞圖和雙凱萊圖自同構群：解決了著名代數圖論專家Godsil於1983年提出的公開問題，即2冪階非正規弧正則凱萊圖的存在性；確定了5度對稱圖點穩定化子結構，這是著名圖論大師Tutte於半個世紀前確定3度對稱圖點穩定化子以來得到的一個重要進展。對稱圖分類一直是代數圖論研究熱點，本項目在小度數對稱圖分類方面獲得多項創新成果，特別是最近完成的存在可解弧傳遞自同構子群的連通3度基本圖分類，在發表後不到一年的時間內由Elsevier統計的下載量高達275次。網路設計與最佳化是本項目另一研究重點，我們對平衡立方體、膨脹立方體等著名網路進行了深入探索，在網路泛圈性、網路診斷度、網路連通度方面取得重要進展，如發表在信息科學頂級雜誌Information Sciences的文章推廣了我國著名網路理論專家徐俊明教授等關於平衡立方體網路在泛圈性方面的成果。另外，本項目還在地圖同構類計數、圖的正則覆蓋等方面取得理想成果，特別2倍素數階三度對稱圖的邊傳遞循環和二面體覆蓋圖分類是目前得到的僅有的幾類關於無限圖類正則覆蓋方面成果之一，發表在組合界著名刊物Combinatorica。本項目部分資助了3次國際會議，特別是2014年8月召開的國際數學家大會《組合與圖論》衛星會議，300餘人參加，其中含多名科學院院士，兩名美國科學院院士做大會邀請報告。資助項目組成員到國外大學進行合作研究或參加國際會議10餘次，參加國內學術會議10餘次，其中申請人多次做大會邀請報告，如2014年11月在廣州舉行的第六屆全國組合數學與圖論大會上做大會邀請報告、2015年7月在蘭州舉行的圖與組合算法會議（暨第八屆國際工業與套用數學大會衛星會議）上做大會邀請報告等。資助國外同行來我校合作研究10餘次，國內專家來我校做報告10餘次。項目還資助7名博士生完成學業，發表SCI科研論文24篇。