生成树计数与其应用.doc

生成树的计数及其应用 安徽 周冬 目录 TOC \o 1-4 \h \z \u HYPERLINK \l _Toc157242663 生成树的计数及其应用 PAGEREF _Toc157242663 \h 1 HYPERLINK \l _Toc157242664 目录 PAGEREF _Toc157242664 \h 1 HYPERLINK \l _Toc157242665 摘要 PAGEREF _Toc157242665 \h 2 HYPERLINK \l _Toc157242666 关键字 PAGEREF _Toc157242666 \h 2 HYPERLINK \l _Toc157242667 问题的提出 PAGEREF _Toc157242667 \h 2 HYPERLINK \l _Toc157242668 [例一]高速公路（SPOJ p104 Highways） PAGEREF _Toc157242668 \h 2 HYPERLINK \l _Toc157242669 [分析] PAGEREF _Toc157242669 \h 2 HYPERLINK \l _Toc157242670 预备知识 PAGEREF _Toc157242670 \h 2 HYPERLINK \l _Toc157242671 排列 PAGEREF _Toc157242671 \h 3 HYPERLINK \l _Toc157242672 行列式 PAGEREF _Toc157242672 \h 4 HYPERLINK \l _Toc157242673 新的方法 PAGEREF _Toc157242673 \h 7 HYPERLINK \l _Toc157242674 介绍 PAGEREF _Toc157242674 \h 7 HYPERLINK \l _Toc157242675 证明 PAGEREF _Toc157242675 \h 9 HYPERLINK \l _Toc157242676 理解 PAGEREF _Toc157242676 \h 12 HYPERLINK \l _Toc157242677 具体应用 PAGEREF _Toc157242677 \h 12 HYPERLINK \l _Toc157242678 [例二]员工组织（UVA p10766 Organising the Organisation） PAGEREF _Toc157242678 \h 13 HYPERLINK \l _Toc157242679 [分析] PAGEREF _Toc157242679 \h 13 HYPERLINK \l _Toc157242680 [例三]国王的烦恼（原创） PAGEREF _Toc157242680 \h 13 HYPERLINK \l _Toc157242681 [分析] PAGEREF _Toc157242681 \h 14 HYPERLINK \l _Toc157242682 总结 PAGEREF _Toc157242682 \h 14 HYPERLINK \l _Toc157242683 参考文献 PAGEREF _Toc157242683 \h 14 摘要 在信息学竞赛中，有关生成树的最优化问题如最小生成树等是我们经常遇到的，而对生成树的计数及其相关问题则少有涉及。事实上，生成树的计数是十分有意义的，在许多方面都有着广泛的应用。本文从一道信息学竞赛中出现的例题谈起，首先介绍了一种指数级的动态规划算法，然后介绍了行列式的基本概念、性质，并在此基础上引入Matrix-Tree定理，同时通过与一道数学问题的对比，揭示了该定理所包含的数学思想。最后通过几道例题介绍了生成树的计数在信息学竞赛中的应用，并进行总结。 关键字 生成树的计数 Matrix-Tree定理 问题的提出 [例一]高速公路（SPOJ p104 Highways） 一个有n座城市的组成国家，城市1至n编号，其中一些城市之间可以修建高速公路。现在，需要有选择的修建一些高速公路，从而组成一个交通网络。你的任务是计算有多少种方案，使得任意两座城市之间恰好只有一条路径？ 数据规模：1≤n≤12。 [分析] 我们可以将问题转化到成图论模型。因为任意两点之间恰好只有一条路径，所以我们知道最后得到的是原图的一颗生成树。因此，我们的问题就变成了，给定一个无向图G，求它生成树的个数t(G)。这应该怎么做呢？ 经过分析，我们可以得到一个时间复杂度为O(3n*n2)的动态规划算法，因为原题的规模较小，可以满足要求。但是，当n再大一些就不行了，有没有更优秀的算法呢？答案是肯定的。在介