基尔霍夫(Kirchhoff)矩阵

设标定映射 $\mu: \{1,2,\cdots,n\}\to V(G_n),K(G_n)=(a_{i,j})_{n\times n},\begin{cases}
a_{i,j}&=&deg(\mu(i)),&i=j\\
a_{i,j}&=-&cnt(\mu(i),\mu(j)),&i\not= j
\end{cases}$
其中 $cnt(m,n)$ 表示点 $m,n$ 间的连边条数,简单图下 $cnt(m,n)=0,1$

性质1: $K(G_n)$ 的每行每列合为 $0$ ,故 $det K(G_n)=0$

性质2: 若 $\omega(G_n)>1$ 则 $K(G_n)$ 的任意 $n-1$ 主子式为 $0$,证明:

将 $G_n$ 分为 $\omega(G_n)$ 个连通分支, 则可通过交换 $K(G_n)$ 的 $i,j$ 行, $i,j$ 列(进行了偶数次交换所以行列式符号不变),使得 $K(G_n)\to diag(K_1,K_2,\cdots,K_{\omega(G_n)})=K’$ 其中 $K_i$ 是 $G_n$ 第 $i$ 个连通分支的 $Kirchoff$ 矩阵,它们的行列式因此等于 $0$
设 $C_r(K)$ 是 $K$ 去掉 $r$ 行, $r$ 列的矩阵
若设去掉的点 $r$ 是第 $s$ 个连通分支中的第 $j$ 个点,则有:
$det(C_r(K’))=det(K_1)det(K_2)\cdots det(C_j(K_s))\cdots det(K_{\omega(G_n)})=0$

性质3: 若 $G_n$ 是树,则 $\forall r\in\{1,2,\cdots,n\}det(C_r(K(G_n)))=1$ ,证明:

选取上述去掉的 $v_r$ 为根节点,把剩余所有点按深度从小到大排序,相同坐标的点间顺序随意,得到 $v_{a_1},v_{a_2},\cdots,v_{a_{n-1}}$
在 $C_r(K(G_n))$ 中同样利用同时交换 $i,j$ 行, $i,j$ 列,把对角线上的点按上述顺序重新排序,得到 $K’=(k_{i,j})_{n-1\times n-1}$ (同样是偶数次交换所以行列式符号不变)
设第 $s$ 列对应的点有 $m$ 个孩子,对应 $z_1,z_2,\cdots,z_m$ 列,把第 $z_1,z_2,\cdots,z_m$ 全部加到第 $s$ 列上去,此操作从深度从大到小进行,即从矩阵的右侧往左侧进行
首先对于深度最大的那些列,它们只有一个父亲,度数为 $1$,其所在矩阵中的位置的下方已不可能有非 $0$ 的值,称第 $i$ 列是满足条件的,如果 $k_{i,i}=1$ 且 $\forall j>i,k_{j,i}=0$
显然这些深度最大的列已经是满足条件的(事实上,如果第 $i$ 列的父亲对应第 $j$ 列,则 $\forall j<s<i,k_{s,i}=0$)
假设从 $i+1$ 到 $n-1$ 列都已经是满足条件的:
第 $i$ 列的所有孩子列 $z_1,z_2,\cdots,z_m$ 会在第 $i$ 行有个 $-1$ (前面的操作不会影响它们)
它们与父亲间连边的 $-1$ 会恰好被加上来的 $k_{i,i}=1$ 给抵消,即第 $i$ 列也是符合规则的
所以可以把 $K’$ 变成对角线全为 $1$ 的上三角矩阵 $\therefore det K’=det C_r(K(G_n))=1$

关联矩阵

无环图 $G$ 的关联矩阵 $B(G)=(b_{i,j})$是一个 $n(G)\times m(G)$ 的矩阵, 其定义是: 对于点和边的标定 $\mu:\{1,2,\cdots,n(G)\}\to V(G),\theta:\{1,2,\cdots,m(G)\}\to E(G)$
如果 $\theta(j)$ 连接了 $\mu(p),\mu(q)$ 则 $b_{p,j},b_{q,j}$ 中一个为 $1$ 另一个为 $-1$ ,具体谁是 $1$ 谁是 $-1$ 并不重要,其余元素为 $0$
$S=BB^T=(s_{i,j})$ 中 $s_{i,j}$ 元素表示 $B$ 中的第 $i$ 行和 $j$ 行的点积
易知, $s_{i,j}=-cnt(\mu(i),\mu(j))(i\not= j),s_{i,i}=deg(\mu(i))$
因此,对于无环图 $G$ 有 $K(G)=B(G)B(G)^T$

定理(Matrix-Tree):

即 $K(G_n)$ 的任意 $n-1$ 阶主子式的绝对值等于 $G_n$ 的标定生成子树个数
证明:
去掉 $B(G)$ 的第 $r$ 行,得到 $B_r$ ,去掉 $K(G)$ 的第 $r$ 行,第 $r$ 列得到 $K_r$,易知 $K_r=B_rB_r^T$
由 $Cauchy-Binet$:
$ det(K_r)=det(B_rB_r^T)=$

设 $x=(x_1,x_2,x_3,\cdots,x_{n(G)-1}),1\leq x_1< x_2<\cdots< x_{n(G)-1}\leq m(G)$ 记 $B_r^x=B_r\left(\begin{matrix}1&&2&&\cdots&&n(G)-1\\x_1&&x_2&&\cdots&&x_{n(G)-1}\end{matrix}\right)$
$det(B_r^x)^2=det(B_r^x)det((B_r^x)^T)=det(B_r^x(B_r^x)^T)$
而 $det(B_r^x(B_r^x)^T)$ 也可以看成是一个 $n(G)$ 阶基尔霍夫矩阵的 $n(G)-1$ 阶主子式,由基尔霍夫矩阵的性质,如果将 $x$ 对应的边加入由 $V(G)$ 组成的空图得到的图是一颗树,有 $det(B_r^x(B_r^x)^T)=1$
如果将 $x$ 对应的边加入由 $V(G)$ 组成的空图得到的图不是一颗树,由于这个 $n(G)$ 个点的图内只有 $n(G)-1$ 条边,如果它不是树,则它的连通分支数必然大于 $1$ ,由基尔霍夫矩阵的性质,可知 $det(B_r^x(B_r^x)^T)=0$
因此 $det(K_r)$ 相当于一个初始值 $s=0$ ,然后列出图 $G$ 中所有 $n(G)-1$ 条边的组合,且如果将这 $n(G)-1$ 条边加入到 $V(G)$ 组成的空图中得到的是一颗树, 那么 $s$ 增加 $1$ ,否则 $s$ 不变
因此 $det(K_r)=\tau(G)$

例题

轮 $W_n=C_n\lor v_o$ 其中 $C_n$ 为 $n$ 圈, $v_o$ 为一点,求 $\tau(W_n)$

给轮的’外圈’标定 $1,2,\cdots,n$ ,’中心点’标定 $n+1$ ,可以列出 $W_n$ 的基尔霍夫矩阵

选取最后一行最后一列消去,得到

这里令设待求式为 $S_n$ ,令 $P_n=\left|\begin{matrix}3&-1&0&\cdots&0\\
-1&3&\ddots&\ddots&\vdots\\
0&\ddots&\ddots&\ddots&0\\
\vdots&\ddots&\ddots&3&-1\\
0&\cdots&0&-1&3\end{matrix}\right|_{n\times n}$
对 $S_n,P_n$ 展开 ,得到 $S_n=3P_{n-1}-2P_{n-2}-2$ 且 $P_n=3P_{n-1}-P_{n-2}$