科学界普遍认为,理论科学、实验科学和计算机科学是促进科学技术进步和人类文明发展的三大科学,它们相辅相成地帮助人们发现未知,认识自然和改造世界。这三大科学也被认为是科学发现与技术创新的三大支柱。

哥尼斯堡七桥问题--对问题进行抽象的一个典型实例

    17世纪的东普鲁士有一座哥尼斯堡城,城中一岛与两条支流将城市分为北区、东区、南区和岛区四处,全城有七座桥将四个城市相连,由此产生一个有趣的数学难题:寻找走遍这七座桥,且每座桥只许走过一次,最后又回到原出发点的路径。该问题即著名的哥尼斯堡七桥问题。

『计算机科学导论--思想与方法』学科的基本问题(1)-LMLPHP『计算机科学导论--思想与方法』学科的基本问题(1)-LMLPHP

    1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文,指出其不可能。

    为解决这一问题,欧拉基于该问题本质考虑,忽略非本质的东西(如桥长、桥宽等),将七座桥与四个城区简化如图,从而将哥尼斯堡七桥问题抽象为一个数学问题,即经过图中每条边一次且仅一次的回路问题。欧拉在论文中证明这样的回路不存在,并用数学方法给出了3条判定规则:

  1. 如果连接奇数座桥的地方不止两个,满足要求的路线是找不到的;
  2. 如果只有两个地方连接奇数座桥,可以从任一地点出发,找到所要求的路线;
  3. 如果没有一个地方连接奇数座桥,则无论哪里出发均可实现。

    欧拉的论文为图论的形成奠定了基础,此处也包含了任一连通无向图是否存在欧拉路径和欧拉回路的判定条件,由上述规则3看出,任一连通无向图存在欧拉回路的充分必要条件是图的所有结点均有偶数度。之后会细讲。

    图论略扩:哈密尔顿回路问题

    由爱尔兰著名学者威廉·哈密尔顿爵士于1859年提出,大意为:在任一给定的图中,能不能找到从一点出发,不重复地走过所有结点(不必通过图中每一条边),最后回到原出发点的路径。而此问题目前仍未找到充分必要条件。

12-08 10:39