沈阳理工大学学士学位论文

subjects glow vigorous vitality. Combinatorial mathematics is the study of the rich content, application widespread discipline. It is also a method, pay attention to skills subject. Combinatorial mathematics power lies in a combination of mathematical problems can get perfect solution often depends on whether we can find ingenious solutions, computer powerful computing power to seek for the combinatorial mathematics problems clever solution provides the infinite possible, at the same time, combinatorial mathematics in turn effectively promoted the development of the computer science.

45

沈阳理工大学学士学位论文

附录B 中文翻译

浅析组合数学

组合数学,又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。电子计算机处理的信息，都是仅用“0”与“1”两个简单数字表示的信息,或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。

组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。离散构形问题是组合数学的主要研究内容，主要包括：①构形的存在性问题；②构形的构造性问题；③构形的计数问题；④构形的最优化问题。 1666年，《组合艺术》一书是组合数学发展史上的里程碑，在此后的三百多年里，组合数学取得了快速发展，特别是20世纪40年代以来，电子计算机的广泛应用对组合数学产生了巨大影响，组合数学在与计算机科学相结合中获得了广阔的发展空间，从而也 为计算机科学奠定了理论基础。组合数学不仅计算机技术中的网络优化、编码和密码学中有重要的应用价值，在企业管理、交通规 划、金融分析等领域都有重要的应用。在2l世纪，组合数学将会紧密的伴随着计算机科学向前发展，组合论技巧将会计算机化，进而成为各种解算机的重要组成部分。

1组合数学中经典问题

组合数学中的经典问题[6-9]主要包括：①棋盘完美覆盖；②切割立方体；③幻方；④四色问题；⑤36军官问题；⑥最短路径；⑦NIM 取子问题；⑧羊狼菜过河问题；⑨中国邮递员问题；⑩稳定婚姻问题。以下重点介绍四色问题和中国邮递员问题。 1.1四色问题

四色问题即使用四种不同的颜色对世界地图着色。要求相邻国家的颜色相异。采用数学语占对本问题进行形式化描述如下：将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这4个数字之一来标记，而不会使相邻的两个区域得到相同的数字。

一个多世纪以来，在四色问题的研究证明过程中，由于对象问题复杂且缺乏数学通常的解题规范，人工直接验证不可行。本世纪70年代．电子计算机的迅速发展和广泛应用使四色问题的研究出现了转机。美国伊利诺斯大学的阿佩尔、哈肯等人在研究了前人各种证明方法和思想的基础后，从1972年起，开始了用计算机证明四色问题的研究工作。终于在1976年彻底解决了四色问题， 整个证明过程在计算机上花费了1200个小时。地图四色问题是第一个主要由计算机完成证明的数学难题。科学家们在研究和解决四色问题的过程中，还由此产生不少新的数学理论，发展了很多数学计算方法，刺激了拓扑学与图论的发展。 1.2中国邮递员问题

一个邮递员的工作是：按一定路线递送他所负责的街区的各条街道的邮件，最后返回邮局，要求邮递员必须走过他负责的街区的每一条街道至少一次，并希望选择一条总

46