圖中路和圈的嵌入問題及相關研究

《圖中路和圈的嵌入問題及相關研究》是依託浙江師範大學，由馬美傑擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖中路和圈的嵌入問題及相關研究
• 項目類別：青年科學基金項目
• 項目負責人：馬美傑
• 依託單位：浙江師範大學

項目摘要

隨著信息科學和計算機科學技術的迅猛發展，圖論和組合數學作為其重要理論基礎得到國際數學界和理論計算機科學界的高度重視和廣泛研究，圖論的思想和方法在網路設計和分析中的套用越來越被科研工作者認可和採用。本項目從圖的結構性質入手，在現有工作基礎上，深入研究以下幾個問題:（一）研究容錯網路圖的路和圈的嵌入問題，力爭解決或部分解決最近提出的關於容錯超立方體網路圈嵌入問題的一個猜想。（二）支撐連通度是新引入的與路的嵌入問題相關的一個參數，研究一些著名網路圖類(如arrangement graph，exchanged hypercube)的支撐連通度。（三）探索支撐連通度與經典連通度之間的關係，試圖推廣經典連通度的一些結果（如一些重要的不等式）到支撐連通度的情形。本項目所研究的問題大多是國際著名學術刊物上提出的新問題，這些研究不僅豐富圖論研究內容，也為大規模互連網路的設計和性能分析提供理論依據。

結題摘要

本項目從圖的結構性質入手,主要研究一些網路圖類的路和圈的嵌入問題、連通性問題、圖的控制數、圖的重構數及圖的雜色子圖劃分等問題。解決了故障點和邊存在的情況下的局部紐立方體中的路的可嵌入問題；確定了金字塔網的對稱性、連通度及在有故障點存在的情況下圈的可嵌入問題；確定了交換超立方體網路的距離性質，如它的Wiener指標，平均距離，寬直徑，容錯直徑等；給出了交換超立方體網路控制數的上下界；確定了整數單純形的寬直徑和容錯直徑；確定了雙星圖、完全多部圖及其補圖的重構數和一致重構數；確定了r邊染色的完全三部圖的雜色樹的劃分數，並給出計算公式；確定了r邊染色的完全圖的雜色樹的劃分數，並給出多項式算法；確定了r邊染色的完全多部圖的雜色樹的劃分數的上下界。本項目所得結果均是創新性研究成果。至今完成學術論文12篇，其中被SCI檢索收錄的有9篇，其餘3篇已經投稿,圓滿完成了本課題所預定的研究任務。