欧拉路径与欧拉回路详解
有些图形能一笔画成,不抬笔,也不重复任何一条线;有些图形无论你试多久都画不成。其实不必试:数一数每个角上的线。如果至多有两个角的线数是奇数,这个图形就画得出来,而笔画必须在这两个角起止。莱昂哈德·欧拉在 1736 年发现了这条规则,并以此开创了图论。
柯尼斯堡七桥
普鲁士城市柯尼斯堡,今天的加里宁格勒,坐落在普雷格尔河两岸以及河中的两座岛上,即克奈普霍夫岛与洛姆瑟岛。七座桥连起四块地方:克奈普霍夫岛到两岸各两座,两岛之间一座,洛姆瑟岛到两岸各一座。市民们想知道,能否走一趟把每座桥恰好走一次。欧拉在 1735 年提交给圣彼得堡科学院、1741 年付印的论文里作了回答:不能。他的关键一步是把城区和桥以外的一切都丢开,而这正是图所做的事:每块陆地一个顶点,每座桥一条边;两座桥连着同样两处时,就是两条边。
奇偶度规则
顶点的度,是连到它的边数。笔画经过一个顶点时从一条边进来、从另一条边出去,所以它把这个顶点的边成对地用掉。只有笔画的第一个顶点和最后一个顶点,才可能留下一条没有配对的边。因此,度为奇数的顶点必须是笔画的起点或终点。克奈普霍夫岛有五座桥,另外三块地方各有三座:四个奇数顶点,多了两个。一般而言,连通图在每个度都是偶数时有欧拉回路,即一笔画回到起点;在恰好两个度是奇数时有欧拉路径,从一个走到另一个。奇数顶点的个数绝不会是一,也不会是任何别的奇数:每条边给所有度之和添上 2,所以这个和是偶数。欧拉也注意到了这一点,今天叫作握手引理。
为什么这条规则就够了
欧拉证明了奇数顶点多于两个的图形画不出来,并且没有给出证明地断言:其他任何连通图形都画得出来。证明来自德国数学家卡尔·希尔霍尔策,他 1871 年英年早逝,论文于 1873 年发表。有奇数顶点就从奇数顶点出发,没有就随便从哪里出发,沿着未走过的边一直走。由于其他顶点的度都是偶数,只可能卡在终点。如果还剩边,其中一些会碰到已走过的路线,因为图形是连通的。从这样的顶点再走一次,直到走不动为止——这一次只会回到该顶点——再把这个圈在那里接进路线。如此重复,直到一条边也不剩。这个证明同时就是最快的算法:每条边只被看固定的次数。
Fleury 算法:别烧掉自己的桥
即使图形画得出来,一笔下去也可能失败。拿两个由一条边连起来的三角形,从第一个三角形的某个角起笔:若在第一个还没画完时就过到第二个,就再也回不来了。那条连接边是一座桥:去掉它,图形就裂成两块。Fleury 在 1883 年的算法给出一条规则:在每个顶点挑一条不是剩余边之桥的边,除非别无选择。照着做,总能画完。判断是不是桥要花时间,所以 Fleury 算法比 Hierholzer 算法慢,但它是你拿着铅笔就能照着走的那一个,本应用的提示用的就是它。
修好一个图形
有 k 个奇数顶点的图形需要 k/2 笔。要一笔画成,就添加把奇数顶点两两配对的边:每条新边让两个奇数顶点变成偶数。添加 k/2 − 1 条后剩下两个奇数顶点,得到一条路径;添加 k/2 条后一个不剩,得到一条回路。柯尼斯堡若在四块地方的任意两块之间再修一座桥,那趟步行就成立了;再修两座,还能绕回起点。历史也做了类似的事:两座桥毁于第二次世界大战,两座被现代公路取代,而今天立在旧址上的五座桥,可以每座各走一次,从一座岛走到另一座岛。
数一数画法
圣尼古拉斯的房子,是一个带两条对角线和一个屋顶的正方形,这是这道谜题的德国儿童版:“Das ist das Haus vom Ni-ko-laus”有八个音节,每条线一个。它下面的两个角是仅有的奇数顶点,从每个角各有整整 44 种画法,一共 88 种。对有向图而言,欧拉回路的条数有公式可循,即以德布鲁因、范阿尔德内-埃伦费斯特、史密斯和图特命名的 BEST 定理。对普通图则没有已知的这类公式,一般认为计数是困难的,所以本应用对小图形逐一试遍各种画法,并跳过那些会把图形分成两块的步骤。
欧拉路径用在哪里
扫雪车、清扫车或邮递员都想把每条街走一次再回来。如果每个路口的街道数都是偶数,一条欧拉回路就够了;否则有些街道得走两遍,而选出代价最小的那些,就是 1962 年管梅谷提出的中国邮递员问题。笔式绘图仪或激光切割机也靠尽量不抬笔多画线来省时间。在基因组测序中,数百万条短 DNA 片段通过在德布鲁因图里寻找欧拉路径来拼接,图里每个片段就是一条边。同一条规则还能告诉你,谜题册上的哪些线条图值得一试。
动手试试
打开欧拉路径探索器,亲手描十二个图形,从 1736 年的和今天的柯尼斯堡,到星形、层层相套的正方形和立方体,也可以画你自己的、带平行边的图形。奇数顶点是实心的,每个顶点都标出它的度,图形下面的奇偶度规则会说明什么是可能的、补哪些边能修好这个图形。卡住时,应用会告诉你是起笔的顶点选错了,还是过桥过早,以及那是第几步。提示给出一条安全的边;求解则用 Fleury 算法把图形画出来并显示桥的判定,或者用 Hierholzer 算法显示每一次子回路的接入。
常见问题
欧拉路径和哈密顿路径是一回事吗?
不是。欧拉路径把每条边走一次,可以多次经过同一个顶点;哈密顿路径把每个顶点走一次,不必用上每条边。一个图有没有欧拉路径,数一数奇数顶点立刻就知道;但哈密顿路径没有已知的快速判定法,找出一条是计算机科学中经典的困难问题之一。
两个顶点之间连着不止一条边时,奇偶度规则还成立吗?
成立。每条边都算进它两端的度,无论是否还有别的边连着同样两个顶点。柯尼斯堡就是这样的多重图,克奈普霍夫岛到每一岸各有两座桥。顶点连到自身的边,也就是自环,给它的度添上 2,从不改变它的奇偶。
单行道怎么办?
在有向图里每条边都有方向,规则比较的是进入每个顶点的边与离开它的边。当每个顶点的入边与出边一样多、而且这些边连成一片时,就有欧拉回路;当一个顶点的出边比入边多一条、另一个顶点的入边比出边多一条、其余顶点都持平时,就有欧拉路径,而且路径从前者走到后者。
会不会有恰好一个奇数顶点的图形?
不会。所有顶点的度加起来等于边数的两倍,因为每条边有两个端点。这个和是偶数,所以其中奇数度的个数也必须是偶数:0、2、4 等等,绝不会是 1 或 3。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开欧拉路径探索器