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

生成樹的計數 Matrix-Tree定理

問題的提出

?

[例一]高速公路（SPOJ 104 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]表示。

生成樹計數

算法步驟：

1、?構建拉普拉斯矩陣

? ? ?Matrix[i][j] =

degree(i) , i==j

??????????-1，i-j有邊

???????????0，其他情況

2、?去掉第r行，第r列（r任意）

3、?計算矩陣的行列式

論文 周冬 《生成樹計數應用》

#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 105; const int maxm = 100005; const int INF = 1e9; int degree[maxn]; ll g[maxn][maxn]; int n, m; ll det(ll a[][maxn], int n) { ll ret = 1; for(int i=1; i<n; ++i){ for(int j=i+1; j<n; ++j){ while(a[j][i]){ ll t = a[i][i]/a[j][i]; for(int k=i; k<n; ++k){ a[i][k] = (a[i][k]-a[j][k]*t); } for(int k=i; k<n; ++k){ swap(a[i][k], a[j][k]); } ret = -ret; } } if(a[i][i]==0){ return 0; } ret = ret*a[i][i]; } if(ret<0){ ret = -ret; } return ret; } void solve() { int u, v; memset(degree, 0, sizeof degree ); memset(g, 0, sizeof g ); scanf("%d%d", &n, &m); while(m--){ scanf("%d%d", &u, &v); u--,v--; g[u][v] = g[v][u] = -1; degree[u]++; degree[v]++; } for(int i=0; i<n; ++i){ g[i][i] = degree[i]; } printf("%lld\n", det(g, n)); } int main() { int t; scanf("%d", &t); while(t--){ solve(); } return 0; }

轉載于:https://www.cnblogs.com/tham/p/6827125.html

總結

以上是生活随笔為你收集整理的生成树的计数 Matrix-Tree（矩阵树）定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。