生成树的计数及其应用

生成树的计数及其应用安徽周冬第1页，共14页生成树的计数及其应用安徽周冬目录生成树的计数及其应用.........................................................................................1目录.........................................................................................................................1摘要.........................................................................................................................2关键字.....................................................................................................................2问题的提出.............................................................................................................2[例一]高速公路（SPOJp104Highways）...............................................2[分析].......................................................................................................2预备知识.................................................................................................................2排列..................................................................................................................3行列式..............................................................................................................4新的方法.................................................................................................................7介绍..................................................................................................................7证明..................................................................................................................9理解................................................................................................................12具体应用...............................................................................................................12[例二]员工组织（UVAp10766OrganisingtheOrganisation）..........13[分析].....................................................................................................13[例三]国王的烦恼（原创）........................................................................13[分析].....................................................................................................14总结.......................................................................................................................14参考文献...............................................................................................................14生成树的计数及其应用安徽周冬第2页，共14页摘要在信息学竞赛中，有关生成树的最优化问题如最小生成树等是我们经常遇到的，而对生成树的计数及其相关问题则少有涉及。事实上，生成树的计数是十分有意义的，在许多方面都有着广泛的应用。本文从一道信息学竞赛中出现的例题谈起，首先介绍了一种指数级的动态规划算法，然后介绍了行列式的基本概念、性质，并在此基础上引入Matrix-Tree定理，同时通过与一道数学问题的对比，揭示了该定理所包含的数学思想。最后通过几道例题介绍了生成树的计数在信息学竞赛中的应用，并进行总结。关键字生成树的计数Matrix-Tree定理问题的提出[例一]高速公路（SPOJp104Highways）一个有n座城市的组成国家，城市1至n编号，其中一些城市之间可以修建高速公路。现在，需要有选择的修建一些高速公路，从而组成一个交通网络。你的任务是计算有多少种方案，使得任意两座城市之间恰好只有一条路径？数据规模：1≤n≤12。[分析]我们可以将问题转化到成图论模型。因为任意两点之间恰好只有一条路径，所以我们知道最后得到的是原图的一颗生成树。因此，我们的问题就变成了，给定一个无向图G，求它生成树的个数t(G)。这应该怎么做呢？经过分析，我们可以得到一个时间复杂度为O(3n*n2)的动态规划算法，因为原题的规模较小，可以满足要求。但是，当n再大一些就不行了，有没有更优秀的算法呢？答案是肯定的。在介绍算法之前，首先让我们来学习一些基本的预备知识。预备知识下面，我们介绍一种重要的代数工具——行列式。为了定义行列式，我们首先来看一下排列的概念。生成树的计数及其应用安徽周冬第3页，共14页排列定义1由1，2，…，n组成的一个有序数组i1i2…in称为1，2，…，n的一个排列。由排列的定义可知，i1，i2，…，in表示了n个不同的自然数，同时i1，i2，…，in中的每个自然数都是集合Sn={1，2，…，n}中的一个元素，换句话说，ninii，，，2121定义了集合Sn到自身上的一个一一对应。这个一一对应可以用符号niiin2121记之，称为置换，而上述一一对应可以改写为njnjjijijij，，，212其中j1j2…jn是1，2，…，n的一个排列。所以这个一一对应也可以用符号njjjniiijjj2121记之，因此对1，2，…，n的任一排列j1j2…jn，可定义njjjnniiijjjiiin21212121任取一个排列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和对换方式无关。将它改写成niiin2112，即的奇排列时。，，，是，当的偶排列时；，，，是，当niiiniiiiiinnntn211211112212121生成树的计数及其应用安徽周冬第4页，共14页n个确定自然数1，2，…，n的排列，可以看作是集合Sn={1，2，…，n}到自身上的一个一一对应。将这个概念推广，任取n个元素的集合S={a1，a2，…，an}。对于集合S到自身上的一一对应niniiaaaaaa，，，2121niiiaaa21称为naaa，，，21的一个排列。容易看出，niiiaaa21是naaa，，，21的排列的充要条件是i1i2…in是1，2，…，n的排列。同样，排列niiiaaa21变为标准排列naaa21的对换总次数的奇偶性和对换方式无关，因此引入符号的奇排列时。是，当的偶排列时；是，当niiiniiitiiinaaaaaaaaaaaaaaaaaannn,,,1,,,11212121212121其中t是某一种将niiiaaa21变为naaa21的对换方式的对换总次数。下面我们介绍行列式。行列式一阶行列式是一个变量a11的函数det(a11)=a11，也可以改写成为1111111111detaaa二阶行列式是四个变量a11，a12，a21，a22的函数1212221122211211detaaaaaaaa，也可以改写成21211221212221121112detiiiiaaiiaaaa三阶行列式是九个变量aij(i，j=1，2，3)的函数322311332112312213322113312312332211333231232221131211detaaaaaaaaaaaaaaaaaaaaaaaaaaa，同样可以改写成为生成树的计数及其应用安徽周冬第5页，共14页321321321123321333231232221131211123detiiiiiiaaaiiiaaaaaaaaa通过观察一、二、三阶行列式的定义，我们得出了n阶行列式的一般定义。定义3n阶矩阵A的行列式是一实数，记作detA，它定义为nnniiiiiinnaaaiiinA212121122112det行列式有下列几种常用的符号：AaaaaaaaaAnnnnnnnn11111111detdet由行列式的定义可知，利用定义直接计算行列式是很困难的，只有在阶数低时才可以直接用定义计算。为了能够进行计算，需要先导出行列式的若干基本性质，在通过这些性质，将复杂的行列式计算化为简单的行列式计算，也可以将高阶行列式的计算化为低阶行列式的计算。性质1设A是n阶矩阵，则detAT=detA。这个定理的重