387
个编辑
更改
跳到导航
跳到搜索
第205行：
第205行： − + 第212行：
第212行： − 闭包问题以一个顶点加权有向无环图为输入，寻求一个闭包的最小(或最大)权重-一组顶点 c，这样没有边离开 c。这个问题可以在没有无环性假设的情况下表示为有向图，但没有更大的一般性，因为在这种情况下，它等价于图的凝聚上的同样问题。通过对最大流问题的约简，可以在多项式时间内求解。+ −
→Closure problem
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递归约包含后者，传递归约可以在和传递闭包相同的渐进时间复杂度（英语：Asymptotic computational complexity）中被构建。[25]
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递归约包含后者，传递归约可以在和传递闭包相同的渐进时间复杂度（英语：Asymptotic computational complexity）中被构建。[25]
=== Closure problem ===
=== Closure problem 闭包问题 ===
The [[closure problem]] takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices ''C'', such that no edges leave ''C''. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the [[maximum flow problem]].<ref>{{citation | last = Picard | first = Jean-Claude | doi = 10.1287/mnsc.22.11.1268 | issue = 11
The [[closure problem]] takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices ''C'', such that no edges leave ''C''. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the [[maximum flow problem]].<ref>{{citation | last = Picard | first = Jean-Claude | doi = 10.1287/mnsc.22.11.1268 | issue = 11
| journal = [[Management Science (journal)|Management Science]] | mr = 0403596 | pages = 1268–1272 | title = Maximal closure of a graph and applications to combinatorial problems | volume = 22
| journal = [[Management Science (journal)|Management Science]] | mr = 0403596 | pages = 1268–1272 | title = Maximal closure of a graph and applications to combinatorial problems | volume = 22
The closure problem takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices C, such that no edges leave C. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the maximum flow problem.
The closure problem takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices C, such that no edges leave C. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the maximum flow problem.
闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。闭包问题（英语：closure problem）是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作最大流问题的简化版，在多项式时间内被解决。实际上，是否有环对于找到闭包没有影响。[26]
=== Path algorithms ===
=== Path algorithms ===