第二章 富有成效的方法

穿越欧拉之桥

在俄罗斯的加里宁格勒市，一座名为奈佛夫的岛屿坐落于普雷格尔河内。该市300年前曾隶属于普鲁士王国，彼时唤作哥尼斯堡，而奈佛夫岛与该市其余部分则由七座桥相互连接（图2上）。当时的城里流行着一个谜题：是否可能在不重复走过一座桥的情况下，遍历所有七座桥？之前没有任何人成功做到这一点。另一方面，对这种走法的可行性，当时也不存在任何形式证明。而其解决方案来自古往今来最著名的数学家之一。1736年，莱昂哈德·欧拉以一种不寻常的方式画出了哥尼斯堡市的地图。他将陆地和岛屿的部分表示为点，而桥则为连接各点的线（图2下）。

图2 版画中的哥尼斯堡（上），即现在的加里宁格勒，它表现了哥尼斯堡七桥之谜，莱昂哈德·欧拉将其表示为一幅简图（下）

当我们以这种方式看待该问题，事情就变得更加容易了。通过展示城市的网络结构，欧拉证明了谜题中的走法不可能。他的解释基于以下观察：若此种走法可行，则路程沿线所有点的连接数必为偶数。这是因为每当某人通过一座桥进入该市的任何部分时，他必须通过另外一座不同的桥离开。总之，每个区域必须有偶数座桥，比如2座、4座、6座等等。只有起点和终点可以有奇数个连接数：起点只能有一座桥，终点亦复如此。不幸的是，哥尼斯堡地图所有顶点的连接数均为奇数。因此，人们不可能一次性遍历所有桥而不重复。

哥尼斯堡地图这种简单的数学图是图的首个例子。数学家将构成这幅图的点和线分别称为顶点和边。如今，欧拉已经因为开启了一整个建立在图解分析基础之上的数学分支而被人们铭记。他的这种直觉可被认为是网络科学的首个创立契机。在他之后，许多数学家都曾研究过网络的形式特征，科学家则将它们应用于更加广泛的问题之中：1845年G.R．基尔霍夫的电路，1857年A．凯利的有机成分异构体，1858年由W.R．哈密顿提出的“哈密顿圈”，等等。其中一个著名的应用是于19世纪中期提出的“地图着色问题”。当时，地理学家正在设法计算出绘制地图所需的最小颜色数量，其中相邻的国家应有不同的颜色。这不仅仅是个理论问题：考虑到为数众多的国家和印刷行业中数量有限的不同油墨，使用最少数量的颜色显得至关重要。从经验角度看，三种颜色不够用，四种颜色则似乎很奏效。人们直到1976年才证实了解决方案确为四种颜色。证明基于将一张地图以图的方式呈现出来，其中的节点为国家，边则画在两个共享一个边界的国家之间。