| 单词 | 计算组合学和计算图论 |
| 释义 | 【计算组合学和计算图论】 拼译：computational combinatorics and graph theory 20世纪70年代发展起来的研究解决组合学和图论方面的理论问题与应用问题的计算机方法。由于图论是组合学的一部分，两者紧密相联，因此这里同时介绍计算组合学和计算图论。 由于计算机的迅速发展和普及，组合学和图论又是计算机科学的重要理论基础，因此计算组合学和计算图论的发展对计算机的理论与应用，以及组合学本身都有很重要的意义。计算组合学和计算图论的第1个重大成就是1976年美国K．Appel和W．Haken用计算机证明著名的四色定理：任何一个平地图可用4种颜色着色使任何两个相邻的国家着不同的颜色。同时在其它方面也不断取得新的成果，我们可以归纳为以下几个方面。1．组合对象的非数值计算的方法。最常用的非数值计算包括搜索、查找、排序等问题。搜索与查找，就是在一个集合中如何查找一个特定的元素或快速、不重复地考察每一个元素，这是许多实际问题和计算机软件设计中常遇的问题。排序问题是将某一个集合的所有元素按某个指标进行排列，也是任何一个计算机语言系统必须处理的问题。对于搜索与查找，虽然有各种不同的算法，但基本的方法可以分为两类：一种称为深度优先搜索法(Depth first search)；另一种称为广度优先搜索法(Breadth first search)。在计算机数据结构中对所谓栈(stack)和队(queue)的处理就是分别用这两种方法。今后的发展方向大致有两方面：一是针对新的实际问题，以这两种基本方法为指导，不断设计出新的算法，二是随着计算机的进一步发展，例如并行机的出现，需要处理更加复杂的搜索、查找与排序等问题。2．组合最优化算法的研究。有许多实际问题和理论问题涉及在一个集合中寻找在某种意义下最优的元素，这就是组合最优化问题。几乎所有有关寻找最优元素的问题都可用组合数学与图论来建立数学模型和寻找适当的算法，最常见的是以下几类：(1)最短路与最优树问题。(2)最大匹配与最优匹配问题。(3)网络流中的最大流与最小流问题。(4)旅行商问题：求通过各个城市的路程或费用最小的旅行路线。(5)中国邮递员问题：求通过各个街道的最短投递路线。(6)最优排序问题：若干台机器和若干种加工另件，如何安排加工次序使总的加工时间最短。除了这6类问题外，还有一大类问题是线性规划与整数规划，它是运筹学的基本内容，同时也属于组合优化的范围。在这几类问题中，有些问题在一定条件下已有好的算法，但有些至今未找到好的算法，例如旅行商问题是一个著名的难题，在最优排序问题中，有些情况也是十分困难的。组合优化有非常广阔的发展前景，由于实际问题层出不穷，不断会有新的最优化问题需要解决；另一方面，旅行商问题和某些最优排序问题远远没有解决，可进一步从理论上、算法上加以研究。3．组合计数的计算机方法，所谓组合计数问题就是求某一类组合结构的数目。经典的组合计数方法是求得一个有限的计数公式、递推公式或生成函数等，随看计算机的发展，对于一些找不到简单的计数公式的问题，可以设计适当的计算机方法来计算具体的数目，这些方法大多以群论中的Burnside-Polya理论为基础，由此得到的一些计数方法用手工是很难进行的，计算机使这些方法有了实际的意义，这些方法在图的计数问题获得了较为系统的成果，在70年代末已有专著出版，并且在化学方面得到了成功的应用。加拿大R．C．Read在这些方面作出了突出的贡献。中国学者也有不少新的成就。目前仍有许多组合结构的计数问题没有解决，例如著名的Hamilton图的计数问题，用计算机已经得到低阶的数目，能否改进方法得到更高阶的结果，尚待研究。4．图的构造、同构检验方法以及图的参数的计算方法。把某一类组合结构全部构造出来不仅具有实际意义，而且在理论上也有很大的价值。例如组合设计中拉丁方的结构，图论中各类图的构造等。与构造问题紧密联系的是同构检验问题，因为我们要构造的是互不同构的图。判断两个图是否同构可转化为判断两个0－1矩阵经过行(列)调换后能否变为相同的问题，如果用枚举法来做，计算复杂度是n!量级的。有人对次数加以限制的图的同构检验找到了好的算法，但算法比较复杂。计算机还可用来研究图的一些性质与参数，例如前面提到的四色定理的证明，如果加以推广，就是求一个图的色数。还有求一个图的连通度，判断一个图的平面性等问题。此外，计算图论还在一些新的高科技领域如大规模集成电路(VLSI)的设计与研究中取得新的成果。【参考文献】：1 Read R C，Selected Topics in Graph Theory， Academic Press，1978，417～4442 徐利治等．计算组合数学．上海：上海科学技术出版社，19833 Papadimitriou C H等著．组合最优化和复杂性．刘振宏等译．北京：清华大学出版社，19884 胡冠章．数学的实践与认识，1989，3∶76～795 Tinhofer G，et al．Computational Graph Theory，Comput．Suppl 7，springer，Vienna，19906 Hu G，et al．Applied Mathematics A Journal of Chinese ∪-niversity，1993，B8(1)∶25～31(清华大学胡冠章教授撰) |
| 随便看 |
科学参考收录了7804条科技类词条，基本涵盖了常见科技类参考文献及英语词汇的翻译，是科学学习和研究的有利工具。