我们知道,每个无向连通图都会有自己的生成树。但是大家更熟悉的,是无向图的最小生成树(MST)算法。本文旨在讨论计算无向连通图的生成树个数的时间复杂度为O(n3)的方法。另外一种时间效率高的递推式方法的讲解在文末附有链接。
我们可以利用矩阵在O(n3)的时间内求出无向连通图的生成树个数。对于一个无向连通图,我们可以根据以下规则列出一个矩阵M:
- 主对角线上的值M(i,i)为i节点的度。
- a[i,j]的值为点i到点j的平行边的条数的相反数。显然,如果i,j不连通,M(i,j)=0。
通过这样的规则,一个矩阵就在O(n2)的时间内建立起来。
以图1为例。
这样,我们就得到了矩阵M:
参考代码(init):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
begin
fillchar(ma,sizeof(ma),
0
);
readln(n,m);
for
i:=
1
to
n
do
for
j:=
1
to
n
do
begin
read(x);
if
x=
1
then
begin
ma[i,i]:=ma[i,i]+
1
;
ma[i,j]:=-
1
;
end
;
end
;
end
.
|
恩,有了这个矩阵有什么用呢?
定理的证明在这里不再赘述(其实我也不会,知道怎么证明又有什么用呢 可以用数学归纳法证明),如果想知道详细的证明过程,可以参阅文末所附的参考文献,或者在网上查阅。
经过删除操作,我们得到如下的矩阵M’:
可是,行列式的值怎么求呢?
我们知道行列式值的手工求法是经过将行列式降阶,通过如下的定理求得:
【定理】三阶行列式D= 的值等于它任意一行(列)的所有元素与它们对应的代数余子式乘积之和。
即:
用等式表示为:
当阶数很高,这种方法由于要递归、压栈,不但占用大量内存,而且代码复杂度很高(现在我还没有打出来过 *.*||)。在这里,我们用高斯消元的思想将行列式转化成一个下三角行列式,运用以下性质即可求出行列式的值。
【性质】三角形行列式的值等于主对角线上元素的乘积。
这样,只要我们将行列式进行消元,然后求得主对角线上元素的乘积即可。
参考代码(make):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
begin
ans:=
1
;
for
k:=
1
to
n
do
begin
ans:=ans*a[k,k];
//记录对角线乘积
for
i:=k+
1
to
n
do
if
a[i,k]<>
0
then
begin
zoom:=-a[k,k]/a[i,k];
ans:=ans/zoom;
//ans也要zoom一下
for
j:=k
to
n
do
a[i,j]:=a[k,j]+a[i,j]*zoom;
//消元
end
;
end
;
writeln
(round(ans));
end
;
|
下面是一道例题。
首先注意,解不是n!。原因是路线不一定是链状的,而可能是树状的。这样,问题就转化成求无向连通图的生成树个数的问题了。
参考代码:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
program
escape;
var
a,ta:
array
[
1..30
,
1..30
]
of
extended
;
n,m,x,y,i:
integer
;
ans:
extended
;
procedure
init;
var
i,j:
integer
;
begin
readln(n,m);
for
i:=
1
to
n+
1
do
for
j:=
1
to
n+
1
do
begin
read(x);
if
x=
1
then
begin
a[i,i]:=a[i,i]+
1
;
a[i,j]:=-
1
;
end
;
end
;
ta:=a;
end
;
procedure
make;
var
i,j,k:
integer
;
zoom:
extended
;
begin
ans:=
1
;
for
k:=
1
to
n
do
begin
ans:=ans*a[k,k];
for
i:=k+
1
to
n
do
if
a[i,k]<>
0
then
begin
zoom:=-a[k,k]/a[i,k];
ans:=ans/zoom;
for
j:=k
to
n
do
a[i,j]:=a[k,j]+a[i,j]*zoom;
end
;
end
;
writeln
(round(ans));
end
;
begin
init;
make;
for
i:=
1
to
m
do
begin
readln(x,y);
ta[x,x]:=ta[x,x]-
1
;
ta[y,y]:=ta[y,y]-
1
;
ta[x,y]:=
0
;
ta[y,x]:=
0
;
a:=ta;
//记录原图
make;
end
;
end
.
|
参考链接(均有递推式法