387
个编辑
更改
跳到导航
跳到搜索
第76行：
第76行： − +
→闭包问题
=== 闭包问题 ===
=== 闭包问题 ===
闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。{{tsl|en|closure problem|闭包问题}}是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作[[最大流问题]]的简化版，在[[多项式时间]]内被解决。实际上，是否有环对于找到闭包没有影响。<ref>{{citation
闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。<font color="#ff8000"> 闭包问题 Closure problem </font>是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作<font color="#ff8000"> 最大流问题 </font>的简化版，在<font color="#ff8000"> 多项式时间 </font>内被解决。实际上，是否有环对于找到闭包没有影响。<ref>{{citation
| last = Picard | first = Jean-Claude
| last = Picard | first = Jean-Claude
| doi = 10.1287/mnsc.22.11.1268
| doi = 10.1287/mnsc.22.11.1268