基於凱萊圖的互連網路有效控制集與自同構群研究

《基於凱萊圖的互連網路有效控制集與自同構群研究》是依託上海電力大學，由鄧芸萍擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於凱萊圖的互連網路有效控制集與自同構群研究
• 項目類別：青年科學基金項目
• 項目負責人：鄧芸萍
• 依託單位：上海電力大學

項目摘要

隨著新一代信息技術產業的飛速發展，如何最佳化與設計互連網路成為一個非常重要的課題。凱萊圖由於具備良好的性質被廣泛用來作為互連網路的模型。本項目主要研究基於凱萊圖的互連網路的有效控制集和自同構群。運用組合論、圖論及有限群論的方法和技巧，考察交換群上的凱萊圖包括循環圖、對稱群與交錯群上的凱萊圖的有效控制集的存在性，給出有效控制集存在的充分或充要條件，並刻畫存在時的所有有效控制集。針對對稱群與交錯群上的某些重要凱萊圖，利用圖論和置換群論的工具，基於對它們的結構特徵的把握來刻畫出其自同構群。本項目的預期研究成果將有效最佳化基於凱萊圖的互連網路的設計、信息傳播與資源配置，並能考察其對稱性的優劣。項目的研究方法將拓寬對凱萊圖有效控制集及自同構群的研究思路。

結題摘要

凱萊圖由於具備良好的性質被廣泛用來作為互連網路的模型。通過運用圖論及有限群論的方法和技巧，本項目研究了基於凱萊圖的互連網路的有效控制集和自同構群。首先，給出了任意循環圖存在有效（開）控制集的充要條件，並給出了存在時的所有有效（開）控制集構成的集合的上下界範圍，再附加一定的條件，如特定的控制數或度數，刻畫了存在時的所有有效控制集；進一步給出了交換群上滿足一定條件的凱萊圖存在有效開控制集的充要條件；另外，給出了任意頂點子集構成某個循環圖的有效（開）控制集的充要條件。其次，作為星圖和烙餅圖的推廣，定義了對稱群上的一類凱萊圖，並考察了它們的有效控制集的存在性，找出了它們的一些有效控制集，從而得到了它們的控制數；也推導出了它們的頂點子集構成有效控制集的一些必要條件。最後，刻畫了交錯群上的兩類重要凱萊圖的自同構群，也刻畫了對稱群上的兩類凱萊圖即冒泡排序星圖和輪對換圖的自同構群。項目的研究成果能有效最佳化基於凱萊圖的互連網路的設計，項目的研究方法拓寬了凱萊圖有效控制集和自同構群的研究思路。