生成树的计数及其应用.DOC

1、生成树的计数及其应用 安徽 周冬第 1 页，共 15 页生成树的计数及其应用安徽 周冬目录生成树的计数及其应用 .1目录 .1摘要 .2关键字 .2问题的提出 .2例一高速公路（SPOJ p104 Highways） .2分析 .2预备知识 .2排列 .3行列式 .4新的方法 .7介绍 .7证明 .9理解 .12具体应用 .12例二员工组织（UVA p10766 Organising the Organisation） .13分析 .13例三国王的烦恼（原创） .13分析 .14总结 .14参考文献 .14生成树的计数及其应用 安徽 周冬第 2 页，共 15 页摘要在信息学竞赛中，有关生成树的

2、最优化问题如最小生成树等是我们经常遇到的，而对生成树的计数及其相关问题则少有涉及。事实上，生成树的计数是十分有意义的，在许多方面都有着广泛的应用。本文从一道信息学竞赛中出现的例题谈起，首先介绍了一种指数级的动态规划算法，然后介绍了行列式的基本概念、性质，并在此基础上引入 Matrix-Tree 定理，同时通过与一道数学问题的对比，揭示了该定理所包含的数学思想。最后通过几道例题介绍了生成树的计数在信息学竞赛中的应用，并进行总结。关键字生成树的计数 Matrix-Tree 定理问题的提出例一高速公路（SPOJ p104 Highways）一个有 n 座城市的组成国家，城市 1 至 n 编号，其中一

3、些城市之间可以修建高速公路。现在，需要有选择的修建一些高速公路，从而组成一个交通网络。你的任务是计算有多少种方案，使得任意两座城市之间恰好只有一条路径？数据规模：1n12。分析我们可以将问题转化到成图论模型。因为任意两点之间恰好只有一条路径，所以我们知道最后得到的是原图的一颗生成树。因此，我们的问题就变成了，给定一个无向图 G，求它生成树的个数 t(G)。这应该怎么做呢？ 经过分析，我们可以得到一个时间复杂度为 O(3n*n2)的动态规划算法，因为原题的规模较小，可以满足要求。但是，当 n 再大一些就不行了，有没有更优秀的算法呢？答案是肯定的。在介绍算法之前，首先让我们来学习一些基本的预备知识

4、。预备知识下面，我们介绍一种重要的代数工具行列式。为了定义行列式，我们首先来看一下排列的概念。生成树的计数及其应用 安徽 周冬第 3 页，共 15 页排列定义 1 由 1，2，n 组成的一个有序数组 i1i2in 称为 1，2，n 的一个排列。由排列的定义可知，i 1，i 2，i n 表示了 n 个不同的自然数，同时i1，i 2，i n 中的每个自然数都是集合 Sn=1，2， ，n中的一个元素，换句话说， niii， 21定义了集合 Sn 到自身上的一个一一对应。这个一一对应可以用符号 nii21记之，称为置换，而上述一一对应可以改写为 njjj iii， 21其中 j1j2jn 是 1，2，

5、n 的一个排列。所以这个一一对应也可以用符号 njjjii21记之，因此对 1，2，n 的任一排列 j1j2jn，可定义 njjjniiii 2121任取一个排列 i1i2in，将其中两个相邻的自然数 ij-1，i j 对换一下，便造出一个新的排列 i1i2ij-2ijij-1 ij+1in，称为原来排列的 对换排列，这样一种步骤成为对换。显然，对于任何一个排列经过若干次对换后都可以变成标准排列12n。不过，不管经过什么途径作对换，在给定排列 i1i2in 后，关于对换的次数有下列重要定理。定理 1 将任意一个排列 i1i2in 通过对换变成标准排列 12n，所需的对换次数的奇偶性与对换方式无

6、关。利用这个定理，我们引入定义 2 一个排列 i1i2in 称为偶（奇）排列，如果有一种方式，经过偶（奇）数次对换后，可以将排列 i1i2in 变为标准排列 12n。设排列 i1i2in 经过 t 次对换后变为标准排列 12n，则数值(-1) t 和对换方式无关。将它改写成 ，即ni21生成树的计数及其应用 安徽 周冬第 4 页，共 15 页的 奇 排 列 时 。，是， 当 的 偶 排 列 时 ；，是， 当 niinnt 211122n 个确定自然数 1，2，n 的排列，可以看作是集合 Sn=1，2，n 到自身上的一个一一对应。将这个概念推广，任取 n 个元素的集合S=a1，a 2，a n。对

7、于集合 S 到自身上的一一对应 niii aaa， 21称为 的一个排列。容易看出， 是nii21 n， 21 nii21的排列的充要条件是 i1i2in 是 1，2，n 的排列。a， 同样，排列 变为标准排列 的对换总次数的奇偶性和对换niia21 na21方式无关，因此引入符号 的 奇 排 列 时 。是， 当 的 偶 排 列 时 ；是， 当 niitiinan,2121 21 其中 t 是某一种将 变为 的对换方式的对换总次数。niia21 a下面我们介绍行列式。行列式一阶行列式是一个变量 a11 的函数 det(a11)= a11，也可以改写成为11det二阶行列式是四个变量 a11，a

8、 12，a 21，a 22 的函数，也可以改写成122121deta 212121detiiaa三阶行列式是九个变量 aij(i，j=1，2，3)的函数 3213213213213213213231det aaaa ，同样可以改写成为生成树的计数及其应用 安徽 周冬第 5 页，共 15 页32132132311det iii aa通过观察一、二、三阶行列式的定义，我们得出了 n 阶行列式的一般定义。定义 3 n 阶矩阵 A 的行列式是一实数，记作 detA，它定义为 nn iiina 21212det行列式有下列几种常用的符号： AaaAnnn 1111dett由行列式的定义可知，利用定义直接

9、计算行列式是很困难的，只有在阶数低时才可以直接用定义计算。为了能够进行计算，需要先导出行列式的若干基本性质，在通过这些性质，将复杂的行列式计算化为简单的行列式计算，也可以将高阶行列式的计算化为低阶行列式的计算。性质 1 设 A 是 n 阶矩阵，则detAT=detA。这个定理的重要意义在于，它告诉我们行列式的行和列的地位是平等的。确切地说，每个关于行的性质，对列必然成立；反之亦然。性质 2 行列式的任两行（或两列）互换，行列式变号。推论 行列式的某两行（或两列）相同时，行列式的值为 0。性质 3 用实数 乘以一行（或列）后，所得到的行列式等于原来的行列式乘以 。推论 行列式有两行（或两列）成比

10、例，则该行列式的值为零。特别的，当行列式有一行（或列）全为零时，行列式的值为零。性质 4生成树的计数及其应用 安徽 周冬第 6 页，共 15 页nnjjnjjnnnjjnjjnnnjj njj n abaaaaabbaa 1,1,1,111,1,1,11,1,1, 11 对列也有同样性质。推论 将行列式的任意行（或一列）乘以实数 ，再相应地加到另一行（或另一列）上去，则行列式的值不变。例如，当 j1 时 nnnnnjnj aaa 1221112211下面我们介绍一种计算行列式的方法。首先，不难证明 nnnnnnn aaaa 12222112212100今取行列式 nnbB 11det我们可以将

11、 化为上三角形式，记为 ，同时记录行交换次数 S。根据定B理 11，易知： nnS bB0det1et 2211 再利用刚才的结论，得 。niiSb1et对于矩阵 A，任取 2p 个自然数1i11)个连通分量 G1，G 2，G k，那么，我们可以重新安排 C 的行和列使得属于 G1 的顶点首先出现，然后是 G2。回忆行列式的性质 2，设我们一共进行了 t 次行交换，显然，我们同样需要进行 t 次列交换。因此，我们总共进行了 2t 次交换，所以，行列式的符号没有改变。重新安排后的矩阵如下图所示：带方框的 Gi 表示了 CGi。注意在方框以外的地方都是 0 因为任意两个连通分量之间没有边相连。设

12、r 是第 i 个连通分量中的第 j 个顶点，那么r 21 kijGC生成树的计数及其应用 安徽 周冬第 10 页，共 15 页00 ijGC3、如果 G 是一颗树，那么它的 Kirchhoff 矩阵 C 的任一个 n-1 阶主子式的行列式均为 1。证明：为了证明这条重要的性质，我们通过不断的变换 CrG从而得到一个上三角矩阵并且使得主对角线上所有的数字都是 1。第一步：我们把所有的顶点按照在树上离 vr 的距离从近至远排列。首先是 vr，然后是离 vr 距离为 1 的点，接下来是离 vr 距离为 2 的点。距离相同的点可以任意排列。我们按照这个顺序将所有的定点重新编号。同时，把以 r 为根的有

13、根树上 vi 的父结点 vj 称为 vi 的父亲，显然，在刚才得到的顺序中，v j 出现在 vi 之前。第二步：将 CrG的 n-1 行和 n-1 列按照刚才得到的顺序重新排列。因为行列都需要交换，所有总交换次数是偶数，C rG的行列式不边。第三步：按照刚才得到的顺序的逆序处理，对于每个 i，如果 vi 的父亲vj 不等于 vr，则把第 i 列加到第 j 列上去。这样处理过之后，我们来看一下现在的 CrG是否和我们的希望相同。我们通过归纳法来证明。显然，最后一列符合要求，因为最后一个点只和它的父亲之间有边，它的度为 1。假设当前处理的是第 i 列，并且第i+1 至第 n-1 列都符合要求。我们

14、设 vi 的父亲是 vj，它有 k 个孩子，显然，只有第 i1，i 2，i k 列才会加到第 i 列上来。所kiiivv， 21有这些列，都在第 i 行有个-1 而在对角线上有个 1，而第 i 列在第j、i 1，i 2，i k 行上为-1 而在第 i 行上为 k+1。每一列加上来的时候，第 i 行第 i 列减一同时与之相对的那一列加一变为 0。最后第第 i 行第 i列变为 1，第 i1，i 2，i k 行变为 0。也就是说，最后 CrG会变成上三角矩阵并且主对角线上所有的数字都是 1。这就证明了我们的结论。在证明 Matrix-Tree 定理的过程中，我们使用了无向图 G 的关联矩阵 B。B是一个 n 行 m 列的矩阵，行对应点而列对应边。B 满足，如果存在一条边e=vi,vj，那在 e 所对应的列中，v i 和 vj 所对应的那两行，一个为 1、另一个为-1，其他的均为 0。至于谁是 1 谁是-1 并不重要，如下图所示。接下来，我们考察 BBT。容易证明，(BB T)ij 等于 B 的第 i 行与第 j 列的点积。