961
个编辑
更改
跳到导航
跳到搜索
第91行：
第91行： − + 第99行：
第99行： − + 第123行：
第123行： − + − + − + − + − 在他1736年关于柯尼斯堡七桥问题图的论文中，被广泛认为是图论的诞生，Leonhard Euler 证明了，对于一个有限的无向图来说，如果有一个封闭的步行恰好访问每条边一次，那么除了孤立的顶点(也就是说，所有的边都包含在一个分量中)和每个顶点的度之外，它是连通的，这是充分必要的。在有向图中，存在一个正好一次访问每条边的闭角色塑造的对应条件是该图是强连通的并且在每个顶点上有相等数目的入边和出边。无论哪种情况，最终的行走都被称为欧拉循环或欧拉环。如果一个有限的无向图在它的每个顶点上都有偶数度，不管它是否连通，那么就有可能找到一组简单的圈，它们一起精确地覆盖每条边一次: 这就是维布伦定理。当连通图不满足欧拉定理的条件时，通过求解路径检查问题，可以在多项式时间内找到覆盖每条边至少一次的最小长度封闭行走。+ − + − + − 找到一个单一的简单循环恰好覆盖每个顶点一次，而不是覆盖边，这个问题要困难得多。这样的循环称为哈密顿循环，确定它是否存在是 np 完全的+ − − | author = [[Richard M. Karp]] − − | author = Richard M. Karp − − 作者: Richard m. Karp − − | chapter = Reducibility Among Combinatorial Problems − − | chapter = Reducibility Among Combinatorial Problems − − | 章 = 组合问题中的可约性 − − | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf − − | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf − − | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf − − | title = Complexity of Computer Computations − − | title = Complexity of Computer Computations − − | title = 计算机计算的复杂性 − − | editor = R. E. Miller and J. W. Thatcher − − | editor = R. E. Miller and J. W. Thatcher − − 编辑: r. e. Miller 和 j. w. Thatcher − − | publisher = New York: Plenum − − | publisher = New York: Plenum − − | publisher = New York: Plenum − − | pages = 85–103 − − | pages = 85–103 − − | 页数 = 85-103 − − | year = 1972}}.</ref> Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is [[Ore's theorem]] that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.<ref>{{citation|first=Ø.|last=Ore|authorlink=Øystein Ore|title=Note on Hamilton circuits|journal=[[American Mathematical Monthly]]|volume=67|year=1960|page=55|issue=1|jstor=2308928|doi=10.2307/2308928}}.</ref> − − | year = 1972}}.</ref> Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph. − − 1972}}.关于可以保证包含哈密顿圈的图类，已经发表了许多研究成果，其中一个例子是奥尔定理，即哈密顿圈总是可以在一个图中找到，对于这个图，每一对不相邻的顶点都有至少与图中顶点总数相加的度数。 第199行：
第151行： − 圈双覆盖猜想指出，对于每一个无桥图，存在一个正好两次覆盖图的每条边的多个简单圈集。证明这是正确的(或者找到一个反例)仍然是一个悬而未决的问题+ − − | last = Jaeger | first = F. − − | last = Jaeger | first = F. − − | last = Jaeger | first = f. − − | contribution = A survey of the cycle double cover conjecture − − | contribution = A survey of the cycle double cover conjecture − − | 贡献 = 循环双重覆盖猜想的研究 − − | doi = 10.1016/S0304-0208(08)72993-1 − − | doi = 10.1016/S0304-0208(08)72993-1 − − | doi = 10.1016/S0304-0208(08)72993-1 − − | pages = 1–12 − − | pages = 1–12 − − | 页数 = 1-12 − − | series = North-Holland Mathematics Studies − − | series = North-Holland Mathematics Studies − − | 系列 = 北荷兰数学研究 − − | title = Annals of Discrete Mathematics 27 – Cycles in Graphs − − | title = Annals of Discrete Mathematics 27 – Cycles in Graphs − − | title = 离散数学年鉴27- 图中的圈 − − | volume = 27 − − | volume = 27 − − 27 − − | year = 1985}}..</ref> − − | year = 1985}}..</ref> − − 1985} . . </ref > − −
→Cycle detection 环检测
== Cycle detection 环检测 ==
== Cycle detection 环检测 ==
The existence of a cycle in directed and undirected graphs can be determined by whether [[depth-first search]] (DFS) finds an edge that points to an ancestor of the current vertex (it contains a [[Depth-first search#Output of a depth-first search|back edge]]).<ref>{{cite book|last=Tucker|first=Alan|authorlink=Alan Tucker|title=Applied Combinatorics |year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref>All the back edges which DFS skips over are part of cycles.<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only ''O''(''n'') time is required to find a cycle in an ''n''-vertex graph, since at most ''n'' − 1 edges can be tree edges.
The existence of a cycle in directed and undirected graphs can be determined by whether [[depth-first search]] (DFS) finds an edge that points to an ancestor of the current vertex (it contains a [[Depth-first search#Output of a depth-first search|back edge]]). In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only ''O''(''n'') time is required to find a cycle in an ''n''-vertex graph, since at most ''n'' − 1 edges can be tree edges.
The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge).All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.
The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge).All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.
Many [[topological sorting]] algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into [[strongly connected component]]s, cycles only exist within the components and not between them, since cycles are strongly connected.<ref name="sedgewick" />
Many [[topological sorting]] algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into [[strongly connected component]]s, cycles only exist within the components and not between them, since cycles are strongly connected.
Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
Applications of cycle detection include the use of [[wait-for graph]]s to detect [[deadlock]]s in concurrent systems.<ref>{{cite book
Applications of cycle detection include the use of [[wait-for graph]]s to detect [[deadlock]]s in concurrent systems.
Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.<ref>{{cite book
Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.
环检测的应用还包括使用等待图来检测并发系统中的死锁。
环检测的应用还包括使用等待图来检测并发系统中的死锁。
== Covering graphs by cycles ==
== Covering graphs by cycles 环覆盖图 ==
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]].<ref>{{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | title=An Application of Modular Equations in Analysis Situs | jstor=1967604 | series=Second Series | year=1912 | journal=[[Annals of Mathematics]] | volume=14 | issue=1 | pages=86–94 | doi = 10.2307/1967604 }}.</ref> 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]].
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年发表的关于柯尼斯堡七桥的论文，这篇论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者经过每条边恰好一次。其充分必要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是维勃伦定理Veblen's theorem。当一个连通图不满足欧拉定理的条件时，通过解决邮路问题，可以在多项式时间内找到覆盖每个边的最短闭合路径。
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]].<ref>{{citation
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.<ref>{{citation
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.
相比较，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为哈密顿环，确定其存在性的过程属于NP-完全问题。目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是奥尔定理Ore's theorem，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。
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
双圈覆盖猜想指出，对于每个无桥图，都存在一组简单环可以将图的每个边缘恰好覆盖两次。然而目前其是否成立（或找到反例）仍然是一个悬而未决的问题。
== Graph classes defined by cycles ==
== Graph classes defined by cycles ==