主題
Search

轉置圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
TranspositionGraph

轉置圖 G_n 是一個 圖，其節點對應於排列，邊對應於僅相差一個轉置的排列 (Skiena 1990, p. 9, Clark 2005)。

轉置圖 G_n 的頂點數為 n!，邊數為 (n; 2)^2(n-2)! (對於 n>1)，並且是度數為 (n; 2) 的正則圖 (Clark 2005)。轉置圖中的所有環都是偶數長度，使其成為二分圖。

多重集的轉置圖總是哈密頓圖 (Chase 1973)。

特殊情況總結在下表中。

nG_n
1單例圖 K_1
22-路徑圖 P_2
3效用圖 K_(3,3)
4Reye 圖

另請參閱

排列, 轉置

使用 探索

參考文獻

Chase, P. J. "Transposition Graphs." SIAM J. Comput. 2, 128-133, 1973.Clark, D. "Transposition Graphs: An Intuitive Approach to the Parity Theorem for Permutations." Math. Mag. 78, 124-130, 2005.Ganesan, A. "Automorphism Group of the Complete Transposition Graph." 27 Apr 2014. https://arxiv.org/abs/1404.7363.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 9-10, 1990.

在 中引用

轉置圖

引用為

Weisstein, Eric W. “轉置圖。” 來自 —— 資源。 https://mathworld.tw/TranspositionGraph.html

主題分類