引入问题
给n个点m条边的图，求该图的最小生成树个数。
定理内容
我们对这个图构造两个矩阵，分别是这个图的连通矩阵和度数矩阵。连通矩阵
S
1
S1
S1的第
i
i
i行第
j
j
j列上的数字表示原无向图中编号为
i
i
i和编号为
j
j
j的两个点之间的边的条数。度数矩阵
S
2
S2
S2只有斜对角线上有数字，即只有第
i
i
i行第
i
i
i列上有数字，表示编号为i的点的度数是多少。我们将两个矩阵相减，即
S
2
−
S
1
S2−S1
S2−S1，我们记得到的矩阵为
T
T
T，我们将矩阵
T
T
T去掉任意一行和一列（一般情况去掉最后一行和最后一列的写法比较多）得到
T
′
T^′
T′，最后生成树的个数就是这个矩阵
T
′
T^′
T′的行列式。 ——摘自：《矩阵树定理浅谈》
基尔霍夫矩阵
定义：如果图
D
D
D有总共
N
N
N个点，那么图
D
D
D的基尔霍夫矩阵
G
G
G可以表示为：
G
i
j
=
{
d
e
g
r
e
e
(
i
)
i
=
j
−
c
n
t
(
i
,
j
)
i
≠
j
G_{ij}=\left\{ \begin{array}{rcl} & degree(i) & &{i=j}\\ &−cnt(i,j) & &{i \neq j}\\ \end{array}\right.
Gij={degree(i)−cnt(i,j)i=ji=j
d
e
g
r
e
e
degree
degree：结点i的度数
c
n
t
cnt
cnt ：两点之间的边数
解决问题的关键就是利用基尔霍夫矩阵。
以下假设图无重边，证明摘自：《生成树的计数及其应用》周冬
性质
∣
G
∣
=
0
\left|G\right|=0
∣G∣=0，证明：显然每行的和为0，把所有列都加到第一列得0。若图
D
D
D不连通，则其对应的基尔霍夫矩阵的任意
n
−
1
n-1
n−1阶主子式为0。
证明：假设图
D
D
D有
k
(
k
>
1
)
k(k>1)
k(k>1)个连通份量
D
1
,
D
2
,
.
.
.
,
D
k
D_1,D_2,...,D_k
D1,D2,...,Dk。我们可以通过矩阵的变换使得这些连通分量的排列如下：(每次变换行列都交换一次，对应行列式符号不变)
(
D
1
0
⋯
0
0
D
2
⋯
0
⋮
⋮
⋱
⋮
0
0
0
D
k
)
\begin{pmatrix} D_1 & 0 &\cdots& 0\\\\ 0 & D_2 &\cdots&0\\\\ \vdots &\vdots & \ddots&\vdots\\\\ 0 & 0 & 0 &D_k\\\\ \end{pmatrix}
⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛D10⋮00D2⋮0⋯⋯⋱000⋮Dk⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞(矩阵中的0元素确保连通分量之间不连通)
∣
G
∣
\left|G\right|
∣G∣=
∣
G
1
∣
\left|G_1\right|
∣G1∣
∣
G
2
∣
⋯
∣
G
k
∣
\left|G_2\right|\cdots\left|G_k\right|
∣G2∣⋯∣Gk∣，据此可得出对应基尔霍夫矩阵的任意
n
−
1
n-1
n−1阶主子式为0。
若图
D
D
D是树，其对应基尔霍夫矩阵
G
G
G的任意一个
n
−
1
n-1
n−1阶主子式为1。 证明：往证，可以不断变换
∣
G
∣
\left|G\right|
∣G∣得到一上三角行列式，且主对角线元素为1。 第一步：假设
v
r
v_r
vr为根结点，以
v
r
v_r
vr为首让每个结点根据与
v
r
v_r
vr的距离从小到大排序，同距离的可任意排。显然对于结点
v
j
v_j
vj，其父亲
v
i
v_i
vi必定在前面。 第二步：将
∣
G
∣
\left|G\right|
∣G∣根据排好的序列调整行列元素，将行列不断交换。因为交换为偶数次，符号不变。此外继续调整，对每个结点
v
i
v_i
vi的儿子
v
i
1
,
v
i
2
,
.
.
.
,
v
i
k
v_{i_1},v_{i_2},...,v_{i_k}
vi1,vi2,...,vik，儿子对应的每一列都加到第
i
i
i列上。 第三步：对于最后一列，对应结点只与父亲相连，故度为1，符合条件。用数学归纳法，目前处理的是第
i
i
i列，假设第
i
+
1
i+1
i+1到第
n
n
n列都已经符合条件，即对角线元素为1。对每个结点
v
i
v_i
vi的儿子
v
i
1
,
v
i
2
,
.
.
.
,
v
i
k
v_{i_1},v_{i_2},...,v_{i_k}
vi1,vi2,...,vik，其对应列的第
i
i
i行元素为-1，第
i
j
i_j
ij行(对角线)的元素为1，再看第
i
i
i列，对应的儿子行元素都为-1，第
i
i
i行元素为
k
+
1
k+1
k+1(儿子和父亲)，故都加到第
i
i
i列后，第
i
i
i行元素变为1，下面每行都为0。因此，最终构造了上三角行列式且主对角元素为1，任意抽去第
i
i
i行第
i
i
i列，行列式值为1，证毕。
定理证明
引入定义，矩阵
B
B
B为
n
×
m
n\times m
n×m矩阵，分别对应结点和边。
B
i
j
=
{
−
1
v
i
为
边
e
j
起
点
1
v
i
为
边
e
j
终
点
0
o
t
h
e
r
w
i
s
e
B_{ij}=\left\{ \begin{array}{rcl} & -1 & &v_i为边e_j起点\\ &1 & &v_i为边e_j终点\\ &0 & &otherwise\\ \end{array}\right.
Bij=⎩⎨⎧−110vi为边ej起点vi为边ej终点otherwise
容易验证：
B
B
T
=
G
BB^T=G
BBT=G，若去掉
B
B
B中第
r
r
r行得到
B
r
B_r
Br，有
G
r
=
B
r
B
r
T
G_r=B_rB_r^T
Gr=BrBrT，即
G
G
G去掉第
r
r
r行和第
r
r
r列。
看一下Binet-Cauchy公式：
设矩阵
A
A
A为
p
×
q
p\times q
p×q矩阵，矩阵
B
B
B为
q
×
p
q\times p
q×p矩阵，有
d
e
t
(
A
B
)
=
{
0
当
p
>
q
时
d
e
t
(
A
)
d
e
t
(
B
)
当
p
=
q
时
∑
1
≤
j
1
<
j
2
<
⋯
<
j
p
≤
q
A
(
1
2
⋯
p
j
1
j
2
⋯
j
p
)
B
(
j
1
j
2
⋯
j
p
1
2
⋯
p
)
当
p
<
q
时
det(AB)=\left\{ \begin{array}{rcl} &0& 当p>q时\\ &det(A)det(B)& 当p=q时\\ & \sum\limits_{1\leq j_1 det(AB)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧0det(A)det(B)1≤j1 其中 A ( 1 2 ⋯ p j 1 j 2 ⋯ j p ) A\begin{pmatrix} 1 &2&\cdots&p\\\\ j_1&j_2&\cdots&j_p \end{pmatrix} A⎝⎛1j12j2⋯⋯pjp⎠⎞表示 A A A的第 j 1 , j 2 , . . . , j p j_1,j_2,...,j_p j1,j2,...,jp列所成的子式， B ( j 1 j 2 ⋯ j p 1 2 ⋯ p ) B\begin{pmatrix} j_1&j_2&\cdots&j_p\\\\ 1&2&\cdots&p \end{pmatrix} B⎝⎛j11j22⋯⋯jpp⎠⎞表示 B B B的第 j 1 , j 2 , . . . , j p j_1,j_2,...,j_p j1,j2,...,jp行所成的子式。 从而得到： d e t ( G r ) = d e t ( B r B r T ) = ∑ x ⊂ { 1 , 2 , . . , m } ∣ x ∣ = n − 1 d e t ( B r x B r x T ) = ∑ x ⊂ { 1 , 2 , . . , m } ∣ x ∣ = n − 1 ( d e t ( B r x ) ) 2 det(G_r)=det(B_rB_r^T)=\sum\limits_{x\subset \{1,2,..,m\}\atop\left|x\right|=n-1}det(B_r^xB_r^{x^T})=\sum\limits_{x\subset \{1,2,..,m\}\atop\left|x\right|=n-1}(det(B_r^x))^2 det(Gr)=det(BrBrT)=∣x∣=n−1x⊂{1,2,..,m}∑det(BrxBrxT)=∣x∣=n−1x⊂{1,2,..,m}∑(det(Brx))2 解释一下： B r B_r Br为 ( n − 1 ) × m (n-1)\times m (n−1)×m矩阵( m > n − 1 m>n-1 m>n−1)，则 d e t ( B r B r T ) = det(B_rB_r^T)= det(BrBrT)=所有 n − 1 n-1 n−1列构成的子式的行列式的平方和。 B r x B_r^x Brx表示 B r B_r Br中边元素属于包含于边集 E E E的子集 x x x的所在列抽出构成的新矩阵，显然 B r x B r x T B_r^xB_r^{x^T} BrxBrxT可以看作一个 n n n个点和 n − 1 n-1 n−1条边构成的图的基尔霍夫矩阵的的一个 n − 1 n-1 n−1阶主子式，当 x x x为树时，行列式值为1，否则图不连通值为0，考察所有边集元素个数为 n − 1 n-1 n−1的子集，结果就恰好为生成树个数！ 对于含重边的图该定理仍然适用，但是如何证明尚且不知… 应用部分 模板题：P4111 [HEOI2015]小 Z 的房间 #include #include #include using namespace std; typedef long long ll; const ll mod = 1e9; const int dir[4][2] = { {1,0},{0,1}}; int n, m; char g[10][10]; ll K[100][100]; int id[10][10]; void update(int x, int y) { K[x][y]--; K[y][x]--; K[x][x]++; K[y][y]++; } ll det(int n) { ll res = 1; for (int i = 1; i <= n; i++) {//依次把第i列，从第i+1行到第n行变为0 for (int j = i + 1; j <= n; j++) { while (K[j][i]) {//直到为0 ll t = K[i][i] / K[j][i];//计算第i列,第i行是第j行的几倍 for (int k = i; k <= n; k++) { K[i][k] = (K[i][k] - t * K[j][k] % mod + mod) % mod; swap(K[i][k], K[j][k]);//把第i行元素变为0后与第j行交换 } res = -res;//每次交换行 值变为原来的负数 } } if (!K[i][i])return 0; res = (res * K[i][i] % mod + mod) % mod;//将行列式化为上三角行列式后 值为对角线元素的乘积 } return res; } char read() { char ch = getchar(); while (ch != '.' && ch != '*')ch = getchar(); return ch; } int main(void) { memset(K, 0, sizeof(K)); memset(id, 0, sizeof(id)); scanf("%d %d", &n, &m); int cnt = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { g[i][j] = read(); if (g[i][j] == '.')id[i][j] = ++cnt; } } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (g[i][j] == '.') { if (id[i - 1][j])update(id[i - 1][j], id[i][j]); if (id[i][j - 1])update(id[i][j - 1], id[i][j]); } printf("%lld\n", det(cnt - 1) % mod); return 0; }