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

【摘要】：一個系統(tǒng)的互連網(wǎng)絡是指該系統(tǒng)中各處理器之間的不同的連接方式.人們通常將互連網(wǎng)絡看作是一個圖,圖中的頂點可以表示互連網(wǎng)絡中的處理器,圖中的邊可以表示處理器之間的通信線路.一個好的網(wǎng)絡,是可以較好的通過它的頂點和邊來進行信息與數(shù)據(jù)的接收和傳遞的.本文探討的k元n立方體,具有很多好的拓撲性質,因此被廣泛用于目前實際應用中的多處理器系統(tǒng)的互連網(wǎng)絡拓撲.多對多不交路覆蓋問題是互連網(wǎng)絡研究領域一個重要的研究課題,它與互連網(wǎng)絡中數(shù)據(jù)的傳遞密切相關.設點集S = {s1,s2,…,sm}和T={t1,t2…,tm}是圖G中兩個包含m個頂點的不相交的集合,若圖G中存在m條互不相交的路Pi,i=1,2…,m,使得每個Pi都連接si和ti且滿足Ui=1mV(Pi)=V(G),則稱P1,P2,…Pm}是圖G的一個多對多m-不交路覆蓋.若對任意的兩個具有m個頂點的集合S和T,圖G都存在多對多m-不交路覆蓋,則稱圖G是多對多m-不交路覆蓋的.隨著科學進步和多處理器系統(tǒng)規(guī)模的不斷擴大,多處理器系統(tǒng)中處理器以及處理器之間的線路出現(xiàn)故障的可能性也越來越大,因此人們對網(wǎng)絡的可靠性的要求也越來越高.對于一個處理器之間的線路出現(xiàn)故障的互連網(wǎng)絡,若其還能有效的傳遞信息和數(shù)據(jù),則稱該互連網(wǎng)絡是具有好的容錯性的.為使故障互連網(wǎng)絡保持良好的信息傳遞能力,研究含有故障邊的互聯(lián)網(wǎng)絡的多對多不交路覆蓋是有意義的.本文主要針對k元n立方體研究了當其含有一定數(shù)目的故障邊時的多對多不交路覆蓋問題.對于k元n立方體Qnk(n≥2,奇數(shù)k≥3),證明了當其故障邊數(shù)最多為2n-4時,Qk-F是二不交路覆蓋的;對于k元3立方體Q3k(奇數(shù)k≥3),證明了當其故障邊數(shù)最多為3條時,它仍然具有二不交路覆蓋性質,且故障邊數(shù)已達到上界;對于k元n立方體Qnk(n≥2,偶數(shù)k≥4),設F是Qnk的故障邊集,證明了當|F|≤2n-m-2時,是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, 鈥，

本文編號：1503202