打开主菜单
首页
随机
登录
设置
关于集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
免责声明
集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
搜索
更改
←上一编辑
下一编辑→
有向无环图
(查看源代码)
2021年6月2日 (三) 22:00的版本
添加74字节
、
2021年6月2日 (三) 22:00
→闭包问题
第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
孙钦贵
387
个编辑