算法合集之《生成树计数附其应用》.doc

生成树的计数及其应用安徽周冬目录生成树的计数及其应用 1文档来自于网络搜索目录 1文档来自于网络搜索摘要 2文档来自于网络搜索关键字 2文档来自于网络搜索问题的提出 2文档来自于网络搜索[例一]高速公路(SPOJp104Highways) 2文档来自于网络搜索[分析] 2文档来自于网络搜索预备知识 2文档来自于网络搜索排列 3文档来自于网络搜索行列式 4文档来自于网络搜索新的方法 7文档来自于网络搜索介绍 7文档来自于网络搜索证明 9文档来自于网络搜索理解 12文档来自于网络搜索具体应用 12文档来自于网络搜索[例二]员工组织(anisation) 13文档来自于网络搜索[分析] 13文档来自于网络搜索[例三]国王的烦恼(原创) 13文档来自于网络搜索[分析] 14文档来自于网络搜索总结 14文档来自于网络搜索参考文献 14文档来自于网络搜索摘要 在信息学竞赛中,有关生成树的最优化问题如最小生成树等是我们经常遇到的,而对生成树的计数及其相关问题则少有涉及。事实上,生成树的计数是十分有意义的,在许多方面都有着广泛的应用。本文从一道信息学竞赛中出现的例题谈起,首先介绍了一种指数级的动态规划算法,然后介绍了行列式的基本概念、性质,并在此基础上引入Matrix-Tree定理,同时通过与一道数学问题的对比,揭示了该定理所包含的数学思想。最后通过几道例题介绍了生成树的计数在信息学竞赛中的应用,并进行总结。文档来自于网络搜索关键字 生成树的计数Matrix-Tree定理问题的提出[例一]高速公路(SPOJp104Highways) 一个有n座城市的组成国家,城市1至n编号,其中一些城市之间可以修建高速公路。现在,需要有选择的修建一些高速公路,从而组成一个交通网络。你的任务是计算有多少种方案,使得任意两座城市之间恰好只有一条路径?文档来自于网络搜索 数据规模:1≤n≤12。[分析] 我们可以将问题转化到成图论模型。因为任意两点之间恰好只有一条路径,所以我们知道最后得到的是原图的一颗生成树。因此,我们的问题就变成了,给定一个无向图G,求它生成树的个数t(G)。这应该怎么做呢?文档来自于网络搜索经过分析,我们可以得到一个时间复杂度为O(3n*n2)的动态规划算法,因为原题的规模较小,可以满足要求。但是,当n再大一些就不行了,有没有更优秀的算法呢?答案是肯定的。在介绍算法之前,首先让我们来学习一些基本的预备知识。文档来自于网络搜索预备知识 下面,我们介绍一种重要的代数工具——行列式。为了定义行列式,我们首先来看一下排列的概念。 排列定义1由1,2,…,n组成的一个有序数组i1i2…in称为1,2,…,n的一个排列。由排列的定义可知,i1,i2,…,in表示了n个不同的自然数,同时i1,i2,…,in中的每个自然数都是集合Sn={1,2,…,n}中的一个元素,换句话说,文档来自于网络搜索定义了集合Sn到自身上的一个一一对应。这个一一对应可以用符号记之,称为置换,而上述一一对应可以改写为其中j1j2…jn是1,2,…,n的一个排列。所以这个一一对应也可以用符号记之,因此对1,2,…,n的任一排列j1j2…jn,可定义任取一个排列i1i2…in,将其中两个相邻的自然数ij-1,ij对换一下,便造出一个新的排列i1i2…ij-2ijij-1ij+1…in,称为原来排列的对换排列,这样一种步骤成为对换。显然,对于任何一个排列经过若干次对换后都可以变成标准排列12…n。不过,不管经过什么途径作对换,在给定排列i1i2…in后,关于对换的次数有下列重要定理。文档来自于网络搜索定理1将任意一个排列i1i2…in通过对换变成标准排列12…n,所需的对换次数的奇偶性与对换方式无关。文档来自于网络搜索利用这个定理,我们引入定义2一个排列i1i2…in称为偶(奇)排列,如果有一种方式,经过偶(奇)数次对换后,可以将排列i1i2…in变为标准排列12…n。文档来自于网络搜索设排列i1i2…in经过t次对换后变为标准排列12…n,则数值(-1)t和对换方式无关。将它改写成,即文档来自于网络搜索n个确定自然数1,2,…,n的排列,可以看作是集合Sn={1,2,…,n}到自身上的一个一一对应。将这个概念推广,任取n个元素的集合S={a1,a2,…,an}。对于集合S到自身上的一一对应文档来自于网络搜索 称为的一个排列。容易看出,是的排列的充要条件是i1i2…in是1,2,…,n的排列。 同样,排列变为标准排列的对换总次数的奇偶性和对换方式无关,因此引入符号其中t是某一种将变为的对换方式的对换总次数。下面我们介绍行列式。行列式一阶行列式是一个变量a11的函数det(a11)=a11,也可以改写成为 二阶行列式是四个变量a11,a12,a21,a22的函数,也可以改写成 三阶行列式是