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} $。