Bubble-sort圖的κ-限制邊連通度.pdf

1、我們經(jīng)常用圖G=(V, E)代表互連網(wǎng)絡，從互連網(wǎng)絡的大規(guī)模多元信息處理機系統(tǒng)中可得到一些基礎拓撲性質.在一個大規(guī)模多元信息處理系統(tǒng)中，元件故障是不可避免的.因此，互連網(wǎng)絡的容錯能力成為一個被廣泛研究的關鍵因素.邊連通度是測量互連網(wǎng)絡容錯性的一個重要參數(shù).然而，在一個大規(guī)模多元信息處理系統(tǒng)中，與一些點相關聯(lián)的所有邊同時出現(xiàn)故障的可能性是很小的.因此，用k-限制邊連通度去度量網(wǎng)絡的可靠性就顯得尤為重要.一個連通圖G的k-限制邊連通度是使得

2、G-F不連通且G-F的每個分支至少有k個頂點的最小邊子集F的基數(shù).特別地，圖G的2-限制邊連通度也叫做限制邊連通度，簡記為λ'(G).
　　在高性能并行與分布系統(tǒng)中，Bubble-sort圖（簡記為Bn）是一個具有一些諸如對稱性和遞歸結構等好的拓撲性質的互連網(wǎng)絡.Bn（n≥1）是含有n!個頂點的圖，每個頂點x可表示為x=x1x2…xn，1≤xi≤n且xi≠xj，1≤i，j≤ n.兩個頂點x=x1x2…xn和y=y1y2…yn.相鄰

3、當且僅當存在整數(shù)1≤i≤n-1使得xi=yi+1，xi+1=yi且xj=yj，j∈{1，2，…，n}\{i，i+1}.
　　在本文中，我們主要研究Bubble-sort圖的k-限制邊連通度，其中k∈{2，3，4}.本文分為四章:
　　在第一章，我們介紹了一些本文將要用到的有關圖論方面的基本概念和記號.
　　在第二章，我們研究了Bubble-sort圖的限制邊連通度.主要結果如下:
　　設Bn(n≥3）是Bubbl

4、e-sort圖，λ'(Bn）是Bn的限制邊連通度.則λ'（Bn）=2n-4.
　　在第三章，我們研究了Bubble-sort圖的3-限制邊連通度.主要結果如下:
　　設Bn(n≥3）是Bubble-sort圖，λ3（Bn）是Bn的3-限制邊連通度.則λ3（Bn）=3n-7.
　　在第四章，我們研究了Bubble-sort圖的4-限制邊連通度.主要結果如下:
　　設Bn(n≥4)（Bn）是Bubble-sort圖，