387
个编辑
更改
跳到导航
跳到搜索
第190行：
第190行： − + 第196行：
第196行： − 一个给定的有向无环图的传递闭包，包括顶点和边，可以通过使用广度优先搜索或深度优先搜索来测试每个顶点的可达性来及时构造。或者，它可以及时解决在哪里是矩阵乘法算法的指数; 这是一个理论上的改进超过了稠密图的界。+ + 第202行：
第203行： − 在所有这些传递闭包算法中，可以区分至少一条长度为2条或更多的路径可到达的顶点对和只能通过一条长度为1条路径连接的顶点对。传递约简由形成长度的边组成——一条路径是连接其端点的唯一路径。因此，传递约简可以在与传递闭包相同的渐近时间范围内构造。+ −
→Transitive closure and transitive reduction
任意有环有向图都可以被转化为有向无环图。只要从图中移除反馈节点集（英语：feedback vertex set）或反馈边集（英语：feedback arc set），即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是NP困难问题。[20] 另外一种将有环有向图去环的方法是将每个强连通分量收缩为一个顶点。[22] 对于无环图，它的最小反馈顶点或边集为空集，它的强连通分量则为自身。
任意有环有向图都可以被转化为有向无环图。只要从图中移除反馈节点集（英语：feedback vertex set）或反馈边集（英语：feedback arc set），即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是NP困难问题。[20] 另外一种将有环有向图去环的方法是将每个强连通分量收缩为一个顶点。[22] 对于无环图，它的最小反馈顶点或边集为空集，它的强连通分量则为自身。
=== Transitive closure and transitive reduction ===
=== Transitive closure and transitive reduction 传递闭包和传递归约===
The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω'' < 2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>
The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω'' < 2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>
The transitive closure of a given DAG, with vertices and edges, may be constructed in time by using either breadth-first search or depth-first search to test reachability from each vertex. Alternatively, it can be solved in time where is the exponent for matrix multiplication algorithms; this is a theoretical improvement over the bound for dense graphs.
The transitive closure of a given DAG, with vertices and edges, may be constructed in time by using either breadth-first search or depth-first search to test reachability from each vertex. Alternatively, it can be solved in time where is the exponent for matrix multiplication algorithms; this is a theoretical improvement over the bound for dense graphs.
有向无环图的传递闭包可以通过广度优先搜索或深度优先搜索对每个节点测试可达性来构建。算法对于一个有着n个顶点和m条边的有向无环图的复杂度为O(mn)。[22]也可以使用矩阵乘法算法（英语：matrix multiplication algorithm）中最快的Coppersmith–Winograd算法（英语：Coppersmith–Winograd algorithm），其复杂度为O(n2.3728639)。这个算法理论上在稠密图（英语：dense graph）中快过O(mn)。[23]
In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.
In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递归约包含后者，传递归约可以在和传递闭包相同的渐进时间复杂度（英语：Asymptotic computational complexity）中被构建。[25]
=== Closure problem ===
=== Closure problem ===