专题1-生成树

这里研究的第一个问题就是图的生成树计数问题 (节点带序，1-2-3和1-3-2不同)

记号说明
incidence matrix
区别全关联矩阵\(\bold{A_0}\) （n行m列）

对于无向图
\(a_{ij}=1 ,if\quad e_j与v_i关联\)
\(a_{ij}=0 ,if\quad e_j与v_i不关联\)

和
它去掉任一行得到的关联矩阵\(\bold{A}\) (n-1行m列)
可以证明，\(\bold{A}\)的每一个\(n-1\)（n个顶点，m条边）非奇异方阵一一对应一个支撑树，并且这个方阵的行列式绝对值是1

A principal cofactor \(L_v(G)\) is obtained from \(L(G)\) by removing the \(v\)th row and \(v\)th column for some vertex v.

证明我看不懂

给一个完全图的生成树数目的证明:

有向矩阵树定理证明

如果不嫌麻烦，也可以计算Tutte多项式，然后求点值(1,1)