柯尼斯堡问题

第 1 章 柯尼斯堡：一座桥城如何生出一个学科

每个学科都有一个属于自己的创世故事。物理学的在苹果树下，生物学的在加拉帕戈斯的甲板上，图论的在一条河上。普雷格尔河从东边流进柯尼斯堡，在城中心拆成两支，绕出一座岛，又汇拢西去。河水切割出的四块陆地，被七座桥连成一个整体。十八世纪的柯尼斯堡市民在礼拜日下午散步时给自己发明了一个游戏：能不能从家里出发，把七座桥每座都走一遍，而且只走一遍，最后回到家里？没有人成功过，但也没有人能说清楚这到底是不可能，还是只是还没找到正确的走法。这个问题看起来跟数学毫无关系，它不涉及计算，不涉及测量，甚至不涉及任何数字。恰恰因为它看起来不像数学问题，它才在数学史上变得那么重要。1736年，圣彼得堡的欧拉发表了一篇论文，用一种前所未有的方式处理了这个问题，图论从此有了自己的第一份文献。这本书要讲的一切，四色定理、拉姆齐数、互联网的无标度结构、大脑连接组，全都是那篇论文播下的种子长出的树。

我想在开篇就把一个态度摆出来：七桥问题本身很小，小到答案只有一句话，但欧拉处理它的方式很大，大到定义了一种新的数学对象。本章的主要任务不是欣赏那句话，而是拆解那个方式。我们会看到欧拉如何无视一切表面信息，把活生生的城市压缩成一张只剩骨架的图，看到他如何在没有画出任何图的情况下完成了图论的第一次推理，也会看到这个方法在之后一百年里几乎无人问津，直到电网络、化学分子和社会网络相继找上门来。一个学科的诞生往往不是欢呼，而是漫长的沉默。这句话也是全书的一个预兆：图论每一次重大进展，几乎都迟到得离谱，又突然得惊人。

一座河城的散步难题

先把地理说清楚。柯尼斯堡今天是俄罗斯的加里宁格勒，在欧拉的时代是普鲁士王国的东普鲁士首府，波罗的海边最重要的商业城市之一。城市人口四五万，有港口，有成立于1544年的阿尔贝蒂娜大学，有让全城人按钟声校对时间的皇家城堡。这座城市后来最著名的居民是康德，他1724年出生在这里，一生没有离开，他的每日散步准时到邻居拿他对表。顺便说一句，康德散步走的那条路后来被叫做哲学家大道，距离七桥区域不远。你可以想象十八世纪的柯尼斯堡：商船沿河而上，码头工人卸下粮食和木材，大学生在酒馆里争论莱布尼茨和牛顿，而普雷格尔河上的七座桥是所有人日常通勤和消遣的必经之路。桥不只是市政设施，也是约会地标、小贩聚集处和城市传说的发生地，每座桥都有名字，有来历，有属于自己的故事。

普雷格尔河自东向西穿城而过，在市中心分成新普雷格尔河和老普雷格尔河两支，两支河道中间夹着克奈普霍夫岛，岛上矗立着大教堂，康德后来就安葬在教堂的东北角。河的两支把城市切成四块陆地：北岸是克奈普霍夫一侧的老城区，商业最密集；南岸是洛姆肖；东边是利普尼茨；再加上河中央的岛本身。七座桥横跨其上。绿色桥和铁匠桥连接北岸与岛，商人桥和高桥连接岛与南岸，木桥连接北岸与东岸，蜜桥连接岛与东岸，最后是肠道桥，连接南岸与东岸。蜜桥的名字来自桥边曾经堆放的蜂蜜仓库，肠道桥的名字则来自它紧邻的肉铺下水道，十八世纪的桥名和今天的地产品牌一样诚实。这些名字在欧拉的论文里一个都没出现，他只用大写字母A、B、C、D代表四块陆地，用小写字母a到g代表七座桥。走在桥上的市民记住的是名字，但欧拉记住的是连接。

这个散步谜题在当时的柯尼斯堡流传到什么程度，没有严格的记载。流传最广的说法是市民们真的在礼拜日下午认真尝试过各种路线，茶余饭后争论各自的走法，甚至有人言之凿凿地说大学教授也参与过讨论。这些细节多半是后人添油加醋，但有一点可以确定：到十八世纪三十年代初，这个问题已经以书信的形式在普鲁士和俄国的学者圈子里流通。它属于当时很流行的一类东西，位置几何问题，与几何有关，却不需要测量和计算，只跟位置和顺序有关。莱布尼茨1679年给惠更斯的信里就抱怨过，说我们缺少一种关于位置的学说，一种只关心图形的相对位置而不管大小和数量的数学，他给它起名叫位置几何学。莱布尼茨预感到了一片新大陆，但没能登陆。七桥问题就是留给后来登陆者的第一块礁石，而礁石的意义从来不是它本身，而是它标出了大陆的位置。

从但泽到圣彼得堡：一封信的旅程

问题是怎么到达欧拉手里的？现在能查到的线索是但泽市长卡尔·戈特利布·埃勒与欧拉的通信。埃勒是普鲁士的官员和数学爱好者，担任但泽数学会的会长，与欧拉有多年书信往来。现存的信件显示，1736年3月他在信里向欧拉提到柯尼斯堡的桥的问题，并且措辞相当客气，说这类关于位置的问题太过渺小，不值得欧拉这样的大人物花费时间，但如果欧拉肯给一个解答，他会转告柯尼斯堡的数学朋友。欧拉的回信原件已经不易查考，但可以确定的是，这个问题当时已经在但泽和柯尼斯堡的学者之间转了好几手，埃勒本人也坦承他转述的版本得自柯尼斯堡的朋友。有意思的是欧拉的反应。一个市长的消遣题，在他那里没有停留三秒钟就被升级了：柯尼斯堡有四块陆地七座桥，可要是有一百块陆地三百座桥呢？有没有一个判据，让人不用试遍所有走法就能下结论？你可以试着体会这个转念的瞬间。普通人问的是这条路怎么走，工程师问的是哪条路最短，数学家问的是这类问题什么时候有解。三个问题里，最后一个最不像问题，却最有用，因为一旦拿到判据，前两个问题立刻降格为查表。数学家对单个谜题的兴趣总是有限的，对一类问题的判据的兴趣才是无限的。欧拉后来在论文开头亲口承认，这个问题本身很平凡，但他紧接着说，解决它所需要的方法值得关注，因为这样的方法可以为位置几何学奠基。这句话是整篇论文的自白书。

这里值得停一下，说说十八世纪数学的传播方式。当时没有今天意义上的快报期刊，学者之间的信件就是学术网络本身，一个问题的流转速度取决于邮路和友谊。欧拉所在的圣彼得堡科学院由彼得大帝创立于1724年，聚集了欧拉、哥德巴赫、丹尼尔·伯努利等一批人，科学院的《彼得堡科学院评论》是当时欧洲一流的出版物，但一卷要攒好几年才印得出来。欧拉这篇论文1735年8月26日先在科学院会议上宣读，正式发表在标注1736年卷次的《评论》第8卷上，页码从128到140，而那一卷实际印行已经是1741年的事了。所以你说它是1736年的论文还是1741年的论文，取决于你认会议记录还是认出版日期。本书一律称1736年，因为论文在1736年已经完成并在学界流通，这也是所有教科书采用的年份。论文标题是拉丁文《解决一个与位置几何有关的问题》，这个标题本身就是宣言：欧拉自觉地把自己放在了莱布尼茨预言过的那片空白大陆上，而且他清楚自己是在做开疆拓土的事。

欧拉其人：一台停在圣彼得堡的思考机器

说七桥问题之前，得先认识解它的人，因为欧拉本人的生活方式本身就是理解这篇论文的背景。莱昂哈德·欧拉1707年出生在瑞士巴塞尔，父亲是加尔文宗牧师，本来也把他往神学方向培养。少年欧拉的数学天分被约翰·伯努利发现，老伯努利当时年事已高，不再收学生，却破例每周六下午单独给这个年轻人答疑，并且叮嘱他别去看那些轻松的教科书，直接去啃难的专著，卡住了再来问。这在今天是难以想象的师资配置。1727年，二十岁的欧拉经丹尼尔·伯努利引荐来到俄国圣彼得堡科学院，先是在医学部挂职，很快转入数学部。此后除了1741到1766年应普鲁士国王腓特烈二世之邀主持柏林科学院的二十五年，他的一生都在圣彼得堡度过。1738年前后他右眼失明，一种说法是当年为政府绘制地图时过度用眼，在烈日下的劳累加速了病变；1766年回圣彼得堡之后，左眼白内障恶化，到1771年前后他几乎完全失明，晚年只剩一点模糊的光感，四年后连这点光感也被白内障夺走。

失明没有减慢他，反而像清空了房间里的干扰。他心算能力惊人，能记住整卷《埃涅阿斯纪》，能把桌上一摞论文哪篇压在哪篇下面都记得清清楚楚。两个儿子和一群助手替他记录口述，他在脑子里做求和、做消元、审论文，失明后的十几年反而产出了他全部著作的近一半。现代版的欧拉全集规划超过八十卷，编号的著作和信件八百多种，从月球运动理论到军舰操纵，从保险精算到音乐理论，无一处不碰。他结过两次婚，生了十三个孩子，只活下来五个，他晚年说自己的许多发现是抱着婴儿、听着孩子们在脚边吵闹时做出的。1783年9月18日下午，他一边喝茶一边逗孙子玩，烟斗还攥在手里，突然中风，几小时后去世，孔多塞写下的讣词成为科学史上最著名的句子之一：他停止了计算，也停止了生活。拉普拉斯则说过一句被一代代老师转述的话：读读欧拉，读读欧拉，他是我们所有人的老师。

我说这些不是为了堆砌景仰。我想说的是，七桥问题的解答出自这样一个人：他一生的产量和广度前无古人，但他从不觉得处理一个消遣性的小问题有失身份。在欧拉的时代，数学的等级观念其实很重，天体力学是皇冠，宫廷资助的工程问题是正务。欧拉两者都做，也都做到了极致，但他同时肯低下头去看市民的散步路线，并且从中识别出一个新的数学物种。这种平等看待一切问题的态度，本身就是七桥故事能发生的条件。一个只把数学等同于高贵问题的时代，不会有人为位置几何学奠基。顺便一提，欧拉在柏林的岁月并不愉快，腓特烈二世嫌他不够风雅，宫廷里的伏尔泰拿这位老实人的朴素文风开涮，国王后来干脆把科学院院长的位置留给了自己的弟弟。欧拉1766年带着全家回到圣彼得堡，叶卡捷琳娜二世以皇室规格接待他，拨给他宅邸和厨师。一个人在柏林被当作工匠，在俄国被当作国宝，他晚年的高产有一半要归功于这种被善待。科学的产出从来不只是智力的函数，也是环境的函数，欧拉的一生是这条规律最好的正反例。

1736年的论文：欧拉到底做了什么

现在进入正题。欧拉论文的完整论证在今天的严格性标准下显得啰嗦，个别地方甚至有缺口，但它的骨架干净得像刀切。第一步，他把四块陆地抽象成四个对象，把七座桥抽象成这四个对象之间的七种连接，然后宣布：如果只问每座桥走一遍，那么陆地的形状、大小、桥的长短宽窄、是石桥还是木桥、河水是急是缓，全部无关紧要。整座柯尼斯堡可以被压成一张只有四个点和七条线的骨架。今天我们把那四个点叫顶点，把那七条线叫边，把整张骨架叫图。欧拉没有画出这张图，他的论文里是四个字母、七个字母和一张记录连接关系的表，人字形的点线示意图是十九世纪的作者们后加的。很多人说欧拉画出了第一张图，这是以讹传讹，但说他想到了第一张图，并不为过。抽象在头脑里完成，画不画在纸上只是演示问题。这个细节值得较真，因为它提醒我们图论真正的对象从一开始就是连接关系本身，而不是任何一种画法。

第二步，他发现了一个约束。假设一次散步把每座桥恰好走一遍，那么除了起点和终点，散步者每次从一块陆地走进去，都必须从另一座桥走出来。也就是说，对任何一个不是起点也不是终点的陆地区域，进去的次数等于出来的次数，而每次进出都要占用一座不同的桥，所以连接这块陆地的桥数必须是偶数。用现代语言说，中间顶点的度数必须是偶数。柯尼斯堡的四块陆地，北岸五座桥，岛三座，南岸三座，东岸三座，四块全是奇数度。四个奇数度顶点，连一个可以豁免的中间点都凑不出来，遑论两个端点。所以路线不存在，谜题在两行推理内死亡。欧拉还不满足，他把问题推广到任意多陆地任意多桥的情形，给出了完整的一套判据：如果有多于两块陆地连着奇数座桥，这样的路线不存在；如果恰好有两块，存在从一块出发到另一块结束的路线；如果所有陆地都连偶数座桥，存在出发点和终点重合的环游路线。他还讨论了要求每座桥走两遍的情形。一篇处理市民消遣的论文，最后给出的是一整类问题的一般理论，这就是数学家的做派。

严格说来，欧拉论证了必要性，即满足条件的路线要求度数条件成立；而充分性那一半，即度数条件满足时路线必定存在，他的说明是跳跃的，只给了构造思路。这个缺口要等到一百三十七年后的1873年才由德国数学家希尔泽尔补全，他给出了今天教科书里标准的构造性证明，而讽刺的是希尔泽尔的论文也是去世后才由朋友整理发表的。数学史的接力常常这样，第一棒跑完，全场安静，第二棒在一百年后无人喝彩地补完。顺便说一句，欧拉论文里还埋着另一个后来极其重要的引理。他把每块陆地连接的桥数加起来，得到一个总和，而这个总和等于桥数的两倍，因为每座桥在计数时恰好被两岸各算了一次。用现代话说，图的所有顶点度数之和等于边数的两倍，由此立刻得出任何图中度数为奇数的顶点必有偶数个。这就是握手引理，名字来自晚会的类比：会场里与人握过奇数次手的人数必为偶数。它是图论里最常用的第一步观察，而它的第一次出场就在这门学科的第一篇论文里。

一笔画的判据：从证明到玩法

把欧拉的结论翻译成现代教科书语言，就是所谓欧拉路径定理。一个连通图存在经过每条边恰好一次的闭合回路，当且仅当它的每个顶点度数都是偶数；存在每条边恰好一次的开路径，当且仅当它恰好有两个奇数度顶点，且路径必须从其中一个出发、在另一个结束。这个定理如今出现在中学竞赛教材和算法课本的第一章，判据简单到可以讲给小学生听，但它的证明思路值得每个人亲手走一遍，因为它示范了数学里最有用的一种动作：把存在性问题转化为计数论证。你要证明路线不存在，不需要穷举所有失败的走法，只需要找到一个所有走法都逃不出的死结。奇偶性就是那个死结。反过来你要证明路线存在，希尔泽尔给出的构造是：在图里随便走，走到走不动为止，得到一个环；如果还有边没经过，连通性保证能从已有的环上某点接出新的环，把它剪开缝进去，像接驳船一样逐段拼接，直到所有的边都被吃掉。这种把环缝进环的操作，正是两百年后弗勒里算法乃至中国邮递员问题的算法灵魂。

用这个判据回看日常的一笔画谜题会很有快感。小学奥数里那个画信封的题，一个方框加两条对角线加顶上一个尖角，总共五个顶点，底边中点度数是四，左下角三度，右下角三度，尖角两度，上边中点两度，恰好两个奇数点，所以能一笔画成，但必须从一个奇数点出发到另一个结束。你要是从底边中点起笔，怎么画都会卡死。这类谜题在欧拉之前靠手感，在欧拉之后靠数数，数数比手感可靠，这就是理论的意义。判据还有一个常被忽略的延伸：把每条桥想象成只能单向通行的单行道，就得到有向图的版本，这时奇偶判据变成入度与出度的匹配，中间每个点的进入次数必须等于离开次数。城市单行线系统的设计、流水线工件的调度、计算机网络里的数据包路由，用的都是这一版。看似只是换个说法，实际是把欧拉的思想从对称关系推进到了带方向的关系，而这一步要到二十世纪才走得干净。七桥问题还有一个后日谈：欧拉本人在论文末尾顺带指出，要柯尼斯堡的散步成立，只需要再修桥改变奇偶分布。历史跟开了个玩笑，1875年，这座城市真的在河上架起了第八座铁路桥，有较真的数学史家核算过，新桥落成后从某块陆地出发的一笔路线出现了。可惜那时欧拉已经去世近百年，柯尼斯堡的市民大概也没几个人知道，他们脚下的通勤桥网刚被一位故人预言式地调过参。还要强调一点，判据只对连通图有效，如果你的城市被分成两片互不相通的桥网，问题当然无解，这一点欧拉在论文里同样交代了。

握手引理也值得多说两句，因为它示范了图论最基本的一种世界观：局部信息相加必然给出全局约束。每个顶点的度数是局部量，你站在任何一块陆地上都能数出来，但把这些局部量一加，就得到一条谁也逃不掉的全局账目。晚会的例子里，你可以随手数出每个人握了几次手，把所有人的次数加起来必然是偶数，因为它等于握手的总次数乘二，于是握过奇数次手的人数只能是偶数个，不多不少。柯尼斯堡四块陆地全奇数，恰好违反了这条账目在奇数点数量上的进一步推论吗？没有违反，四个是偶数个，账面是平的，所以握手引理本身并不排除这个图，排除它的是奇数点不能超过两个的判据。这两个层次的观察一个管账目平衡，一个管路径存在，读者应该体会它们分工的精确。图论的很多定理都是这样，先有全局恒等式，再有结构存在的充要条件，欧拉一篇论文把两层都占全了，这就是起点的意义。

解剖一篇论文：欧拉的表格与两步走

这篇论文短得可以一次读完，德文翻译版只有十几页，却值得像解剖标本一样逐段看过，因为它显示了在没有现成语言的情况下，数学家如何徒手搭出概念。论文大体分两半。前一半处理具体的柯尼斯堡：欧拉先耐心数出每块陆地各连几座桥，然后引入他的核心记法，把一次完整的散步写成字母序列。散步从某块陆地出发，每过一座桥就写下到达的那块陆地的字母，于是走m座桥的散步被记成一个长m加一的字母串，比如ABDCACBC这样的东西。接着他指出，如果在序列中字母A和B相邻出现，就意味着走过了某座连接A与B的桥。于是问题被改写成排列问题：什么样的字母串能恰好把每座桥对应的相邻字母对都用到一次？他把连接关系整理成一张表，行是陆地字母对，列是每对之间桥的数目，然后推导出他的一般规则：如果某块陆地连着奇数座桥，那么它的字母在序列中必须出现的次数，比桥数的一半多一点；如果连着偶数座桥，字母出现次数的规矩则取决于路径是否要求回到出发点。把四块陆地的字母出现次数的下限加起来，一旦超过序列的总长度，路线就被判死刑。柯尼斯堡的四个奇数算出来总和超过限制，解答宣告不存在。这套字母账本式的方法今天看笨拙，但它就是度数概念的第一次手工实现，欧拉在没有图的情况下，用序列和表格硬算出了图的性质。

论文的后一半是推广和系统化。欧拉宣布他的方法适用于任意块陆地、任意座桥的情形，并给出前面说过的三条判据，还顺手处理了一个变体问题：如果允许每座桥走恰好两次又如何。最后在论文的收尾处，他做了那个决定现代图论命运的声明，大意是：这类问题的解法与大小数量无关，只与位置关系有关，过去无人知晓该如何用数学处理它，本篇算是一个尝试。读者应该体会这句话的分量。欧拉不是解出了一道题，他是划定了一类题，并且给这类题配了专属的方法论。今天的论文写作讲究问题、方法、贡献的清晰分离，欧拉这篇1736年的文章在结构上完全够格发在今天的期刊上，只是审稿人大概会要求他把表格换成一张图，那个他自己想到却没画的图。数学史里这样的遗憾不多：概念已全部就位，只欠一次可视化。要等到十九世纪，人们才普遍用画出来的点线图讨论这类问题，而那时距离欧拉已经过去整整三代人。

一笔画的现代生活：从市政清扫到基因测序

一个自然的疑问是，这个判据在今天还有什么用，还是只是数学史的古董。答案远比想象的热闹。第一类应用是市政路线。城市的洒水车、扫街车、垃圾收集车、邮递员的投递路线，本质上都是在街道网络上的遍历问题，街道的每一段都必须走到，理想的方案是每段恰好走一次。真实的街道网几乎从不满足偶数条件，于是问题变成如何以最少的重复把奇数抹平，这就是第7章要讲的中国邮递员问题，它的地基正是欧拉的判据。上世纪七十年代纽约市的扫街计划就用这套思路把上百条街道的清扫班次排出了可行的路线，运筹学界把它当作图论落地的经典案例。第二类应用在计算机和通信里。循环移位寄存器的序列设计可以叙述成超立方体或德布鲁因图上的欧拉回路问题，德布鲁因1946年系统研究的这类序列，其构造的钥匙正是每点入度等于出度的有向图必有欧拉回路，这条定理是欧拉判据在有向图上的直系后代。从电信编码到密码学的流密码设计，这些序列一直在岗。

最出人意料的应用在生物学。测 DNA 序列的鸟枪法把长链打碎成海量短片段，再像拼图一样拼回去。上世纪九十年代末，帕夫兹纳等人指出，传统拼图模型其实难处理重复片段，更好的做法是把片段重叠关系组织成德布鲁因图，把基因组重构问题转化成在这个图上找欧拉回路。欧拉判据保证回路存在，算法只需沿路拼接。这一思路成了第二代测序技术的组装算法的重要源头之一，你手机里的消费级基因检测报告，间接用到了欧拉在1736年想清楚的那条奇偶原理。数学史上