欧拉路径

一个欧拉路径在一个图上是一个图的遍历，它恰好通过每条边一次，而这些路径的研究出现在它们与欧拉在18世纪研究的问题的关系中，如下图所示:

在尝试并未能画出这样一条道路之后，似乎似乎不可能完成这项任务。但是如何证明呢?如果桥梁的结构略有不同呢?(例如，除了一座桥外，要跨越所有的桥并不难，在现有的七座桥上再增加一座桥也可以实现完全跨越。)有没有一种方法可以描述这些路径的构型?如果路径需要在同一位置开始和结束，该怎么办?

这些问题的答案在1736年由欧拉他在一篇论文中证明了第一个结果，现在被称为图论．遍历所有桥的路径(或者，更一般地说，遍历底层图的所有边的路径)被称为欧拉路径，起始和结束于同一位置的欧拉路径称为欧拉路径欧拉回路．

上面的问题被称为哥尼斯堡桥这个问题以普雷格尔河上的一座普鲁士城市命名，桥的配置如图所示。

图片上有四个大陆块。每一条穿过这些桥的道路都会在这四个大陆之间来回穿梭。假设每个陆块上都有一个人站在那里，看着有人走在路上，计算步行者每次进入或离开陆块的次数(包括他们计算的路径的起点和终点)。如果有一条路径只经过每座桥一次，当步行者走完时，计数器的数字是多少?

上面的柜台会有 $3.$因为在他的陆地上的三座桥中，每一座桥都只经过一次，每次经过都将被算作一个入口或一个出口。同样，中间岛屿上的计数器也会显示出来 $5$，右边的计数器就会显示 $3.$，底部的计数器就会显示出来 $3.$．

但步行者每次经过每个大陆时都进出，这有助于 $2$对于计数，因此每个计数器的最终计数应该是偶数——除了两个计数器计数路径的开始和结束(第一个出口没有相应的条目，最后一个条目没有相应的出口)。但是，四个计数器都以奇数结尾是不可能的，所以没有这样的路径。

这个问题可以换种说法为图论，如下。考虑这个图形，顶点对应四个大陆块，顶点之间的边对应桥梁。所讨论的路径是对图的遍历，它只经过每条边一次。或者，换句话说，它是在纸上画一个图形，而不用拿起铅笔，也不用多次画任何边。

在接下来的内容中，图将被假定为有限的(具有有限个顶点和边)。回想一下学位图中顶点的边数是与顶点接触的边数。

这张图对应的是桥的问题。

原始问题中四个陆块之一对应的顶点的度数是上面证明中每个计数器的度数:顶部、右侧和底部顶点都有度数 $3.$左边顶点有度数 $5$．

一个欧拉路径在图上是对图的遍历，遍历的每条边都只经过一次。这是一个欧拉回路如果它开始和结束于同一个顶点。 $_ \广场$

上一节中的非正式证明，翻译成图论的语言，立即表明:

如果一个图允许欧拉路径，那么两者都有 $0$或 $2$奇数次顶点。如果一个图允许一个欧拉电路，那么就有 $0$奇数次顶点。

更有趣和更难的说法是相反的。什么条件能保证欧拉路径或欧拉电路的存在?事实证明，除了度的必要条件外，唯一的另一个条件是任意两个度顶点 $通用电气\ 1$在它们之间建立一条路径。

图表是连接如果任意两个顶点之间有一条路径。 $_ \广场$

每个(有限)图都可以被唯一地分解为连接组件:每个分量都是连通子图，且任意两个分量之间没有边。0度顶点是它自己的连通分量。

一个图具有欧拉路径当且仅当(1)每个度的顶点 $通用电气\ 1$(2)有0个或2个奇度顶点。
一个图具有欧拉电路当且仅当(1)每个度顶点 $通用电气\ 1$(2)每个顶点都是偶次的。 $_ \广场$

欧拉在1736年解决哥尼斯堡桥问题时，没有证明地提出了这个定理，但直到后期才给出证明 $19 ^ \文本{th}$世纪。

为了证明该定理，由上述讨论建立了“仅当”命题。证明“如果”语句的一种方法是通过以下算法，由于弗勒里构造了欧拉路径或电路。

如果有两个奇数度的顶点，从其中一个顶点开始。否则，从任意顶点开始。在算法的每一步，选择一条边，如果它被移除，它不会断开图，除非没有这样的边。(在这个上下文中，有些令人困惑的是，那些如果被移除就会断开图形的边被称为桥梁)。沿着这条边移动，一旦完成，就从图中删除它。继续下去。

可以证明，Fleury算法总是产生一个欧拉路径，如果每个顶点都是偶数次，则产生一个欧拉电路。这里使用了一个重要而直接的引理，即握手引理:

每个图都有偶数个奇数度的顶点。

证明:每条边都会碰到两个顶点，所以顶点的度数和等于边数的两倍。所以它是偶数。引理紧随其后。

这里不是给出这个证明的细节，而是给出一个由Hierholzer提出的同样有效的替代算法。该算法生成的是欧拉电路，但如果存在两个奇度顶点，则可以修改为生成欧拉路径。

假设每个顶点都是偶数次。从顶点开始 $v$然后沿着图上的一条路径，直到它回到 $v$．这总是可能的，因为路径所到达的顶点总是有奇数条未使用的边。这就产生了一个可能不是欧拉的电路;但如果不是，我们可以从一个顶点开始 $w$它有一些未使用的边然后沿着图中未使用的边的路径，直到它返回到 $w$．旧电路和新电路可以作为一个大电路(从 $v$，转至 $w$，做 $w$电路，继续剩下的 $v$电路)。重复此步骤，直到不再有未使用的边。 $\广场$

所有顶点都是偶数次的图。^[1]

考虑一下上面的图表。从顶点1开始，画一个电路1-2-3-7-1。有从顶点1发出的未使用的边，所以画另一个电路1-3-4 7-8-1。把它们组合成1-2-3-7- 3-4-7-8-1。现在顶点1不再有未使用的边，但顶点4有:画4-5-9-4。把这个插入前面的电路，得到 $1-2-3-7-1-3 -{\男朋友4-5-9-4}1-2-3-7-1-3。$最后，顶点9还有一些未使用的边，因此绘制电路9-6-7-9，并注意所有的边都已被使用。把它插入前面的电路得到 $1-2-3-7-1-3-4-5 -{\男朋友9-6-7-9}1-2-3-7-1-3-4-5。$

柯尼斯堡桥有一个有趣的特性，在任何两个大陆块之间增加或删除一座桥都将允许一条欧拉路径。实际上，添加或删除桥接将改变关联图的四个顶点中两个顶点的度的奇偶性，这将使它们都是偶数。那么就会有两个奇数次的顶点，这就意味着存在欧拉路径。

这说明了这个定理的力量;而不需要画出可能出现的各种情况下的路径，然而，对于欧拉路径的存在性问题，可以给出一个肯定的答案。

该定理的另一个应用是以下谜题:

假设一所房子里有五个房间的布局如下:

想象一下，每个房间的每面墙(包括外面)都有一扇门。每扇门都有只经过一次的路径吗?

---

答案是否定的，因为相关的图有四个奇数次的顶点。这里分别是哥尼斯堡问题和五室问题的图表，每个顶点上都有度数图。

请注意，在5个房间的问题中，有可能构造一条路径穿过所有的门，但在这种情况下，只有某些门可以省略;门必须对应一条连接两个奇度顶点的边。 $_ \广场$

1. 丁丁，C。Hierholzer的算法．检索于2008年8月8日，从https://commons.wikimedia.org/wiki/File Hierholzer_ (3) . png