961
个编辑
更改
跳到导航
跳到搜索
第89行：
第89行： − + 第95行：
第95行： − 在有向图和无向图中，圈的存在性取决于深度优先搜索是否找到一条指向当前顶点祖先的边(它包含一条后边)。DFS 跳过的所有后边都是循环的一部分。在无向图中，一个节点的父节点的边不能算作后边，但是找到任何其他已经访问过的顶点都表示后边。在无向图的情况下，只需要 o (n)时间就可以在 n 点图中找到一个圈，因为最多 n-1条边可以是树的边。+ 第103行：
第103行： − 许多拓扑排序周期算法也会检测周期，因为这些是拓扑有序周期存在的障碍。另外，如果一个有向图被划分为强连通分支，则圈只存在于分支之内而不存在于它们之间，因为圈是强连通的。+ 第111行：
第111行： − 对于有向图，可以使用基于消息的分布式算法。这些算法依赖于这样一种思想，即一个顶点在一个周期中发送的消息会返回到它自己。+ + + 第117行：
第119行： − 分布式循环检测算法对于在超级计算机上使用分布式图形处理系统处理大规模图形非常有用。分布式循环检测算法是一种非常有用的计算机集群。+ 第125行：
第127行： − 循环检测的应用包括使用等待图来检测并发系统中的死锁+ − − | last = Silberschatz − − | last = Silberschatz − − | last = Silberschatz − − | first = Abraham − − | first = Abraham − − | first = Abraham − − |author2=Peter Galvin |author3=Greg Gagne − − |author2=Peter Galvin |author3=Greg Gagne − − 2 = Peter Galvin | author3 = Greg Gagne − − | title = Operating System Concepts − − | title = Operating System Concepts − − 操作系统概念 − − | url = https://archive.org/details/operatingsystemc0006silb − − | url = https://archive.org/details/operatingsystemc0006silb − − Https://archive.org/details/operatingsystemc0006silb − − | url-access = registration − − | url-access = registration − − | url-access = registration − − | publisher = John Wiley & Sons, INC. − − | publisher = John Wiley & Sons, INC. − − 2012年10月21日 | 出版商 = 约翰威立。 − − | year = 2003 − − | year = 2003 − − 2003年 − − | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260] − − | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260] − − [ https://archive.org/details/operatingsystemc0006silb/page/260260] − − | isbn = 0-471-25060-0}}</ref> − − | isbn = 0-471-25060-0}}</ref> − − | isbn = 0-471-25060-0} </ref > − −
→Cycle detection
根据代数拓扑Algebraic topology的思想，二元环空间Binary cycle space可以推广为其他环Ring中的向量空间Vector spaces或模Module，例如整数，有理数或实数等。。
根据代数拓扑Algebraic topology的思想，二元环空间Binary cycle space可以推广为其他环Ring中的向量空间Vector spaces或模Module，例如整数，有理数或实数等。。
== 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]]).<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 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.
关于环在有向（无向）图中的存在性，可以通过深度优先搜索（DFS）来确定，具体方法是查找是否存在一条连边指向当前顶点的祖先点（包括回边）。DFS跳过的所有回边都是环的一部分。在无向图中，指向一个节点父级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。
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.
很多拓扑排序算法也可以用于检测环，因为这些环阻碍了拓扑排序。另外，如果一个有向图被划分为具有强连接的不同组成部分，则环仅存在于这些组成部分内，而不是它们之间，因为环本身性质就是强连接的。
For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself.
For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself.
对于有向图的环检测，可以使用基于分布式消息的算法。其概念是环中的某一个顶点发出了一条消息并最终返回，因此称为分布式环检测算法。
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a [[computer cluster]] (or supercomputer).
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a [[computer cluster]] (or supercomputer).
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).
通过在计算机集群（或超级计算机）上使用分布式图形处理系统，该方法非常适合大规模图的运算。
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.<ref>{{cite book
环检测的应用还包括使用等待图来检测并发系统中的死锁。
== Covering graphs by cycles ==
== Covering graphs by cycles ==