交換折疊超立方體的連通度

蔡學鵬，楊 偉，任佰通，馮苗苗

（新疆農業大學數理學院，新疆，烏魯木齊 830052）

0 引言

隨著計算機的飛速發展，信息化和數字化技術的不斷進步，許多實際問題的數學模型使離散型結構上的數字化技術得到了更多人的關注，圖的連通度理論[1-7]作為離散數學的一個重要的組成部分。多處理器系統由兩個或兩個以上的處理器構成，處理器交換各種信息是用消息協議通過互聯網絡傳播的。在大規模集成(VLSI)技術和圓片規模集成技術(WSI)領域的最新進步已經能使含有非常多的處理器數量的處理器系統實現信息交流。因為增加的多處理器系統中處理器的數量、多處理器系統的可靠性和容錯性的研究已經成為一個活躍的熱門的研究領域，因此受到了國際數學界與工程界越來越廣泛的重視。

本文僅考慮有限的、無向的、簡單的并且連通的圖[1,8-9]。

設G=G(V,E)是一個圖。對于圖G中兩個子圖H和K，記是點集誘導的子圖。設NH(K)是在H中且與K中的點相鄰的點的集合。特殊地，如果K={v}，可記作NH(v)。設是點v在圖G中的度，設NG[v]=NG(v)∪{v}。如果不產生歧義，我們可省略下標即記為d(v),N(v),N[v]。δ(G)=表示圖G的最小度。

設S?V(G)(或者S?E(G))，如果G-S是不連通的或者平凡的，則稱S是圖G的一個點割（或者邊割）。連通度（或者邊連通度）是衡量網絡可靠性的一個重要參數。圖G的連通度κ(G)（或者邊連通度λ(G)）是圖G中最小點割（或者邊割）的基數。我們知道κ(G)≤λ(G)≤δ(G)，并且κ(G)（或者λ(G)）越大圖G就越可靠。

互聯網絡的拓撲結構經常被表示成一個連通的圖，其中圖的點和邊分別表示互聯網絡的處理器和互聯網絡的連接線[9]。……