2-3论文正文 李海明

《2-3论文正文 李海明》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科毕业论文第23页共23页1引言说起来，组合数学是一门很古老的科学，人们对它的兴趣和研究肇源颇早，它起始于数学游戏，起初只是研究娱乐或审美要求所涉及的组合问题，据传，早在《河图》、《洛书》中我国人民就已对一些有趣的组合问题给出了正确的解答。贾宪，北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（WilliamGeogeHorne

2、r，1786-1837）的方法（1819）早770年。1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。但是，这门学科的飞速发展和不完善则是近几十年的事。这是多种因素促进的结果。一方面，它受到了许多新兴的应用和理论学科的推动和刺激，诸如计算科学、数字通讯理论、规划论和试验设计等等。另一方面，它自身内部的要求和力量也使它不停息地向前发展，因而这门具有悠久历史的学科又焕发出青春的光彩，在近几十年来显得异常活跃，并且颇富成果。今天无论在基础理论方面还是在应用科学当中都起着非常重要的作用，它已经发

3、展成为数学的一个重要分支，而且其影响正在迅速扩大。还有一个重要的原因，就是计算机的发展对社会所产生和将继续产生的巨大冲击力。由于计算机的闪电般的运算速度，为用组合数学来解决实际问题提供了一个理想的工具，要解决过去根本无法想象的大规模问题，现在已经成为可能与现实。对于组合数学人们有不同的认识。有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。组合数学问题在生活中随处可见。例如，本科毕业论文第23页共23页n个球队参赛，每队只和其他队比赛一次，计算在此赛制下总的比赛次数。网络路径问题

4、，计算两点之间路径有几种。还有身边普遍的分组问题。所有这些都是组合数学问题。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。组合数学算法与计算机技术的结合在现代科学技术领域发挥着极为重要的作用。对从事数学的人员来讲，学习数学组合可以提高分析问题的能力；对从事计算机的人员来讲，若没有组合数学的基础，就难以深入研究与分析有关算法。所以说，组合数学不仅是近年来最活跃、最迷人的数学分支，也是计算机科学技术的重要理论基础之一。组合数学近期发展的另一个重要原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组

5、合数学的思想和技巧不仅仅正在用于数学应用的传统自然科学领域，而且也用于电子工程、数字通信、物理学、力学、管理科学等诸多领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。组合数学中有许多计数和归纳原理。本文主要讨论网络路径问题、母函数与排列组合、容斥原理以及几何图形计数。1．1课题的背景及研究的目的和意义组合数学在在日常生活中的作用日益明显，本论文主要介绍研究组合数学中的四种组合方法。本论文主要目是对四种组合方法进行分析，研究其在简单数学问题中的应用。运用离散数学的思维培养自身分析、解决数学问题的能力。讨论组合方法在简单数学问题中的应用是本论文研究的

6、中心。1．2本课题研究的内容本论文主要研究的内容是对网络路径问题、母函数与排列组合、容斥原理以及几何图形计数等四种组合方法进行分析，研究其在简单数学中的应用。并且给出四种组合方法的基本组合解释，并应用这些组合方法解决简单的组合问题，理解组合方法在组合数学研究中的重要意义。培养自己初步研究数学问题的能力，从而使自己具有一定的科研独立性。2网络路径问题2.1路径问题的矩阵算法本科毕业论文第23页共23页路径问题是组合数学中的一个重要问题，本论文主要是在提出的矩阵算法的例子中总结出一般算法。首先规定所要讨论的图为简单的有向图，其中表示非空集合，，其元素称为弧。定义矩阵，其

7、中：若从点到点有边相连，则，若从点到点无边相连，则。中元素为1，表示1条从一步到的道路。我们再看，其中：.当且仅当，也就是说从到和从到都有直接相通的道路，所以的值表示从点出发经过，再到的路径数目。进而，一般有，其中，表示从出发k步到达的路径数目。2.2矩阵算法与乘法原理、加法原理的统一性2.2.1加法、乘法原理加法原理：如果完成一件工作，只要采取n类方式中的某一种方式就可以完成，第一类方式有种做法，第2类方式有种做法，，第n类方式有种做法，那么，完成这件工作共有种做法。乘法原理：如果完成一件工作，必须依次经过n个步骤，第1步有种做法，第2步有种做法，，第n步有种