2017年3月

组合图论的内容。与其说是图论倒不如说是组合数学。


预备基础:图论(各定义)、组合数学基础(生成函数)、线性代数(行列式)。


有标号无根树 labelled unrooted tree

Prüfer 编码 Prüfer code/sequence

对一棵有标号无根树,每次取度数为一且标号最小的点的相邻点加入编码序列并删除。可以证明每一段编码对应唯一一棵无根树。
一些有用的性质是编码长度为$ n-2 $,对度数为$ d_i $的点其在编码里出现$ d_i-1 $次。

Cayley 公式 Cayley's Formula

(Cayley's)在完全图$ K_n $中,生成树的个数是$ n^{n-2} $。
由 Prufer 编码原理显然。
推论:
在完全图$ K_n $中,$ i $号点度限制为$ d_i $的生成树个数是$ {{n-2} \choose {d_i-1}} = \frac{(n-2)!}{\prod(d_i-1)!} $。
在完全二分图$ G=(U,V,E) $中,生成树个数是$ |U|^{|V|-1}|V|^{|U|-1} $。

参考

Wikipedia: Prüfer sequence
morejarphone~: prufer数列学习笔记 (有树转Prufer和Prufer转树的代码)
Matrix67: 经典证明:Prüfer编码与Cayley公式(图与证明)

有编号有根树 labelled rooted tree

由上节结论,及「每一种有编号无根树的情况都对应$ n $种有编号有根树的情况」这一显然结论(每一个节点均可为根),可得完全图$ K_n $中有编号有根生成树个数为$ n^{n-2} \cdot n=n^{n-1} $。

待续