兩類(lèi)互連網(wǎng)絡(luò)的邊容錯(cuò)直徑.pdf

1、隨著科學(xué)技術(shù)的飛速發(fā)展，計(jì)算機(jī)系統(tǒng)需要處理的信息和數(shù)據(jù)日益龐大。這樣就對(duì)計(jì)算機(jī)系統(tǒng)的性能提出了很高的要求，其內(nèi)部各處理器的網(wǎng)絡(luò)設(shè)計(jì)也成為了一個(gè)亟待解決的問(wèn)題。實(shí)踐證明，圖論是設(shè)計(jì)和分析互連網(wǎng)絡(luò)的最基本且強(qiáng)有力的數(shù)學(xué)工具。互連網(wǎng)絡(luò)一般可以被看成為一個(gè)簡(jiǎn)單無(wú)向圖，圖中的頂點(diǎn)表示網(wǎng)絡(luò)中的結(jié)點(diǎn)，圖中的邊表示各結(jié)點(diǎn)之間的通信連線。這樣，就可以用數(shù)學(xué)語(yǔ)言來(lái)研究和分析一些復(fù)雜的網(wǎng)絡(luò)問(wèn)題。其中，圖的直徑可以刻畫(huà)網(wǎng)絡(luò)的通訊狀態(tài)，考察直徑的變化就成為了分析

2、網(wǎng)絡(luò)傳輸延遲的重要方法。在第二章，我們對(duì)一些基本概念以及圖和網(wǎng)絡(luò)的相關(guān)性作了系統(tǒng)的說(shuō)明。另一方面，由于網(wǎng)絡(luò)的結(jié)點(diǎn)和連線都有可能發(fā)生故障，因此，容錯(cuò)網(wǎng)絡(luò)的研究和設(shè)計(jì)是引起了許多人的關(guān)注。點(diǎn)容錯(cuò)直徑和邊容錯(cuò)直徑則是度量網(wǎng)絡(luò)可靠性和有效性的兩個(gè)重要參數(shù)，它們分別是考慮故障只發(fā)生在結(jié)點(diǎn)和故障只發(fā)生在連線的情形，這方面的基本情況在第三章有詳細(xì)的描述。通過(guò)連接一些低維網(wǎng)絡(luò)來(lái)構(gòu)建高維網(wǎng)絡(luò)，這是設(shè)計(jì)大型互連網(wǎng)絡(luò)的一個(gè)重要方法，許多著名的網(wǎng)絡(luò)都可以用這種