知识卡片
不相交选边给出二倍界
每次选边后删除其两端相接的其他边,故被选边集合A两两不共享端点。
任意顶点覆盖至少要为A的每条边选一个不同端点,因而|C|≥|A|;算法恰取两端,|C|=2|A|≤2|C|。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
No two edges in A share an endpoint, since once an edge is picked in line 4, all other edges that are incident on its endpoints are deleted from E′ in line 6. Thus, no two edges in A are covered by the same vertex from C*, meaning that for every vertex in C*, there is at most one edge in A, giving the lower bound on the size of an optimal
参考来源
- 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[5000,10000))。
- 结论依据:第35章近似定义、顶点覆盖与满足三角不等式的旅行商算法;图35.1–35.2已核对。
- 原始内容:No two edges in A share an endpoint, since once an edge is picked in line 4, all other edges that are incident on its endpoints are deleted from E ′ in line 6. Thus, no two edges in A are covered by the same vertex from C *, meaning that for every vertex in C *, there is at most one edge in A , giving the lower bound on the size of an optimal