計算機科學中的若干組合問題研究

《計算機科學中的若干組合問題研究》是依託中國科學技術大學，由徐俊明擔任項目負責人的面上項目。

基本介紹

• 中文名：計算機科學中的若干組合問題研究
• 項目類別：面上項目
• 項目負責人：徐俊明
• 依託單位：中國科學技術大學

中文摘要

本項目主要研究互連網路可靠性和有效性分析中的若干圖論參數：各種限制條件下的連通度、支撐連通度、有界連通度、Menger數、寬直徑、容錯直徑等，它們是度量網路性能的重要參數。這些參數的研究不僅為新一代超大規模並行計算機系統的互連網路設計和分析提供進一步的數學理論基礎和依據，而且進一步充實完善組合網路理論，大大豐富了圖論的研究內容和套用範圍。這些問題的解決和參數的確定大多是NP-hard問題，具有很大的挑戰性。本項目將通過組合和代數分析方法，深入研究網路結構性質，揭示這些參數之間密切關係和內在聯繫，探索變化規律，力爭在理論和方法上取得較大突破，實現擬定的研究目標。在項目實施過程中加強國內外學術交流，普及組合網路新理論和新方法，培養具有創新能力的高水平年輕人才，提高我國組合網路理論研究水平和國際影響。

結題摘要

本項目研究計算機科學中的若干組合問題，順利完成計畫書中擬定的主要研究任務。圖的各種各樣條件連通度和寬直徑是網路容錯性和有效性的重要度量參數。網路故障是不可避免的，故障診斷和由網路故障引起的各種度量參數變化是網路理論研究的重要課題。本項目通過圖的替代乘積和群的半直積構造Cayley圖，弄清了給定限制邊連通度的點可遷圖的存在性，解決了困擾10多年的問題；確定了許多著名網路（如星網路、(n,k) 星網路、超立方體型網路、對偶立方、交換超立方體網路和分層立方網路等）的高階超連通度；建立了在限制條件下的故障診斷數與 2 強點連通度之間的密切關係,從而確定了許多著名網路在限制條件下的診斷數和 2 強點連通度；研究了具有遞歸結構網路的嵌入連通度, 確定了若干網路（如超立方體、星圖等）嵌入點連通度和嵌入邊連通度；研究和確定了正則圖、置換圖、笛卡爾乘積圖等的 2 強邊連通度的脆弱性（即持久度）；證明了變形超立方體網路的點可遷性和圈、路容錯嵌入和容錯超立方體網路多對多不交路問題；利用圖的本原指數, 確定了直積圖的直徑；研究了正則圖的寬直徑；確定了強超立方體網路的容錯直徑和寬直徑。本項目共完成學術論文17 篇,英文版網路理論專著一部。這些研究成果大大豐富和完善了圖的理論,為分析網路性能提供進一步的理論依據。