主题
Search

排列图

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook
ArrangementGraph

The (n,k)-排列图 A_(n,k) 定义为顶点集上的图，该顶点集由 顶点集 组成，包含 排列，排列来自 {1,2,...,n} 且最多包含 k 个元素，其中当且仅当两个 排列 在其 k 个位置中的一个位置不同时，顶点通过边连接。 (n,k)-排列图具有 n!/(n-k)! 个节点，是 正则图，顶点度 为 k(n-k)，k(n-k)-连通，具有 图直径 |_3k/2_|，并且是顶点-顶点传递图和 边传递 图 (Day 和 Tripathi 1992)。

排列图 A_(n,2) 是 线图，是 n-冠图。

排列图的预计算属性在 Wolfram 语言 中可用，如GraphData[{"ArrangementGraph", {n, k}}].

A_A_(n,k) 的特殊情况总结在下表中，并在上图中进行了说明。

(n,k)图
(n,1)完全图 K_n
(n,n-1)排列星图 S_(n,n-1)
(n,n-2)交错群图 AG_n
(4,2)正八面体图
(4,3)Nauru 图 GP(12,5)

另请参阅

交错群图, 排列星图

使用 Wolfram|Alpha 探索

参考资料

Day, K. 和 Tripathi, A. "排列图：一类广义星图。" Inform. Proc. Lett. 42, 235-241, 1992.

在 Wolfram|Alpha 中被引用

排列图

引用为

Weisstein, Eric W. "排列图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/ArrangementGraph.html

主题分类