矩陣樹定理

摘要

?

?????? 在信息學競賽中，有關生成樹的最優化問題如最小生成樹等是我們經常遇到的，而對生成樹的計數及其相關問題則少有涉及。事實上，生成樹的計數是十分有意義的，在許多方面都有著廣泛的應用。本文從一道信息學競賽中出現的例題談起，首先介紹了一種指數級的動態規劃算法，然后介紹了行列式的基本概念、性質，并在此基礎上引入Matrix-Tree定理，同時通過與一道數學問題的對比，揭示了該定理所包含的數學思想。最后通過幾道例題介紹了生成樹的計數在信息學競賽中的應用，并進行總結。

關鍵字

?

?????? 生成樹的計數 Matrix-Tree定理

問題的提出

?

[例一]高速公路（SPOJ p104 Highways）

?

?????? 一個有n座城市的組成國家，城市1至n編號，其中一些城市之間可以修建高速公路。現在，需要有選擇的修建一些高速公路，從而組成一個交通網絡。你的任務是計算有多少種方案，使得任意兩座城市之間恰好只有一條路徑？

?????? 數據規模：1≤n≤12。

[分析]

?

?????? 我們可以將問題轉化到成圖論模型。因為任意兩點之間恰好只有一條路徑，所以我們知道最后得到的是原圖的一顆生成樹。因此，我們的問題就變成了，給定一個無向圖G，求它生成樹的個數t(G)。這應該怎么做呢？

經過分析，我們可以得到一個時間復雜度為O(3n*n2)的動態規劃算法，因為原題的規模較小，可以滿足要求。但是，當n再大一些就不行了，有沒有更優秀的算法呢？答案是肯定的。在介紹算法之前，首先讓我們來學習一些基本的預備知識。

新的方法

?

介紹

?

?????? 下面我們介紹一種新的方法——Matrix-Tree定理(Kirchhoff矩陣-樹定理)。Matrix-Tree定理是解決生成樹計數問題最有力的武器之一。它首先于1847年被Kirchhoff證明。在介紹定理之前，我們首先明確幾個概念：

1、G的度數矩陣D[G]是一個n*n的矩陣，并且滿足：當i≠j時,dij=0；當i=j時，dij等于vi的度數。

2、G的鄰接矩陣A[G]也是一個n*n的矩陣， 并且滿足：如果vi、vj之間有邊直接相連，則aij=1，否則為0。

我們定義G的Kirchhoff矩陣(也稱為拉普拉斯算子)C[G]為C[G]=D[G]-A[G]，則Matrix-Tree定理可以描述為：G的所有不同的生成樹的個數等于其Kirchhoff矩陣C[G]任何一個n-1階主子式的行列式的絕對值。所謂n-1階主子式，就是對于r(1≤r≤n)，將C[G]的第r行、第r列同時去掉后得到的新矩陣，用Cr[G]表示。

附程序：

#include<iostream>

??????#include<cmath>

using namespace std;

#define zero(x)((x>0? x:-x)<1e-15)

int const MAXN = 100;

double a[MAXN][MAXN];

?????? doubleb[MAXN][MAXN];

int g[53][53];

?????? int N, M;

double det(double a[MAXN][MAXN], int n) {

??? int i, j,k, sign = 0;

??? doubleret = 1, t;

??? for (i =0; i < n; i++)

??????? for(j = 0; j < n; j++)

???????????b[i][j] = a[i][j];

??? for (i =0; i < n; i++) {

??????? if(zero(b[i][i])) {

???????????for (j = i + 1; j < n; j++)

???????????????if (!zero(b[j][i]))

???????????????????break;

???????????if (j == n)

???????????????return 0;

???????????for (k = i; k < n; k++)

???????????????t = b[i][k], b[i][k] = b[j][k], b[j][k] = t;

???????????sign++;

??????? }

??????? ret*= b[i][i];

??????? for(k = i + 1; k < n; k++)

???????????b[i][k] /= b[i][i];

??????? for(j = i + 1; j < n; j++)

???????????for (k = i + 1; k < n; k++)

???????????????b[j][k] -= b[j][i] * b[i][k];

??? }

??? if (sign& 1)

??????? ret =-ret;

??? returnret;

}

int main() {

??? int cas;

???scanf("%d", &cas);

??? while (cas--) {

??????? scanf("%d%d", &N,&M);

??????? for (int i = 0;i < N; i++) {

???????????for (int j = 0; j < N; j++) {

??????????????

????????? ?????g[i][j] = 0;

??????????? }

??????? }

??????? while(M--) {

???????????int a, b;

???????????scanf("%d%d", &a, &b);

???????????g[a - 1][b - 1] = g[b - 1][a - 1] = 1;

??????? }

??????? for(int i = 0; i < N; i++) {

???????????for (int j = 0; j < N; j++) a[i][j] = 0;

??????? }

??????? for(int i = 0; i < N; i++) {

???????????int d = 0;

???????????for (int j = 0; j < N; j++) if (g[i][j]) d++;

???????????a[i][i] = d;

??????? }

??????? for(int i = 0; i < N; i++) {

???????????for (int j = 0; j < N; j++) {

???????????????if (g[i][j]) a[i][j] = -1;

??????????? }

??????? }

???????double ans = det(a, N - 1);

???????printf("%0.0lf\n", ans);

??? }

??? return 0;

}