本文關(guān)鍵詞： 互連網(wǎng)絡(luò) k元n立方體 容錯(cuò)性 多對(duì)多不交路　出處：《太原科技大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：一個(gè)系統(tǒng)的互連網(wǎng)絡(luò)是指該系統(tǒng)中各處理器之間的不同的連接方式.人們通常將互連網(wǎng)絡(luò)看作是一個(gè)圖,圖中的頂點(diǎn)可以表示互連網(wǎng)絡(luò)中的處理器,圖中的邊可以表示處理器之間的通信線路.一個(gè)好的網(wǎng)絡(luò),是可以較好的通過它的頂點(diǎn)和邊來進(jìn)行信息與數(shù)據(jù)的接收和傳遞的.本文探討的k元n立方體,具有很多好的拓?fù)湫再|(zhì),因此被廣泛用于目前實(shí)際應(yīng)用中的多處理器系統(tǒng)的互連網(wǎng)絡(luò)拓?fù)?多對(duì)多不交路覆蓋問題是互連網(wǎng)絡(luò)研究領(lǐng)域一個(gè)重要的研究課題,它與互連網(wǎng)絡(luò)中數(shù)據(jù)的傳遞密切相關(guān).設(shè)點(diǎn)集S = {s1,s2,…,sm}和T={t1,t2…,tm}是圖G中兩個(gè)包含m個(gè)頂點(diǎn)的不相交的集合,若圖G中存在m條互不相交的路Pi,i=1,2…,m,使得每個(gè)Pi都連接si和ti且滿足Ui=1mV(Pi)=V(G),則稱P1,P2,…Pm}是圖G的一個(gè)多對(duì)多m-不交路覆蓋.若對(duì)任意的兩個(gè)具有m個(gè)頂點(diǎn)的集合S和T,圖G都存在多對(duì)多m-不交路覆蓋,則稱圖G是多對(duì)多m-不交路覆蓋的.隨著科學(xué)進(jìn)步和多處理器系統(tǒng)規(guī)模的不斷擴(kuò)大,多處理器系統(tǒng)中處理器以及處理器之間的線路出現(xiàn)故障的可能性也越來越大,因此人們對(duì)網(wǎng)絡(luò)的可靠性的要求也越來越高.對(duì)于一個(gè)處理器之間的線路出現(xiàn)故障的互連網(wǎng)絡(luò),若其還能有效的傳遞信息和數(shù)據(jù),則稱該互連網(wǎng)絡(luò)是具有好的容錯(cuò)性的.為使故障互連網(wǎng)絡(luò)保持良好的信息傳遞能力,研究含有故障邊的互聯(lián)網(wǎng)絡(luò)的多對(duì)多不交路覆蓋是有意義的.本文主要針對(duì)k元n立方體研究了當(dāng)其含有一定數(shù)目的故障邊時(shí)的多對(duì)多不交路覆蓋問題.對(duì)于k元n立方體Qnk(n≥2,奇數(shù)k≥3),證明了當(dāng)其故障邊數(shù)最多為2n-4時(shí),Qk-F是二不交路覆蓋的;對(duì)于k元3立方體Q3k(奇數(shù)k≥3),證明了當(dāng)其故障邊數(shù)最多為3條時(shí),它仍然具有二不交路覆蓋性質(zhì),且故障邊數(shù)已達(dá)到上界;對(duì)于k元n立方體Qnk(n≥2,偶數(shù)k≥4),設(shè)F是Qnk的故障邊集,證明了當(dāng)|F|≤2n-m-2時(shí),是m-F-不交路覆蓋的,其中1 ≤ m≤2n-2.
[Abstract]:The interconnection network of a system refers to the different ways of connection between the processors in the system. People usually think of the interconnection network as a graph, the vertices in the graph can represent the processors in the interconnection network. The edges in the graph can represent the communication lines between processors. A good network can receive and transfer information and data through its vertices and edges. It has many good topological properties, so it is widely used in the interconnect network topology of multiprocessor systems in practical applications. Many-to-many disjoint coverage problem is an important research topic in the field of interconnection network research. It is closely related to the transmission of data in the interconnection network. The set of points S = {S1 / s2, 鈥，

本文編號(hào)：1503202