- 0 个奇数顶点:一条回路,从任一顶点出发回到该点
- 2 个奇数顶点:一条从一端到另一端的路径
- 4 个或更多:一笔画不出来
欧拉路径探索器
能不能不抬笔、也不重复任何一条线,把圣尼古拉斯的房子画出来?能,但只有从下面两个角之一起笔才行,而且每个角各有 44 种画法。原因在于顶点的度,也就是交汇于该点的线数:笔每经过一个顶点一次,就用掉它的两条线。莱昂哈德·欧拉在 1736 年通过柯尼斯堡七桥发现了这条规则。自己描一个图形,看看会在哪里卡住、为什么卡住,要个提示,或者看算法把它画出来。 选择一个图形并描画它:点一个顶点开始,然后按顺序点各条边或下一个顶点,也可以从顶点拖到顶点。每条边只能走一次。后退撤回一步,提示给出下一条安全的边,求解则一步步演示 Fleury 算法或 Hierholzer 算法。奇数顶点是实心的,每个顶点旁的标记是它的度。在绘制模式下,点空白处添加顶点,点两个顶点把它们连起来,再点一次添加第二条边;拖动顶点可以移动它。擦除会删去顶点和边。当奇数顶点多于两个时,添加会补上让图形可以一笔画成的边。
它是如何运作的
- 选一个图形,比如柯尼斯堡七桥、圣尼古拉斯的房子或一颗星,也可以在绘制模式下画你自己的图形,两个顶点之间想连几条边都行。
- 点一个顶点开始,然后按顺序点边或顶点,也可以从顶点拖到顶点。卡住时状态栏会说明原因;后退撤回一步,提示给出一条安全的边。
- 读图形下面的奇偶度规则,给画不成的图形补上它建议的边,或者按求解,看 Fleury 算法或 Hierholzer 算法一步步把它画出来。
为什么由奇数顶点说了算
笔画经过一个顶点时,沿一条线进来,又沿另一条线出去,所以它把这个顶点的线成对地用掉。只有笔画的起点和终点,才可能剩下一条没有配对的线。因此,线数为奇数的顶点必须是起点或终点。没有奇数顶点时,笔画会回到起点:这是欧拉回路。有两个时,笔画从一个走到另一个:这是欧拉路径。有四个或更多时,端点对一笔画来说太多了,k 个奇数顶点需要 k/2 笔。柯尼斯堡有四块陆地,桥数分别是五、三、三、三:四块都是奇数,所以没有哪趟步行能每座桥各走一次。只要在其中两块之间再修一座桥,这趟步行就成立了。
Fleury 算法与 Hierholzer 算法
知道一个图形画得出来,和真把它画出来是两回事:一笔下得不小心,就可能把自己和还没画的线隔开。Fleury 在 1883 年提出的算法用一条规则避免这件事:永远不要过桥,也就是不要走那种一旦去掉就会把剩余的线分成两块的线,除非别无选择。Hierholzer 的算法出自 1873 年发表的一篇论文,速度更快:随便走到走不动为止,而这只可能发生在起点;然后从回路上仍有空线的某个顶点出发,再走一个闭合的圈,把它接进回路。它的用时与边数成正比,计算机就是这样找欧拉路径的。
常见问题
欧拉路径和欧拉回路有什么区别?
两者都把图的每条边恰好走一次。欧拉回路回到起点;欧拉路径在别处收尾。连通图在每个顶点的度都是偶数时有回路,在恰好两个顶点的度是奇数时有路径,这时路径从其中一个走到另一个。
为什么柯尼斯堡七桥不能每座各走一次?
把每块陆地画成顶点,每座桥画成边。克奈普霍夫岛有五座桥,另外三块陆地各有三座,所以四个顶点都是奇数。步行只能在奇数顶点起止,而四个太多了。在其中两块之间加一座桥,就只剩两个奇数顶点,步行也就成立了。
圣尼古拉斯的房子有多少种画法?
下面两个角各有 44 种,一共 88 种,这里把不同的顺序或方向算作不同的画法。从其他任何顶点都画不成,因为只有这两个下角的线数是奇数。本应用就是用这种方式统计小图形的画法数。
图中的桥是什么?
一旦去掉就会把连通图分成两块的边。只要还有别的选择,Fleury 算法绝不会走剩余边中的桥,否则图形的一部分就会被落下。在本应用里,因为过桥过早而卡住的笔画,会被告知那是第几步。
两个顶点之间可以有不止一条边吗?
可以。有平行边的图叫多重图,柯尼斯堡正需要这样的图:有两座桥把克奈普霍夫岛和每一岸连起来。在绘制模式下再次点两个顶点,就能在它们之间加一条边,最多四条。奇偶度规则照常适用,每条边都算。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器