一平行分散式系統通常可以使用一個圖來表示,在設計一平行分散式 系統有兩個考慮的重點: 通信延遲與容錯傳輸延遲。在平行分散式系 統兩個處理器之間的最大通信延遲可以由其表示的圖的直徑來決定,而圖的直徑會隨著圖上邊的增減而改變。我們證明n 維超立方體可以增加22k–1個邊來降低他的直徑k, 2≤ k ≤ n/2 。 對於容錯傳輸延遲我們探討圖的衍生連通性,我們證明廣義皮特森圖P(n, 3)是全域3*連通若且為若n 為奇數。
A parallel and distributed system is usually represented by a graph. In a parallel and distributed system, we consider two important issues, namely, communication delay and fault tolerant transmission delay. The maximum communication delay between any pair of processors in a parallel and distributed system can be determined by the diameter of its underlying graph. The diameter of a graph can be affected by the addition or deletion of edges. We had shown that an n-dimensional hypercube can be decreased by k with the addition of 22k−1 edges for 2 ≤ k ≤ ⌊n/2⌋. We would like to compute the diameter variability caused by the removal of edges in a hypercube. For fault tolerant transmission delay, we consider the spanning connectivity of a graph. We would like to prove that general Peterson graph P(n, 3) with odd n is globally 3∗-connected which is one factor of spanning connectivity.