主題
Search

排列星形圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

在數學、計算機科學和資訊處理領域，有幾種被稱為“星形圖”的圖。最常見的星形圖是 n-星形圖 S_n，定義為完全二分圖 K_(1,n-1)。

一種完全不同的 n-星形圖，這裡稱為 n-排列星形圖 PS_n（等同於 A_(n,n-1)-排列圖），被定義為頂點是 n! 個排列的圖，其中當兩個排列透過交換一對元素相關聯時，頂點之間透過邊連線（Akers 等，1987；Akl 和 Qiu，1991；Palis 等，1994；Rajasekaran 和 Wei，1997）。這種圖是 正則 的，頂點度數為 n-1，圖直徑為 |_3(n-1)/2_|（Akers 等，1987；Rajasekaran 和 Wei，1997），其中 |_x_| 是向下取整函式。它們也是頂點傳遞的、邊傳遞的和弧傳遞的。

Chiang 和 Chen（1995）考慮了 S_(n,k) 對 n-排列星形圖的推廣。這種型別的圖包括 n-排列星形圖 PS_n（以及因此的排列圖 A_(n,n-1)）作為特例 S_(n,n-1)。

排列星形圖 S_(n,k) 是正則的，頂點度數為 n-1，具有 頂點計數 n!/(n-k)!，圖直徑為

d(S_(n,k))={2k-1 for k<=|_n/2_|; |_(n-1)/2_|+k for k>=|_n/2_|+1
(1)

（Chiang 和 Chen，1995）。當 k!=n-1 時，S_(n,k) 是頂點傳遞的，但既不是邊傳遞的也不是弧傳遞的。

（n,k）-排列星形圖在 Wolfram 語言中實現為GraphData[{"PermutationStar", {n, k}}].

PermutationStarGraph

特殊情況如上圖所示，並在下表中進行了總結。

(n,k)S_(n,k)
(1,0)單點圖 K_1
(2,1)路徑圖 P_2
(3,2)環圖 C_6
(4,2)截角四面體圖
(4,3)Nauru 圖 GP(12,5)
(n,n-1)排列圖 A_(n,n-1)

另請參閱

交錯群圖, 排列圖, 排列圖, 星形圖

使用 探索

參考文獻

Akers, S.; Harel, D.; and Krishnamurthy, B. "The Star Graph: An Attractive Alternative to the n-Cube." In Proc. International Conference of Parallel Processing, pp. 393-400, 1987.Akl, S. G. and Qiu, K. "Data Communication and Computational Geometry on the Star and Pancake Interconnection Networks." Technical Report TR 91-301, Dept. of Computing and Information Science, Queen's University at Kingston, Ontario, Canada. May 1991.Chiang, W.-K. and Chen, R.-J. "The (n,k)-Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.Palis, M.; Rajasekaran, S.; and Wei, D. S. L. "Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks." J. Parallel Distrib. Comput. 20, 145-157, 1994.Rajasekaran, S. and Wei, D. S. L. "Selection, Routing, and Sorting on the Star Graph." J. Parallel Distrib. Comput. 41, 225-233, 1997.

在 中被引用

排列星形圖

引用為

Weisstein, Eric W. “排列星形圖。” 來自 -- 資源。 https://mathworld.tw/PermutationStarGraph.html