欧拉径

一个欧拉路径在一个图表上是一个穿过每个边缘的图形一直通过一次，并且对这条路径的研究提出了与欧拉在18世纪研究的问题的关系，就像下面的欧拉一样：

在尝试并无法绘制这样的路径之后，它似乎可以合理于此任务是不可能的。但这怎么能被证明吗？如果桥梁的配置略有不同，怎么办？（例如，除了一个桥梁之外并不难，并向现有七个添加另一桥也将允许完整的交叉。）有没有办法表征允许这些路径的配置？如果需要路径以在同一个地方开始和结束怎么办？

这些问题的答案最早是在1736年由Leonhard欧拉这篇论文证明了第一个结果，也就是现在所说的图论理论．通过所有桥的路径(或者更笼统地说，通过图的所有边的路径)称为欧拉道路和在同一位置开始和结束的欧拉岛路径欧拉电路．

上面的问题被称为Konigsberg的桥梁这个问题以普鲁士普雷格尔河上的一座城市命名，其桥的结构如图所示。

图片中有四个山泥。穿过桥梁的每一个道路都将在这四个山泥之间来回来回。假设有一个人站在每个山地上，看着有人走路，每次步行者都进入或退出陆地数（包括他们计数的路径的开始和结束）。如果有一条路径一直穿过每个桥梁一次，当助行器完成时，柜台的数量会是什么？

顶部的柜台将有 $3.$，因为连接他的大陆的三座桥中，每座桥都只经过一次，而每座桥都将被视为入口或出口。同样，中间岛屿上的计数器也会显示 $5$，右边的计数器会显示 $3.$，底部的柜台将显示 $3.$．

但是每次通过一次都会进入并退出每个陆地，这是贡献 $2$到计数，所以每个计数器的最终计数应该是偶数 - 除了计算路径的开始和结尾的两个计数器（第一个退出没有相应的条目，并且最后一个条目都没有有一个相应的出口）。尽管如此，所有四个计数器都不可能以奇数结束，因此没有这样的路径。

这个问题可以用图论理论,如下所示。考虑这个图，它的顶点对应于四个陆块，顶点之间的边对应于桥。所讨论的路径是通过每条边恰好一次的图的遍历。或者，换句话说，它是在一张纸上画一个图形，而不需要拿起铅笔或不止一次地画任何边。

接下来，我们假设图是有限的(顶点和边的数量是有限的)。回忆,学位图中一个顶点的边数是与该顶点相接触的边数。

这是桥问题对应的图。

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

一个欧拉路径在图形上是一个穿过每个边缘一次的图形的遍历。它是一个欧拉回路如果它开始和结束在同一个顶点。 $_ \广场$

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

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

更有趣和困难的陈述是匡威。什么条件保证欧拉路径或欧拉电路的存在？事实证明，除了最必要的条件之外，唯一的其他要求是任何两个程度的明显之一 $通用电气\ 1$他们之间有一条路。

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

每个(有限)图都可以被唯一分解成连接组件：每个组件是连接的子图，并且在任何两个组件之间没有边缘。程度为零的顶点是其自己的连接组件。

如果（1）每个程度的每个顶点，则图表具有eulerian路径 $通用电气\ 1$位于同一连通分量，且(2)有0或2个奇数次顶点。
图表具有欧拉电路，如果才有（1）每个顶点的（1） $通用电气\ 1$(2)每个顶点都有偶数度。 $_ \广场$

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

为了证明该定理，通过上述讨论，建立了“仅当”命题。证明“如果”命题的一种方法是通过Fleury的算法，它构造了一个欧拉路径或电路。

如果有两个奇数度的顶点，从其中一个开始。否则，从任意顶点开始。在算法的每一步，选择一条即使被移除也不会断开图的边，除非没有这样的边。(如果移除将断开图形的边——在这种情况下有点令人困惑——被称为桥梁。）沿着这个边缘移动并完成一旦完成从图表中删除它。继续。

结果表明，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-1-3-4-7-8-1。现在顶点1不再具有未使用的边缘，但顶点4确实如下：绘制4-5-9-4。将其粘在前一个电路中 $1-2-3-7-1-3 - {\ bf 4-5-9-4} -7-8-1。$最后，顶点9留下了一些未使用的边缘，因此绘制电路9-6-7-9并注意所有边缘都已使用。把它贴在前一条电路中获得 $1-2-3-7-1-3-4-5 - {\ bf 9-6-7-9} -4-7-8-1。$

KONIGSBERG桥梁具有在任何两种山地之间添加或删除桥梁的有趣属性将允许欧拉岛路径。实际上，添加或删除桥将改变关联图中的四个顶点中的两个顶点的度的奇偶校验，这将使它们均匀。然后将有两个奇数的顶点，这将意味着欧拉道路的存在。

这说明了定理的力量;不必在可能出现的各种情况下绘制的路径，尽管可以给予欧拉路径存在的问题。

这个定理的另一个应用是解决下列难题:

假设房子里的五个房间如下所示：

想象一扇门切成每个房间的每个墙壁（包括外部）。是否有一条路径遍布每扇门一次？

---

答案是否定的，因为关联的图表有四个奇数顶点。以下是KONIGSBERG和五个房间问题的图形，每个顶点上有学位，具有学位。

请注意，在五个房间问题中可以构建通过除One One之外的所有通道的路径，但在这种情况下只能省略某些门;门必须对应于连接两个奇数顶点的边缘。 $_ \广场$

1. 锡锡，C.Hierholzer的算法．2008年8月8日从https://commons.wikimedia.org/wiki/file:hierholzer_（3）.png