2,443
个编辑
更改
跳到导航
跳到搜索
第63行：
第63行： − 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. − + + − 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>'''，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。 − − − − The [[cycle double cover conjecture]] states that, for every [[bridgeless graph]], there exists a [[multiset]] of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.<ref>{{citation − − The cycle double cover conjecture states that, for every bridgeless graph, there exists a multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.<ref>{{citation
→环覆盖图
== 环覆盖图 ==
== 环覆盖图 ==
莱昂哈德·欧拉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年发表的关于'''柯尼斯堡七桥Seven Bridges of Königsberg'''的论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理Veblen's theorem</font>'''。当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000"> 邮路问题Route inspection problem</font>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。
相较之下，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为'''哈密顿环Hamiltonian cycle'''，确定其存在性的过程属于NP-完全问题。目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''奥尔定理Ore's theorem'''，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。
'''<font color="#ff8000"> 双圈覆盖猜想Cycle double cover conjecture</font>'''指出，对于每个无桥图，都存在一组简单环可以将图的每个边缘恰好覆盖两次。然而目前其是否成立（或找到反例）仍然是一个悬而未决的问题。
'''<font color="#ff8000"> 双圈覆盖猜想Cycle double cover conjecture</font>'''指出，对于每个无桥图，都存在一组简单环可以将图的每个边缘恰好覆盖两次。然而目前其是否成立（或找到反例）仍然是一个悬而未决的问题。