论文--数据关系的简化

《论文--数据关系的简化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据关系的简化I.摘要数据之间的关系有着和数据本身同等的重要性。最常见的数据关系有线性关系、树关系和图关系。信息学竞赛的本质就是对数据的充分挖掘。然后有时候挖掘太过充分，反而会把问题复杂化。本来将讨论的就是如何通过适当的简化数据关系，实现数据的合理挖掘。II.关键字树，图，序列，数据关系III.引言我们经常面对大量的数据，但是他们之间不是杂乱无章的。一些用道路连接的城市表现出来的数据关系是图；一些行政部门的上司下属关系表现出来的是树关系；学校的成绩排名表现出来的数据关系是线性关系。图、树和线性关系是我们在生活中、也是在信息学竞赛中遇到的三种最常见的关系。虽然信息

2、学竞赛强调对输入信息的充分挖掘和应用，但有时候关系过于复杂反而让人眼花缭乱。本文就是要介绍一种重要的思想：简化数据结构。具体的说可以把图简化成树、把树简化成线性结构。这看起来不可思议，因为在简化的过程中必然会丢失一些信息，但是通过本文接下来的分析和举证，你又会发现这是切实可行的一种思想。IV.简化图关系先来看一个题目：坐船问题雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。学校希望每个同学都坐上船，但是小船的租用费用很高，学校想要租用最少的船。请问：学校至少要租多少船？我们可以把每个学生看作一个顶点。如果两个学

3、生同姓，就在两者之间连一条红边；如果他们同名，就在两者之间连一条蓝边。这样我们就把问题的全部信息都毫无遗漏的包含在这个图里面了。剩下的问题就是求一个最小边覆盖，实际上也就是求最大匹配。这个图并不一定是二分图，所以求最大匹配涉及到带花树，十分复杂。有没有更好的方法呢？首先假设这个图是连通的。下面我们用一棵树来表示这个图。这是一颗二叉树。每个节点的左儿子（如果存在）和它同姓，右儿子（如果存在）和它同名。构树算法如下：假设树中已经含有k个点了。如果k=n，那么构造算法结束。9否则因为整个图是连通的，剩下的点中至少有一个和当前的树连通。不妨设剩下的某个点P和树中的一个点

4、T之间有边。第一种情况是P和T同姓。沿着T的左儿子不断的“往左”走，直到到达某一个点X无法继续前进（也就是X没有左儿子）。因为X和T同姓，所以它也必然和P同姓；同时X没有左儿子，令P为X的左儿子即可。这样树的规模就增大了1。第二种情况是P和T同名。和第一种情况类似。于是我们总是可以把树的规模增大1，直到把所有的点都包含到树中。构造出这样一棵树有什么好处呢？下面考虑任意一个叶子节点P，设它的父亲是F。如果P是F的唯一孩子，那么令P和F坐一条船。树的规模就减小了2。否则F有两个孩子，设另一个孩子是Q。为了方便讨论，不妨设P是F的左儿子，Q是F的右儿子。第一种情况：F

5、是根节点。这时候总共有三个学生还没坐船。至少要两条船。令F和P坐一条船，Q坐一条船即可。第二种情况：F是它父亲的左儿子。设F的父亲是F’。……FPQF’……PF’令F和Q坐一条船。然后把F和Q从树中删除。此时P的左儿子P落了单。因为F和F’同姓，F又和P同姓，所以F’和P同姓。令P为F’的左儿子即可。这就保证了树的连通性。第三种情况：F是它父亲的右儿子。……FPQF’……F’Q和第二种情况类似。见上图。通过以上算法，可以不断的把树的规模减小。如果树有n个节点，那么最后的结果就是需要条船。毫无疑问这是最优解。9如果图不连通，那么把每个连通图按照上述算法分别处理，最

6、后把船数相加即可。整个算法的复杂度是O(n)，不仅效率上大大优于匹配算法，而且两者的编程复杂度更是不能同日而语。这个题目的数据是学生，数据关系是同姓或者同名。毫无疑问，用图来表示学生之间的关系是很自然的想法，而且图也的确可以毫无遗漏的把所有信息包含进去。但是正因为图的包罗万象，使得我们束手无策。虽然存在匹配算法，但是它不仅思维、编程复杂度高，而且效率也不尽人意。在思维的路上转一个弯，我们用一棵二叉树来表现数据关系。尽管有些人之间的信息被忽略了，比如根节点和某个叶子节点可能同姓或者同名、而在树中他们两者之间也许没有直接关联的边；我们反而能够更加有效率的应用这些简化

7、后的数据关系解题。可见数据和数据关系的利用也不是越充分越好，有时候合理的运用更有效。下面我们再来看一个例子。仙人掌图的判定如果一个有向图：1.它是一个强连通图。2.它的任意一条边都属于且仅属于一个环。这个图就称为仙人掌图。输入一个n个节点，m条边的图（1<=n,m<=105），请判断它是不是仙人掌图。为了对仙人掌图有一个感性认识，我们先看下面三个图。a)非强连通b)仙人掌图c)红色的弧同时属于两个圈1234其中a)和c)都不是仙人掌图，因为a)不是强连通的、c)中的红弧同时属于两个圈1à2à3à4à1和1à2à4à1。b)就是一个仙人掌。直观的说，仙人掌图就是一

8、个一个的圈直接“粘”在一