《有向圖及網路的曲面嵌入虧格問題的研究》是依託北京交通大學，由郝榮霞擔任項目負責人的面上項目。
基本介紹
- 中文名：有向圖及網路的曲面嵌入虧格問題的研究
- 項目類別：面上項目
- 項目負責人：郝榮霞
- 依託單位：北京交通大學
項目摘要,結題摘要,
項目摘要
有向圖及網路的曲面上的虧格是有向曲面嵌入理論的核心和關鍵，它內容新、理論豐富，且有更普遍的發展前景. 開展對該問題的研究具有重要的科學意義和套用價值。目前人們對它的研究尚處於前期階段，有很多待解決的問題。本項目就是要圍繞有向圖和網路在可定向曲面上的嵌入虧格進行系統和深入的研究，具體內容為：（1）研究一些具有代表性的圖類在曲面嵌入上的虧格，為有向圖的有向可嵌入性的研究打下基礎. （2）有向圖在可定向曲面上的嵌入的性質研究。（3）推廣確定圖在可定向曲面上虧格的各種方法到有向圖的有向嵌入上；計算有向圖在可定向曲面上的嵌入虧格.（4）研究網路的圈，路嵌入性及其最小虧格. 這些定性研究不僅能深刻地揭示有向圖及網路的曲面嵌入的內在特徵，而且也為今後研究圖,有向圖和網路的潛在套用提供必要的理論基礎.
結題摘要
圖的嵌入和網路容錯是國際上非常活躍的研究領域，在多重系統和信息安全領域有著廣泛的套用。本項目致力於網路的路，圈嵌入性，有向圖在可定向曲面的虧格以及網路的容錯性，診斷度等的研究，取得了系列創新成果。圖的虧格問題是本課題的重點和難點問題之一。在這方面，關於歐拉有向競賽圖，我們證明了有向圖的有向嵌入和對應的無向圖的面二可著色嵌入的一一對應關係，得到了階n的完全圖存在一種定向使得競賽圖的有向虧格和無向完全圖虧格相同的充分必要條件，此結果回答了Bonnington於2002年在組合界頂級期刊 JCTB上提出的一個公開問題。網路容錯嵌入是本項目另一個研究重點。本項目對超立方體，摺疊超立方體，平衡超立方體等圖類，分別研究了邊容錯圈嵌入和點容錯圈嵌入問題。在泛圈性，路覆蓋，容錯圈嵌入和容錯泛圈性方面取得重要進展。如：有五篇文章發表在信息科學頂級雜誌Information Sciences上。另外，本項目還在圖的群作用，外連通度，網路的g-好鄰診斷，條件診斷度和悲觀診斷度方面取得一些列理想成果。對一般正則圖類的條件診斷度和悲觀診斷度的結果是目前得到的僅有的適應多個網路的成果之一。作為結果的推論，我們可以得到Fan等在IEEE Trans. Comput. 上關於星圖網路的悲觀診斷和Tsai在Inform. Process. Lett.上關於交錯群圖的悲觀診斷等結果。另外，本課題對Berge-Fulkerson猜想進行研究，給出了滿足Berge-Fulkerso猜想的某些圖類的刻畫，推出多個無限類的Snarks關於猜想的正確性。課題的研究結果分別發表在著名SCI刊物Information Sciences, Applied Mathematics and Computation, Journal of Graph Theory等。 本項目部分資助了3次國際會議，其中2014年8月召開的國際數學家大會《組合與圖論》衛星會議，300餘人參加。2017年6月的《圖論與組合網路國際學術會議》來自中國、美國、澳大利亞、以色列和韓國等國117名專家學者參加。資助項目組成員到國外大學進行合作研究或參加國際會議10餘次，參加國內學術會議20餘次，其中申請人多次做會議邀請報告。資助國外同行來我校合作研究10餘次。項目還資助4名博士生5名碩士完成學業。發表SCI科研論文25篇。
