更改

In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once, it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting walk is known as an Euler cycle or Euler tour. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is Veblen's theorem. When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem.

In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once, it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting walk is known as an Euler cycle or Euler tour. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is Veblen's theorem. When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem.

莱昂哈德·欧拉Leonhard Euler在1736年发表的关于'''<font color="#ff8000"> 柯尼斯堡七桥Seven Bridges of Königsberg</font>'''的论文，这篇论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者经过每条边恰好一次。其充分必要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理Veblen's theorem</font>'''。当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000"> 邮路问题Route inspection problem</font>'''，可以在多项式时间内找到覆盖每个边的最短闭合路径。

莱昂哈德·欧拉Leonhard Euler在1736年发表的关于'''<font color="#ff8000"> 柯尼斯堡七桥Seven Bridges of Königsberg</font>'''的论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理Veblen's theorem</font>'''。当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000"> 邮路问题Route inspection problem</font>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP-complete.

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP-complete.

相比较，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为'''<font color="#ff8000"> 哈密顿环Hamiltonian cycle</font>'''，确定其存在性的过程属于NP-完全问题。目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''<font color="#ff8000"> 奥尔定理Ore's theorem</font>'''，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。

相较之下，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为'''<font color="#ff8000"> 哈密顿环Hamiltonian cycle</font>'''，确定其存在性的过程属于NP-完全问题。目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''<font color="#ff8000"> 奥尔定理Ore's theorem</font>'''，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。