← 学习库 Discrete Mathematics (Levin) · 中英对照 目录

4.4 Euler Paths and Circuits 欧拉路径与回路

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 4.4 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

An Euler path, in a graph or multigraph, is a walk through the graph which uses every edge exactly once. An Euler circuit is an Euler path which starts and stops at the same vertex. Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.

在图（或重图）中，欧拉路径是一种经过图中每条边恰好一次的游走；欧拉回路则是起点与终点为同一顶点的欧拉路径。我们的目标是找到一种快速方法，判断一个图（或重图）是否存在欧拉路径或欧拉回路。
  1. Which of the graphs below have Euler paths? Which have Euler circuits?
    image-129.svg image-130.svg image-131.svg image-132.svg
  2. List the degrees of each vertex of the graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?
  3. Is it possible for a graph with a degree 1 vertex to have an Euler circuit? If so, draw one. If not, explain why not. What about an Euler path?
  4. What if every vertex of the graph has degree 2. Is there an Euler path? An Euler circuit? Draw some graphs.
  5. Below is part of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler path or circuit?
    image-133.svg
  1. 下面哪些图有欧拉路径？哪些有欧拉回路？
  2. 列出上面各图每个顶点的度数。度数与欧拉路径、欧拉回路的存在性之间是否存在关联？
  3. 一个含有度为 1 的顶点的图，是否可能有欧拉回路？若可能，画出一个例子；若不可能，说明理由。那欧拉路径呢？
  4. 如果图的每个顶点度数都是 2，情况如何？是否存在欧拉路径？是否存在欧拉回路？画几个图看看。
  5. 下面是某个图的一部分。即便你只能看到其中部分顶点，能否推断该图是否会有欧拉路径或回路？

If we start at a vertex and trace along edges to get to other vertices, we create a walk through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence. If the walk travels along every edge exactly once, then the walk is called an Euler path (or Euler walk). If, in addition, the starting and ending vertices are the same (so you trace along every edge exactly once and end up where you started), then the walk is called an Euler circuit (or Euler tour). Of course if a graph is not connected, there is no hope of finding such a path or circuit. For the rest of this section, assume all the graphs discussed are connected.

若从一个顶点出发，沿着边走到其他顶点，便得到图中的一种游走。更确切地说，图中的一个游走是一个顶点序列，其中每个顶点都与它在序列里的前一个和后一个顶点相邻。若这种游走恰好经过每条边一次，则称其为欧拉路径（或欧拉游走）。进一步，若起点与终点相同（即恰好经过每条边一次并回到出发点），则称其为欧拉回路（或欧拉环游）。当然，若一个图不连通，就根本不可能存在这样的路径或回路。在本节余下部分，我们假设所讨论的图都是连通的。

The bridges of Königsberg problem is really a question about the existence of Euler paths. There will be a route that crosses every bridge exactly once if and only if the graph below has an Euler path:
image-134.svg

柯尼斯堡七桥问题，本质上就是关于欧拉路径存在性的问题。当且仅当下面的图存在欧拉路径时，才存在一条恰好穿过每座桥一次的路线：（图见英文块）

This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler path (let alone an Euler circuit). On small graphs which do have an Euler path, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler path or circuit, even if the graph is quite large.

这个图足够小，我们完全可以逐一检查所有不重复用边的游走，从而确证它不存在欧拉路径（更别提欧拉回路了）。对于确实存在欧拉路径的小图，通常也不难找到一个。我们的目标是找到一种快速方法，用以判断一个图——即便相当大——是否存在欧拉路径或欧拉回路。

One way to guarantee that a graph does not have an Euler circuit is to include a “spike,” a vertex of degree 1.
image-135.svg

要确保一个图没有欧拉回路，一种办法是加入一个“尖刺”——即一个度为 1 的顶点。（图见英文块）

The vertex a has degree 1, and if you try to make an Euler circuit, you see that you will get stuck at the vertex. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. It starts at the vertex a, then loops around the triangle. You will end at the vertex of degree 3.

顶点 a 的度数为 1。若你想构造一条欧拉回路，会发现你会卡在这个顶点上——它是个死胡同。除非你从它出发，但那样就无法再回来，因此不可能找到欧拉回路。不过却存在一条欧拉路径：它从顶点 a 出发，绕三角形一圈，最终停在度为 3 的那个顶点上。

You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there (after traversing every edge exactly once). After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again. Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again.

只要图中存在任一奇度顶点，你都会遇到类似的麻烦。若从这样的顶点出发，就不可能在那里结束（在恰好遍历每条边一次之后）。用掉一条边离开起点后，从该顶点伸出的边还剩偶数条：一半可用于回到该顶点，另一半用于离开。于是你回去、再离开，回去、再离开。要用完所有边，唯一的办法是把最后一条边用来离开该顶点。另一方面，若一个奇度顶点不是你路径的起点，那么你最终会卡在这个顶点上。路径会成对地使用该顶点关联的边——到达、再离开。最终这些边中只剩一条未被用掉，于是只留下一条用于到达的边，却没有可再离开的边了。

What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other. In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree.

这一切说明：若一个图有欧拉路径，且存在两个奇度顶点，那么欧拉路径必从一个奇度顶点出发，在另一个奇度顶点结束。在这种情况下，其余每个顶点都必须是偶度——因为到达与离开这些顶点所需的边数必须相等。欧拉回路又当如何？图里不能有任何奇度顶点，否则欧拉路径就必须在那里开始或结束，而无法二者兼得。因此，一个图要有欧拉回路，所有顶点都必须是偶度。

The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path. To prove this is a little tricky, but the basic idea is that you will never get stuck because there is an “outbound” edge for every “inbound” edge at every vertex. If you try to make an Euler path and miss some edges, you will always be able to “splice in” a circuit using the edges you previously missed.

其逆命题同样成立：若图的所有顶点都是偶度，则该图有欧拉回路；若恰好有两个奇度顶点，则该图有欧拉路径。证明这一点稍费周折，但其基本思想是：你永远不会卡住，因为每个顶点处每有一条“入边”，就有一条“出边”。如果你在构造欧拉路径时漏掉了一些边，总能借助先前漏掉的边，把一段回路“拼接”进去。

Euler Paths and Circuits 欧拉路径与回路

Since the bridges of Königsberg graph has all four vertices with odd degree, there is no Euler path through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.

由于柯尼斯堡七桥对应的图四个顶点全是奇度，因此不存在穿过该图的欧拉路径。也就是说，居民们不可能恰好每座桥都只经过一次。

Hamilton Paths 哈密顿路径

Suppose you wanted to tour Königsberg in such a way where you visit each land mass (the two islands and both banks) exactly once. This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path). We could also consider Hamilton cycles, which are Hamliton paths which start and stop at the same vertex.

假设你想游览柯尼斯堡，且每个陆地（两座岛与两岸）都恰好经过一次。这是可以做到的。用图论的术语说，我们问的是：是否存在一条恰好访问每个顶点一次的路径。这样的路径称为哈密顿路径（Hamilton path）。我们还可以考虑哈密顿圈（Hamilton cycle），即起点与终点相同的哈密顿路径。

Example 1

示例 1

Determine whether the graphs below have a Hamilton path.
image-136.svg image-137.svg

判断下面的图是否有哈密顿路径。（图见英文块）

Solution

解答

The graph on the left has a Hamilton path (many different ones, actually), as shown here:
image-138.svg

左侧的图存在哈密顿路径（实际上有很多种），如下图所示：（图见英文块）

The graph on the right does not have a Hamilton path. You would need to visit each of the “outside” vertices, but as soon as you visit one, you get stuck. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.

右侧的图没有哈密顿路径。你需要访问每个“外围”顶点，但一旦访问了其中一个，就会被卡住。注意，这个图也没有欧拉路径；当然，也存在有欧拉路径却没有哈密顿路径的图。（图见英文块）

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check wither there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve; it is an example of a problem which is NP-complete.

看起来寻找哈密顿路径应该更容易，因为图的边通常比顶点多，需要满足的条件更少。然而，没人知道这是否真的成立。目前还没有判断一个图是否有哈密顿路径的简单检验方法。对小路图这不是问题；但随着图规模增大，检查是否存在哈密顿路径会变得越来越困难。事实上，这是一个（就我们所知）对计算机而言也过于困难的问题的例子——它是一个 NP 完全问题。