← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

35 第35章 近似算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.785Z

—in particular, an optimal cover C*—must include at least one endpoint of each edge in A.

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

vertex cover. Each execution of line 4 picks an edge for which neither of its endpoints i

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter035.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea