一笔画问题是我的最爱，小学时候我可喜欢一笔画问题了，而且经常拿一笔画问题去考周围小伙伴，每次都会给他们问迷糊了，看着他们答不上来，我的心里美滋滋的。

————Shy

昨天我写了篇图论入门的文章，给两个智商普通的小伙伴看，她俩竟然看懂了，而且觉得很好玩！所以，我决定开始写图论系列的文章。

• 一座城池

柯尼斯堡，网上也有叫哥尼斯堡的，作为一个中国人，每次国外的名字经常被翻译成好几个版本，令我很纠结。所以这里我不打算用中文叫它了，这座城市德语是——Königsberg。

1255年条顿骑士团北方十字军建立了 Königsberg 这座城市，之后的数百年期间先后被条顿骑士团国（1255年）、普鲁士公国（1525年）和东普鲁士（1641年）定为首都或首府。Königsberg 曾是德国文化中心之一（1932年），伊曼努尔·康德、E·T·A·霍夫曼和达维德·希耳伯特都曾在此居住过。

第一次世界大战德意志国防军将其作为第一军区司令部所在地，最初有成千上万的犹太人在这个城市居住过，世界大战期间，犹太人遭受迫害，人数越来越少最后少于五百人，到了1942年，犹太人开始被遣送至灭绝营。1944年，第二次世界大战，盟军轰炸Königsberg，城市遭受重创，大火燃烧了几天几夜。4月9日，在红军的强烈攻势下，Königsberg 德军司令奥托·拉施率残余部队投降。此时，城市中的军民死亡已达42,000人，大约有12万人幸存，其中大部分是妇女、儿童和老人，而被俘的则超过90,000人。留下来的德国人中，大部分在1949年前死于疾病、刑讯和饥饿。1949年－1950年，最后幸存的2万德国人被陆续驱赶出Königsberg。1945年，根据《波茨坦协定》，Königsberg划归苏联，现在是俄罗斯加里宁格勒州首府。

Königsberg这座城市演绎了和平与战争的交替，它也孕育了伟大的文明，这座城池便是图论的起源地。

• Königsberg七桥问题

Königsberg七桥问题是世界著名古典数学问题之一。

18世纪，在Königsberg的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来，有人提出了一个问题，是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，并且最后回到起点。

当地的居民每周六都会举行活动，看谁能一次走过七座桥。有趣的是没有居民能完成这个目标，要不就是少走一座桥，要不就是某座桥需要经过两次，或者无法回到出发点。到底存不存在一条这样完美的线路——每座桥只能经过一次而且起点与终点必须是同一地点，大家谁也不知道，也无法证明不存在。

• 传说哥

1736年，牛逼哄哄的大数学家欧拉造访了Konigsberg这座城市, 他发现了当地居民这个有趣的消遣活动。

如何找出这样一个行走路线，欧拉指出陆地是不重要的，重要的是跨过桥的线路。因为陆地没有任何限制，人们可以不停地走动，只要不经过桥，那么就相当于什么也没做。因为在陆地上任意一点出发，只要不经过桥，不论怎么走都可以回到这个出发点，我们完全可以将陆地看成一个点。所以欧拉把这个问题简化了，他把公园不相连的四块地画成A、B、C、D四个点，而把七座桥画成七条线，每一座桥就是从一个点（陆地）到另一个点（陆地），如图所示。

图的简化过程很清晰，可以看出A陆地和B陆地有两座桥相连所以A点和B点连接两条线，同理B点和D点连接两条线，AC、BC、DC各连一条线，总共七座桥对应七条线。

那么这道问题就变成了，从A、B、C、D任意一点出发，是否可以一笔画出该图形，且每一条线只许画一次，不许重复画，俗称一笔画问题。

神奇不！！！这就是图论的起源，欧拉将复杂的、有公园视觉效果的问题归结成点和线！

• 自由的变换

我说过，做相同图论的问题，有时候图可能画的不一样，这是为什么呢？因为图论的精髓在于画这个动作，而画成什么样不重要，一条线，你画的急了拐弯也好，沟沟八翘也行，直线也罢，都不影响图论的本质。就像下面这两个图，虽然长得不太一样，但其实都是Königsberg七桥问题。

图论解题过程中，你的图画美观可能别人会夸你，你画的埋了乎汰的，别人可能不愿瞅你答案。但是我觉得，画自己的图，让别人喷去吧！我将下面这句名言送给那些画画不好看的人，也包括我自己：

• 简单到底

回归正题，欧拉证明的思路非常简单。他观察到，除了起始点以外，每经过一个顶点，都是一条线的结束，另一条线的开始。

就是说，每经过一点时，就需要两条线，一条线结束，一条线开始。所以，如果一个点不是起始点，那么这个点的连线必须是偶数，才能保证进入、经过并离开此点。若一个点有奇数条线相连，那么之个点要么是起点，要么是终点。

定义：
奇点 ———— 一个点有奇数条连线。
偶点 ———— 一个点有偶数条连线。
欧拉创造了伟大的欧拉定理：
1. 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
2. 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点为终点。
3. 其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)

这里简单解释下什么是连通图，就是图里所有点都是可以经过线路互相到达的。比如，这个就是不连通的图，不连通的图画吐血了也不可能一笔画完：

• 轻松证明

如图所示，四个点的连线数分别是3、5、3、3，4个都是奇点，所以不能一笔画成，因此Königsberg七桥问题不存在解。

怎么样，好玩不，是不是很神奇，还不去找智商低的人炫耀去！