对拟阵的初步研究..doc

对拟阵的初步研究 浙江省杭州第二中学 刘雨辰 摘要 拟阵中文又称矩阵胚，英文名matroid。1935年美国数学家Whitney首先提出了拟阵的概念。拟阵是组合优化与图论的重要内容，在近几十年得到了空前的发展，成为了一门博大精深的学科。 本文对拟阵进行了初步探讨，第一部分引入了拟阵的概念，第二部分提出了拟阵的最优化问题，并论证了其贪心算法的正确性，这两部分都将同步讲解2个实例，力求做到严谨而生动。第三部分讨论了一个拟阵最优化问题的实例。这三部分是本文的重点所在。第四部分给出一些拟阵的实例，重点是线性拟阵。拓展部分对一个有趣问题进行了简单讨论，有相当难度。附录I介绍了罗素悖论，附录II主要讨论第三部分中的问题如何用并查集实现。 拟阵理论非常难，需要有良好的数学功底才能深入研究。希望本文对拟阵的初步探讨能够使读者对拟阵理论有所认识。 关键字 拟阵 贪心算法 Shannon开关游戏 序言 拟阵中文又称矩阵胚，英文名matroid。1935年美国数学家Whitney首先提出了拟阵的概念。拟阵是他在研究线性无关时发现的。拟阵是组合优化与图论的重要内容，在近几十年得到了空前的发展，成为了一门博大精深的学科。 本文第一部分讨论了拟阵的的基本概念，第二部分提出了拟阵的最优化问题，并论证了其贪心算法的正确性，这两部分都将同步讲解2个实例，分别是众所周知的部分背包问题（即物品是不用整个拿，可以分割）与最小生成树问题，希望理论结合实例能够帮助读者更好地理解。第三部分讨论了一个拟阵最优化问题的实例。前三部分是本文的重点所在，难度适中，只要读者能够仔细读，慢慢读，反复体会，必能发现其奥妙所在。本文的第四部分和拓展部分比较难，其中有一些结论与证明，我自己也尚未搞明白，但因为这些结论都很有趣，我还是把它们写入了本文，这两部分主要为了拓宽读者视野，对拟阵论的博大精深有个更全面的认识。 理论和实践是不分家的，但历史上却有很多理论与应用不协调的例子：有的是为了实际用途，而发现了一些新方法，但理论根据却不很清楚，过了很久才被完善，并在完善后得到了空前的发展，比如著名的微积分；有的是先有了理论研究，但一直只作为一种智力游戏，并无实际用途，但却在某样事物发明以后，大显神威，于是成为了应用的理论根据，并得到空前的发展，比如著名的数论、组合数学。我们发现这些例子仅仅是时间上的一种暂时分离，而并不是说理论是没有用的，或实践不需要理论，只是两者被发现的早晚而已，而当两者都被发现以后，相辅相成，却能走得更快更好更远。如果我们认为拟阵没什么实际用途，应该不是因为应用还没被发现，只是没被我们发现，因为我们的知识还不够，我们不知道，仅此而已。拟阵是好的、美的，所以我要把它介绍给大家。 拟阵论很难，需要非常良好的数学基础才能学好，所以一般作为研究生的课程。我在研究过程中深感自己水平有限，诸如线性代数，拓扑学等数学基础知识都不懂，无奈只得边研究边学习。当然这样临时性的学习必然只能获得皮毛，但我还是在这种研究性学习中获得了无限乐趣。“吾生也有涯，其知也无涯”。知识是无穷尽的，我们要做的就是永远保持对知识的渴望，对真理的追求。这样也就称的上一个爱智慧的人了。 正文 第一部分：子集系统与拟阵的概念 定义： 子集系统是一个二元组，它须满足以下条件： 1、S是一个有限集。 2、L是由S的一些子集组成的有限非空集 3、遗传性：对任意，任意,有（可知必须是L的元素）。 拟阵是一个子集系统，它须满足： 4、交换性：对任意,,,存在一个,使。 对该定义做些解释是有益处的。我们把S看成一个班级所有的同学，L看成若干张名单的集合。一张名单记录了若干个同学，表示他们能够组成一个团队。遗传性说明，从一张名单中选出若干个同学组成的子名单仍存在于我们的名单集合，这是一种包容性。交换性说明，名单A上的人数如果少于名单B，则必然可以从B中选出一个人，该人不属于A，将该人加到A里形成的新名单仍然存在于我们的名单集合中，要注意，我们加到A中的人必须本来不是A的，并且必须是B的人，而不能是2张名单以外的人，外人不能干预。当然你也可以将S想象成别的事物组成的集合，而L则是将这些事物的组合看成基本元素的集合。由于是集合，万物皆可做元素（这句话严格地说是有问题的，比如著名的罗素悖论,详见附录I，任何数学体系都有其局限性与不完备性,因此需要公理化。在此只想说明拟阵是个抽象概念，而不是一个具体问题）。 遗传性和交换性是拟阵最根本的2条性质，拟阵上的其他性质都是基于这2个性质发展出来的。古人云：“君子务本，本立而道生。”这2条性质就是拟阵的本。拟阵是一种组合结构。研究组合结构的意义正如研究代数结构，一旦我们发现某个问题具有拟阵结构（符合4个基本条件，前2条比较显然，因为构造时就已完成，所以后面2个本的成立是