乘積圖的連通度和容錯直徑的研究.pdf

1、近年來，關(guān)于乘積圖的研究相當(dāng)活躍，其中四種常見乘積圖的結(jié)構(gòu)刻畫與識別算法已經(jīng)建立了優(yōu)雅而比較完備的理論．另外關(guān)于乘積圖的各種圖論變量的研究也始終是一個充滿具有挑戰(zhàn)性問題的領(lǐng)域．2000年，Imrich和Klavzar的專著《Product Graphs》[21]對這些內(nèi)容都作了詳盡的綜述． 連通度是圖論的最基本的參數(shù)之一．在互連網(wǎng)絡(luò)中，連通度以及和連通度相關(guān)的各種概念，比如說極大連通和超連通，是衡量互連網(wǎng)絡(luò)的可靠性和容錯性能的

2、重要參數(shù)．而且實(shí)際中使用的互連網(wǎng)絡(luò)，大多具有乘積圖的結(jié)構(gòu)．研究乘積圖的連通度，在乘積圖理論里面是一個基本的內(nèi)容，而且在互連網(wǎng)絡(luò)中有一定的應(yīng)用價值．直到2003年，關(guān)于各類乘積圖的連通度的研究結(jié)果不多，文獻(xiàn)中可以看到的只有關(guān)于笛卡兒乘積圖的比較粗糙的界． 本文主要研究了四種常見乘積圖(笛卡兒乘積，強(qiáng)乘積，字典乘積圖，直接乘積)和一種廣義乘積圖的連通度和邊連通度． min{λ<,m>V<,p>,λ<,p>v<,m>，δ<,p