难题 科学研究类-《什么学科这么有趣》（bookish师父的题目目前无人解答，50奖第

图论

图论
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若
干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的
某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系
。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地
建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问
题有很强的实际背景。

图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中
的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。



问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然
而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽象分析法将这
个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接
相应的两个点的一条线来代替，从而相当於得到一个「图」（如下图）。欧拉证明
了这个问题没有解，并且推广了这个问题，给出了对於一个给定的图可以某种方式
走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。



1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的
20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好
一次的闭回路，即「绕行世界」。用图论的语言来说，游戏的目的是在十二面体的
图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由於运筹学、计算机科学
和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。


在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面
或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的
颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的
边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出
一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所
以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论
等分支的发展起到推动作用。

图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论
、极图理论，以及代数图论、拓扑图论等都有很大的发展

神经网络理论
神经网络理论：认知心理学家通过计算机模拟提出的一种知识表征理论，认为知识在人脑中以神经网络形式储存，神经网络由可在不同水平上被激活的结点组成，结点与结点之间有联结，学习是联结的创造及其强度的改变。

神经网络是一门活跃的边缘性交叉学科.研究它的发展过程和前沿问题，具有重要的理论意 义.
　　神经网络理论是巨量信息并行处理和大规模平行计算的基础，神经网络既是高度非线性动力 学系统，又是自适应组织系统，可用来描述认知、决策及控制的智能行为．它的中心问题是 智能的认知和模拟．从解剖学和生理学来看，人脑是一个复杂的并行系统，它不同于传统 的Neumann式计算机，更重要的是它具有“认知”“意识”和“感情”等高级脑功能 ．我们以人工方法摸拟这些功能，毫无疑问，有助于加深对思维及智能的认识．80年代初， 神经网络的崛起，已对认知和智力的本质的基础研究乃至计算机产业都产生了空前的刺激 和极大的推动作用．
　　近十年来，神经网络理论与实践有了引人注目的进展，它再一次拓展了计算概念的内涵，使 神经计算、进化计算成为新的学科，神经网络的软件模拟得到了广泛的应用．近几年来科技 发达国家的主要公司对神经网络芯片、生物芯片独有情钟．例如Intel公司、IBM公司、AT &T公司和HNC公司等已取得了多项专利，已有产品进入市场，被国防、企业和科研部门选 用，公众手中也拥有神经网络实用化的工具，其商业化令人鼓舞．尽管神经计算机、光学神 经计算机和生物计算机等研制工作的艰巨性和长期性，但有一点可以使人欣慰：它现在还只 是初露锋芒，有巨大的潜力与机会，前景是美好的．
　　事实上，探究大脑—思维—计算之间的关系还刚刚开始，道路还十分漫长，关于脑的计算原 理及其复杂性；关于学习、联想和记忆过程的机理及其模拟等方面的研究已受到人们的关注 ，它未来的发展必将是激动人心的．神经网络理论的前沿问题将渗透在21世纪科学的挑战性 问题中，可能取得重大的突破．