中文
Sign in
AI tools
聊天
热门问题
时间线
Loading AI tools
全部
文章
字典
引用
地图
Vertex cover
来自维基百科,自由的百科全书
Found in articles
覆盖 (图论)
图的覆盖是一個顶点的集合,使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题(
Vertex
cover
(英语:
Vertex
cover
)),它是一个NP完全问题。 顶点覆盖和边覆盖分别与独立集合和匹配问题有关。 图G的顶点覆盖是一个顶点集合V,使得G中的每一条边都
卡普的二十一個NP-完全問題
integer programming) 分團問題(Clique,參考獨立集) Set packing(Set packing) 最小顶点覆盖问题(
Vertex
cover
) 集合覆盖问题(Set covering) Feedback node set(Feedback node set) Feedback arc
边覆盖
集合的元素是顶点,每个子集正好覆盖两个元素。 Garey & Johnson (1979), p. 79, uses edge
cover
and
vertex
cover
as one example of a pair of similar problems, one of which can be
数据结构与算法术语列表
卡诺图(Veitch diagram) 文氏图(Venn diagram) 顶点 (图论)(
vertex
) 顶点着色(
vertex
coloring) 顶点连通性(
vertex
connectivity) 顶点覆盖(
vertex
cover
) 虚拟可见地图(vertical visibility map) 虚拟散列法(virtual
NP完全
problem(英语:Subgraph isomorphism problem)) 子集合加總問題 分團問題 頂點覆盖問題:(
Vertex
cover
(英语:
Vertex
cover
)) 獨立頂點集問題:(Independent set problem(英语:Independent set problem))