离散数学漫谈
Ai
朱绪鼎教授 国立中山大学应用数学系86.6.18
离散数学是一门范围很广的学科,粗略的讲,离散数学是研究有离散结构的系统的科学.不过,
物理世界中除了离散的结构,难道还有其他的结构么?其实,万事万物均是一个个离散的粒子
组成.譬如,画一条直线段,墨水的痕迹并不真的是连续的.它是由很多个离散的点组成的(地
球上所有分子的个数也是有限的),只是我们肉眼无法分辨罢了.有趣的是,当计算机把这条线
段打印出来的时候,真的是把它当作一些点(大约几百个)打印出来的.
那么离散数学的研究对象是否包罗一切呢?当然不是.很多结构虽然本身并不是真正连续的,
但我们讲它看作是连续的结构却非常方便和确切.数学所描述的永远只是真是世界的一个近
似.选取什么样的模型来描述一个实际的系统,一般有两方面的考量.一是精确性,而是简法
性.只有充分精确,才会有作用.只有充分的简洁,我们才能处理.比如海水,可以说,它是一个
个水分子的运动.但我们把它看作是连续的流体,一则它充分的精确,二则我们没有能力分析
处理那么多水分子的运动.而有一些结构,则不可以看作是连续的结构,或者看作连续的结构
会很不精确.像是工厂企业各部门之间的联系,工程施工的工序,DNA序列的结构,交通,通讯
网络的结构,课程安排等等,都不是连续的结构.
至于哪一些问题应当看作连续的,哪一些应看作是离散的,除了问题本身的特性外,往往还依
赖于我们对精确性的要求,以及我们处理信息的能力.一般来说,讲系统看作是离散的结构会
导致需要处理大量的信息.在计算机诞生之前,人们能处理的信息量是很有限的,随着计算机
的迅速发展,人们能处理的信息量越来越大.离散数学,虽然有很多古老的问题,但作为一门
较完整的学科,则正是随着计算机的发展而迅速成长,壮大的.
连续和离散,既是矛盾的,又是统一的,用离散数学作模型的问题,常常用到连续的方法去处
理.而连续数学中的问题,则又往往化成离散的问题来求解.特别是在使用计算机时,则不论
什么问题,都是先离散化之后再处理.计算机无论多么先进,都只能处理有限的离散数据.
虽然离散数学是研究离散结构的一门科学,但基于各种原因,并不是所有研究离散结构的数
学都归功于离散数学.比如自然数是典型的离散结构.但对于自然数性质的研究属于数论的
范畴.另外,代数学,几率,统计等都讨论很多离散性质的委托.然而究竟什么是属于离散数学
之下,人们也没有完全一致的看法.而且精确的划分也不必要.数学本来就是一家,各分支之
间相互重叠和渗透是自然而且必然的事情.不过,每个数学分支还是有它的核心部分.而作为
离散数学的核心部分,学者认为有组合学(计数,排列,组合结构的分析及区组设计)和图论.
计数问题是非常基本的问题.在很多地方都会冒出来.经过长时间的发展,计数也有了很多有
效的方法.除了高中所学的组合排列公式,计数中常用的方法有生成函数(generatingFuncti
on),递归,差分方程,超几何函数(hypergeometicFunctions),群论导出的Polya公式,排容原
理(InclusionExclusionPrinciple)等等.
计数只是组合学的一个专题.组合学作为离散数学的一部分,自身亦是一个非常广泛的学科.
其他专题包括对组合结构的探讨,组合区组设计等等,都是非常丰富,活泼但应用广泛的专题.
图论(GraphTheory)是离散数学的另一个主要部分.图是一种很简单的结构.一个图G是由一
个集合V(称之为顶点集)和该集合上的一些元素对E(称之为边集)组成.记做G=(V,E).图有一
个很好的特点,即我们可以把一个图画下来.用平面上的点来表示顶点集中V的元素,用两点
间连一条线来表示E中的一对元素.这大概是为什么称之为图论,以及为什么V的元素称之为
顶点,E的元素称之为边的缘故吧.
图可以用来作很多实际问题的模型.比如若用V表示某地区所有城市的集合,用E表示哪两个
城市之间有道路连通,则图G=(V,E)就是该地区交通网路的一个模型.还有很多意想不到的东
西可以用图来作模型.
图作为一种数学结构,可以说是最简单的结构.它只是一个集合上的一个二元关系而已.而且
大多数情况下,这个集合还是有限的.这样简单的结构,能研究出什么明堂么?还真是大有明
堂.图论中有很多漂亮的,深刻的订立.而且正是由于结构的简单,使得这些定理有着广泛的
普遍性.
当然,这个定理不会是用来配夫妻的,尽管有时候被称为MarriageTheorem.很多实际问题中
会用到这个定理或者由它演生出来一些定理.譬如计算处理器的分配,员工工作安排等等,都
是这类在图论中被成为匹配(matching)的问题.
匹配问题是图论中一个重要课题.其他重要课题还有图的着色,图的分解,连通性等等.图论
中除了结构性问题外,还有一类很重要的问题,就是算法性问题,计算理论中有关问题的复杂
性研究,绝大多数都是图论问题.图论是计算机不可或缺的一部分.
将组合学和图论作为离散数学的核心,很大程度上是学者个人的偏好.很多其他问题都是离
散数学的重要组成部分,譬如自动机理论,开关理论和布尔代数,对局论和离散几率等等.
离散数学和其他的数学分支比较起来,它较少由复杂的数学语言的包装.很多问题很容易理
解.而解决的方法也许很简单,也许很难.很多人由于这些特点而喜欢它,也有人因此而看不
起它.欣赏它也好,鄙视它也罢,我们都离不开它.十八,十九世纪的工业革命依赖于,也促进
了微积分的发展.二十,二十一实际的信息革命则依赖于,也正促进着离散数学的发展.随着
计算机科学的发展,离散数学将扮演越来越重要的角色.
这篇漫谈已经很"散漫"了.虽然言犹未尽,也一定要打住了.这里所介绍的只是离散数学的冰
山一角.其实,学者对离散数学的所知所晓,又何尝不是冰山一角呢?
Ai
google的group排版能力真是太弱了.居然不会自动换行! ><
并且响应速度比较慢,发表了文章或者删除之后不能立即看到结果.原来一直以为google的实力应该比微软的强,没想到也存在这么多弱点,
离散数学和微分几何是计算机的基础理论课程.所以有必要收集相关的评论.