幾類互連網路拓撲結構圖的交叉數算法及其套用研究

《幾類互連網路拓撲結構圖的交叉數算法及其套用研究》是依託大連理工大學,由楊元生擔任項目負責人的面上項目。

基本介紹

• 中文名：幾類互連網路拓撲結構圖的交叉數算法及其套用研究
• 依託單位：大連理工大學
• 項目類別：面上項目
• 項目負責人：楊元生

項目摘要

圖G的交叉數cr(G)是圖的一個拓撲不變數，它是衡量圖的非平面性的一個重要量度。研究互連網路拓撲結構圖的交叉數有助於確定網路交叉數和為制定該網路的VLSI線路所需要的平面布局二者之間的關係，以降低晶片造價。確定一個圖的交叉數是NP困難問題，研究它對解決一般NP困難問題有重要的借鑑意義。. 本項目將研究幾類重要網際網路拓撲結構圖(包括n-維星圖Sn、薄餅圖 Pn、冒泡排序圖Bn、排列圖An,k、交錯群圖AGn、(n,k)-星圖Sn,k)的交叉數，以此研究一般網際網路拓撲結構圖的交叉數的性質；同時，研製出較好的計算網際網路拓撲結構圖的交叉數算法與計算網際網路拓撲結構圖的交叉數的上界的算法。.本項目的研究將豐富利用計算機算法解決圖論問題的理論成果，對圖的交叉數在網際網路的拓撲設計、電子線路板的設計等領域的研究有重要的理論意義和套用價值。

結題摘要

圖G的交叉數cr(G)是圖的一個拓撲不變數，它是衡量圖的非平面性的一個重要量度。交叉數的研究是拓撲圖論的一個中心問題，在過去的三十年里，包括Erdos, Guy, Turan, Tutte 等在內的一批著名的數學家都對圖的交叉數進行過深入的研究。過去的研究成果表明，圖的交叉數的研究在離散及計算幾何領域有重要的套用，而且在超大規模積體電路和網路布線問題方面也有重要的套用。研究互連網路拓撲結構圖的交叉數有助於確定網路交叉數和為制定該網路的VLSI線路所需要的平面布局二者之間的關係，以降低晶片造價。確定一個圖的交叉數是NP困難問題，研究它對解決一般NP困難問題有重要的借鑑意義。本項目研究了幾類重要網際網路拓撲結構圖(包括n-維星圖Sn、薄餅圖 Pn、冒泡排序圖Bn、排列圖An,k、交錯群圖AGn、(n,k)-星圖Sn,k)的交叉數，以此研究一般網際網路拓撲結構圖的交叉數的性質；同時，研製出了較好的計算網際網路拓撲結構圖的交叉數算法與計算網際網路拓撲結構圖的交叉數上界的算法。 本項目的研究豐富了利用計算機算法解決圖論問題的理論成果，對圖的交叉數在網際網路的拓撲設計、電子線路板的設計等領域的研究有重要的理論意義和套用價值，為後續研究以及更為複雜的互連網路拓撲圖的交叉數性質的研究提供了有效途徑和研究方法，為圖的交叉數問題在互連網路的實際套用提供更堅實的理論基礎。