算法合集之《生成树的计数及其应用》.ppt

生成树的计数及其应用 芜湖一中周冬 引入 最小 大 生成树最小 大 度限制生成树最优比率生成树 生成树 生成树的计数 例一 高速公路 一个国家需要在n座城市之间建立通信网络 某些城市之间可以铺设通信线路 要求任意两座城市之间恰好有一条通讯路线 试求方案个数 满足 1 n 12 分析 首先将问题抽象成图论模型点 城市边 通讯线路任意两点之间恰好只有一条路径这是一颗树 问题转化为 给定一个n个点的无向图 其中无重边和自环 试求其生成树的个数 分析 由于原题规模较小 因此我们可以使用一些复杂度较高的算法来解决它 如指数级的动态规划算法 但是 如果规模更一些呢 预备知识关联矩阵 Kirchhoff矩阵 大 图的关联矩阵 对于无向图G 我们定义它的关联矩阵B是一个n m的矩阵 并且满足 如果ek vi vj 那么Bik和Bjk一个为1 另一个为 1 而第k列的其他元素均为0 图G的关联矩阵如右下角所示 图的关联矩阵 图的关联矩阵有什么特殊的性质呢 我们不妨来考察一下B和它的转置矩阵BT的乘积 图的关联矩阵 根据矩阵乘法的定义 我们可以得到 也就是说 BBTij是B第i行和第j行的内积 因此 当i j时 BBTij vi的度数 而当i j时 如果存在边 vi vj 那么BBTij 1 否则BBTij 0 我们通常将BBT称为图的Kirchhoff矩阵 图的Kirchhoff矩阵 对于无向图G 它的Kirchhoff矩阵C定义为它的度数矩阵D减去它的邻接矩阵A 显然 这样的定义满足刚才描述的性质 有了Kirchhoff矩阵这个工具 我们可以引入Matrix Tree定理 对于一个无向图G 它的生成树个数等于其Kirchhoff矩阵任何一个n 1阶主子式的行列式的绝对值 所谓n 1阶主子式 就是对于任意一个r 将C的第r行和第r列同时删去后的新矩阵 用Cr表示 Matrix Tree定理 让我们通过一个例子来解释一下定理 如图所示 G是一个由5个点组成的无向图 它的Kirchhoff矩阵C为 Matrix Tree定理 我们取r 2 根据行列式的定义易知 detC2 11 这11颗生成树如下图所示 这个定理看起来非常 神奇 让我们尝试着去证明一下吧 定理的证明 经过分析 我们可以发现图的Kirchhoff矩阵C具有一些有趣的性质 C的行列式总是0 如果图是不连通的 则C的任一个n 1阶主子式的行列式均为0 如果图是一颗树 那么C的任一个n 1阶主子式的行列式均为1 证明略 定理的证明 我们知道 C BBT 因此 我们可以把C的问题转化到BBT上来 设Br为B去掉第r行得到的矩阵 容易知道Cr BrBrT 这时 根据Binet Cauchy公式 我们可以将Cr的行列式展开 其中 是把Br中属于x的列抽出后形成的新矩阵 定理的证明 注意观察上面的式子 实际上是图Gx的Kirchhoff矩阵的一个n 1主子式 其中Gx是由所有的顶点和属于x的边组成的一个G的子图 若属于x的n 1条边形成了一颗树时 由Kirchhoff矩阵的性质可知等于1 若属于x的n 1条边没有形成树 则Gx中将至少含有两个连通块 这时等于0 因此 我们认为 每次从边集中选出n 1条边 若它们形成了生成树 则答案加1 否则不变 定理的理解 当x取遍边集所有大小为n 1的子集后 我们就可以得到原图生成树的个数 这样我们成功证明了定理 刚才的证明过程看起来有些 深奥 下面就让我们从直观上来理解一下这个定理的原理 定理的理解 试求方程x1 x2 x3 2所有非负整数解的个数 这是大家都很熟悉的一道组合计数问题 通常的解法是 设有2个1和两个 我们将这4个元素任意排列 那么不同的排列的个数就等于原方程解的个数 即 为什么要这样做呢 定理的理解 我们将所有6种排列列出后发现 一种排列就对应了原方程的一个解 11对应x1 0 x2 0 x3 2 1 1对应x1 0 x2 1 x3 1 11 对应x1 0 x2 2 x3 0 也就是说 我们通过模型的转化 找出了原问题和新问题之间的对应关系 并利用有关的数学知识解决了转化后的新问题 也就同时解决了原问题 这种转化的重要意义在于 在不同问题之间的架起了互相联系的桥梁 定理的理解 回到我们讨论的Matrix Tree定理上来 我们同样是经过模型的转化后 将图模型转化为矩阵模型 发现Binet Cauchy公式展开式中的每一项对应着边集一个大小为n 1的子集 其中 值为1的项对应一颗生成树 而没有对应生成树的项值为0 这样 将问题转化为求展开式中所有项之和 再利用已有的数学知识 就可以成功解决这个问题 两个问题的对比 方程的解 图的生成树 类似 排列方案 展开式的项 类似 对应 对应 不同之处在于 相互之间的对应关系更加隐蔽 复杂需要更加强大的数学理论来支撑 定理的扩展 利用该定理 我们可以容易得到著名的Cayley公式 完全图Kn有nn 2颗生成树 我们刚才只对图中没有重边的情况进行了分析 实际上 图中有重边时该定理仍然成立 并且证明与没有重边的情况类似 该定理也可以扩展到有向图上 用来计算有向图的外向树的个数 例二 UVap10766OrganisingtheOrganisation 例三 国王的烦恼 信息学竞赛中的应用 例三 国王的烦恼 一个王国由n座城市组成 由于遭到了洪水的袭击 许多道路都被冲毁了 国王组织了专家进行研究 列举出了所有可以正常通行的道路 其中有的已经被冲毁 需要重新修复 有的则可以继续使用 并且所有可以继续使用的道路没有形成环 例三 国王的烦恼 国王希望修建最少的道路 使得任意两个城市之间都能互达 请你计算可行方案的总数 下面我们通过一个例子来看一下 如右图所示 王国由a b c d 4座城市组成其中蓝色边表示可以通行但需要修复的道路红色边表示可以继续使用的道路共有2种方案 如右下角所示 方案1 方案2 问题分析 难点在于由于必选边的存在 我们无法直接应用Matrix Tree定理我们知道 如果要求生成树中必须包含某条边e 那么 我们可以将e压缩 将原图的问题转化到新图上来 因此 我们需要1 将所有的必选边压缩2 求压缩后的图的生成树的个数 问题分析 压缩一条边的时间复杂度为O n 而最多只要压缩n 1条边 因此 第一步的复杂度为O n2 计算一个图的生成树的个数的时间复杂度依赖于求其Kirchhoff矩阵行列式的时间复杂度 为O n3 因此 整个算法的时间复杂度为O n3 总结 矩阵的行列式 图的生成树 模型转化 数学证明 扎实的数学功底是解决问题的保证 创造性的联想则是解决问题的灵魂 谢谢大家 Cayley公式的证明 首先计算完全图Kn的Kirchhoff矩阵的一个n 1阶主子式C1 Kn 下面我们对C1 Kn 进行化简 第2至第n 1列均减掉第一列 得到如下的矩阵 Cayley公式的证明 我们可以发现 除了第一列以外 其他每列都在第一行上有一个 n 在对角线上有一个n 而其他位置上的元素均为0 现在 我们把第2至第n行都加到第一行上去 可以得到如下矩阵 Cayley公式的证明 再次观察这个矩阵 我们可以发现 在第一行上只有一个1 剩下部分中 只有对角线上的数字为n 其他元素都是0 因此 完全图Kn的生成树的个数为nn 2 SPOJp9