9.18.1. 团到独立集¶

下面的幻灯片表明， CLIQUE 的一个实例可以在多项式时间内归约为 INDEPENDENT SET 的一个等价实例。

Settings

Saving...
Server Error
Resubmit

这个归约有助于为独立集（Independent Set）问题提供 NP 完全性证明。

下面的练习给你一个机会，让你重现 INDEPENDENT SET 是 NP 完全的证明。这将有助于确认你是否理解这一过程。