【图论】Cayley定理

本文最后更新于:14 天前

Cayley定理 于1854年在 Arthur Cayley 的论文中首次被提到。

本文简单讲述了Cayley定理在图论中的应用,并用普吕弗序列做了简单证明

一般的表述:

每个群 \(G\) 同构于 对称群的子群


而在图论与组合数学中,该定理被用来计算 完全图生成树 的总数。

图论中的表述:

假如某一完全图有 \(n\) 个顶点,那么该图的生成树的数量为 \(n^{n-2}\) 个。

Cayley定理 的证明方法大概有三种,这里讲述最简单也是最直观的一种方法 利用 普吕弗序列 来证明 Cayley定理。


\(T\) 为一颗标号树,共有 \(n\) 个顶点,分别标号为 \(a_1,a_2,a_3, \cdots ,a_{n}\)

每次取出标号最小的叶子,记为 \(a_1\) ,而 \(a_1\)的邻接点记为 \(b_1\) 。注意:此时 叶子 \(a_1\) 不一定为 标号为 \(1\) 的叶子。

将顶点 \(a_1\) 与 边 ( \(a_1 , b_1\) ) 从树中删去。注意:此时 \(b_1\) 不一定会变成叶子。

设一个 普吕弗序列 \(B\) ,将 \(b_1\) 加入到序列 \(B\) 中。

如此往复,执行操作共 \(n-2\) 次,直到树 \(T\) 只剩一条边。

我们便可以得到一个普吕弗序列 \(B\)

\[b_1,b_2,b_3,\cdots ,b_{n-2}\]

我们可以用该序列重新构造出 树 \(T\)

我们先写一个从 \(1\)\(n\) 的有序序列 \(C\)

\[1,2,3,\cdots ,n\]

然后每次从 序列 \(C\) 中找到第一个不出现在序列 \(B\) 中的元素,记为 \(c_1\)

\(c_1\)\(b_1\) 分别从序列中删去,并在树 \(T\) 中加入这两个顶点与他们之间的边 (\(c_1,b_1\))

如此往复,执行操作共 \(n-2\) 次,序列 \(C\) 中仅剩两个元素,分别设为 \(c_{n-1},c_{n}\)

在树 \(T\) 中加入最后一条边 ( \(c_{n-1},c_{n}\) ) ,我们便从普吕弗序列中将树 \(T\) 构建了回来。


经过上述推导,在构建普吕弗序列时,我们可以得知 \(B\) 序列中一共有 \(n-2\) 个元素,\(b_i \in [1,n] 且 b_i \in Z^{+}\)

\[\begin{matrix}n-2\\\overbrace{n \times n\times \cdots \times n}\end{matrix} = n^{n-2}\]

所以便可以证明得

假如某一完全图有 \(n\) 个顶点,那么该图的生成树的数量为 \(n^{n-2}\) 个。