發(fā)布時間：2023-03-26 19:52

　　當(dāng)今的超級計算機(jī)包括成千上萬的處理器,它們都是大規(guī)模并行系統(tǒng)�；ミB網(wǎng)絡(luò)是設(shè)計超級計算機(jī)過程中必不可少的組成部分,在很大程度上決定并行計算機(jī)的性能。在選擇互連網(wǎng)絡(luò)時,如何選擇一個合適且高效的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是現(xiàn)在急需解決的問題。在這樣的背景下,廣大學(xué)者相繼設(shè)計了各式各樣的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。但是如何衡量一個網(wǎng)絡(luò)的優(yōu)劣,且衡量這個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)劣需要參考什么參數(shù)的問題相繼出現(xiàn)。人們希望通過比較這些互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的相關(guān)參數(shù)來找出一種較優(yōu)的互連方式,從而設(shè)計出更好的計算機(jī)系統(tǒng)。消圈數(shù),也稱反饋數(shù),是衡量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)性能優(yōu)劣的重要參數(shù)之一。它作為圖論研究中最經(jīng)典的問題之一,已經(jīng)在計算機(jī)科學(xué)、互連網(wǎng)絡(luò)和通信等領(lǐng)域中有極其重要的應(yīng)用。求解圖的消圈數(shù)問題屬于NP-hard問題。但到目前為止已經(jīng)給出消圈數(shù)的圖類還較少,甚至已給出較好消圈數(shù)界的圖類也不多。尤其是一些較復(fù)雜的圖類(包括有重要應(yīng)用前景的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖)的消圈數(shù)問題還有待進(jìn)一步解決。本文將求解圖的消圈數(shù)問題轉(zhuǎn)化為構(gòu)造圖的含有盡可能多的頂點(diǎn)的可遞推無圈子圖的問題,采用數(shù)學(xué)構(gòu)造與計算機(jī)分支限界搜索交互的方法,通過反復(fù)交互來完成數(shù)學(xué)構(gòu)造,最后用數(shù)學(xué)...

【文章頁數(shù)】：80 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 消圈數(shù)問題的研究現(xiàn)狀
    1.3 研究內(nèi)容與文章結(jié)構(gòu)
第二章 基礎(chǔ)理論概述
    2.1 基礎(chǔ)概念
        2.1.1 圖論的基本概念
        2.1.2 圖的消圈集
    2.2 互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計的基本方法
        2.2.1 笛卡爾乘積方法
        2.2.2 Cayley方法
        2.2.3 線圖方法
第三章 平衡超立方體網(wǎng)絡(luò)的消圈數(shù)研究
    3.1 平衡超立方體網(wǎng)絡(luò)的定義與性質(zhì)
    3.2 平衡超立方體網(wǎng)絡(luò)的無圈點(diǎn)集構(gòu)造
        3.2.1 當(dāng)n≤5時無圈點(diǎn)集的構(gòu)造
        3.2.2 當(dāng)n≥6時無圈點(diǎn)集的構(gòu)造
    3.3 平衡超立方體網(wǎng)絡(luò)的消圈數(shù)
    3.4 小結(jié)
第四章 Kn(?)del圖的消圈數(shù)研究
    4.1 Kn(?)del圖的定義與性質(zhì)
    4.2 Kn(?)del圖的無圈點(diǎn)集構(gòu)造
        4.2.1 特殊情況無圈點(diǎn)集的構(gòu)造
        4.2.2 W_5,n無圈點(diǎn)集的構(gòu)造
    4.3 Kn(?)del圖的消圈數(shù)
    4.4 小結(jié)
第五章 Goldberg Snarks及其相關(guān)圖的消圈數(shù)研究
    5.1 Goldberg Snarks及其相關(guān)圖的定義
    5.2 Goldberg Snarks及其相關(guān)圖的無圈點(diǎn)集構(gòu)造
        5.2.1 G_n和Gn
*的無圈點(diǎn)集的構(gòu)造
        5.2.2 TG_n和TGn
*的無圈點(diǎn)集的構(gòu)造
    5.3 Goldberg Snarks及其相關(guān)圖的消圈數(shù)
    5.4 小結(jié)
結(jié)論與展望
參考文獻(xiàn)
攻讀碩士學(xué)位期間發(fā)表的學(xué)術(shù)論文
致謝



本文編號：3771611

suoshi