变元矩阵-树定理

变元矩阵-树定理(variable matrix-tree theorem)是矩阵-树定理的推广。矩阵Mx的任何一个余因子的值是G的树多项式(G的一个生成树的项是指它的边的积，G的树多项式是它的各个生成树的项的和)1。

基本介绍若为对应于图G的形式矩阵，其元素定义为：

对于，当，；

当不相邻，，

则M的任何代数余子式的值是G的树多项式，这称为变元矩阵-树定理。附图为一示例。其中，P(T(G))为圈G的树多项式2。

矩阵-树定理矩阵-树定理 设G为一个具有顶点集的图。那么L(G)中任意元素的余子式等于G中支撑树的数量。

证明 在下文定理1中令，则等于只有一个分支的G的支撑森林的数量，也就是等于G中支撑树的数量。通过下文引理1可知，L(G)的所有余子式是相等的，定理得证。

需要指出，在此定理中G并不需要被假设为连通图。如果G是非连通的，则其没有支撑树。同时，L(G)的秩最多为n-2，因此其所有的余子式都为0。

引理1 设G为一个具有顶点集和边集，那么下述命题成立：

(i)L(G)为对称的半正定矩阵。

(ii)L(G)的秩为，其中k为G中连通分支的数量。

(iii)对于任意的向量x，有

(iv)L(G)的每行元素与每列元素之和都为0。

(v)L(G)中任何两个元素的余子式相等。

定理1 设G为一个具有顶点集的图，并令W为V(G)的一个非空真子集。那么的行列式等于G中含有个分支的支撑森林的数量，其中每一个分支都包含了W中的一个顶点3。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学