主题
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.net.cn/TranspositionGraph.html

主题分类