线性代数5 基尔霍夫定理

Kirchhoff’s Theorem

基尔霍夫定理 (Kirchhoff’s Theorem), 因为是用矩阵求无向图的所有本质不同的生成树的数量, 所以又叫矩阵树定理 (Matrix Tree Theorem):

构造一个矩阵, 对角线上 (i,i)(i, i) 是第 ii 个点的度, 两个点 ii, jj 之间连边就将 (i,j)(i, j) 和 (j,i)(j, i) 设为 −1-1. 钦定一个点为根, 则删掉这个点对应的行和列, 矩阵的行列式就是需要求的答案.

对于有向图, (i,i)(i, i) 记录出度, 每条从 ii 到 jj 的有向边将 (i,j)(i, j) 置为 −1-1. 需要枚举每个点作为根求行列式, 然后求和.

如果存在自环, 直接忽略这种边, 因为无论什么生成树都不可能包含自环边. 如果有重边, 我们可以认为这两个点之间有边的情况都要被计数两次, 分别给两个点的度数在之前的基础上再加一, 邻接矩阵上也再减一. 如果把重边看成是带权的边, 有几条重边边权就是几, 那么求得的行列式就是所有生成树的边权之积的总和. 发现两种情况是等价的.

对于带权图, 只要把 −1-1 设为负的两点间边权总和, 让每条边对度数的共献为边权, 就可以求出每棵生成树的边权积之和了. 有向图也存在类似的结论.

下面是模板题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const unsigned long long Mod(1000000007);
unsigned long long a[305][305], Tms(1);
unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(1);
char Opt;
inline unsigned long long Pow(unsigned long long x, unsigned y) {
  unsigned long long Rt(1);
  while (y) { if (y & 1) Rt = Rt * x % Mod; x = x * x % Mod, y >>= 1; }
  return Rt;
}
signed main() {
  n = RD() - 1, m = RD(), Opt = RD();
  for (unsigned i(1); i <= m; ++i) {
    A = RD() - 1, B = RD() - 1, C = RD();
    if (A ^ B) {
      a[B][B] += C, a[A][B] += Mod - C;
      if (!Opt) a[A][A] += C, a[B][A] += Mod - C;
    }
  }
  for (unsigned i(1); i <= n; ++i) for (unsigned j(1); j <= n; ++j) a[i][j] %= Mod;
  for (unsigned i(1); i <= n; ++i) {
    unsigned No(i);
    while ((No <= n) && (!a[No][i])) ++No;
    if (No > n) { printf("0\n"); return 0; }
    if (No ^ i) { for (unsigned j(i); j <= n; ++j) swap(a[No][j], a[i][j]); Tms = Mod - Tms; }
    for (unsigned j(i + 1); j <= n; ++j) {
      unsigned long long Tmp(a[j][i] * (Mod - Pow(a[i][i], Mod - 2)) % Mod);
      for (unsigned k(i); k <= n; ++k) a[j][k] = (a[j][k] + a[i][k] * Tmp) % Mod;
    }
  }
  for (unsigned i(1); i <= n; ++i) Ans = Ans * a[i][i] % Mod;
  printf("%llu\n", Ans * Tms % Mod);
  return Wild_Donkey;
}