最大独立集问题和（ ）问题等价。
A: 最小顶点覆盖
B: 稳定匹配问题
C: 最大团
D: 区间调度问题
A: 最小顶点覆盖
B: 稳定匹配问题
C: 最大团
D: 区间调度问题
举一反三
- 区间调度问题可以变换为最大独立集问题
- 最大独立集问题和（）问题等价。
- 区间调度问题可以变换为最大独立集问题 A: 正确 B: 错误
- 下面哪个问题不是NPC问题 A: 最大团问题 B: 子集和问题 C: 旅行售货员问题 D: 最小生成树问题
- 图[img=288x85]17d604369fd86cd.png[/img]的顶点子集[img=72x72]17d60436b0aa6bd.png[/img]称为顶点覆盖，若[img=62x68]17d60436c0cc4e3.png[/img]中每条边至少有一个端点在[img=72x72]17d60436b0aa6bd.png[/img]中。图[img=288x85]17d604369fd86cd.png[/img]的顶点子集[img=72x72]17d60436b0aa6bd.png[/img]称为独立集，若[img=72x72]17d60436b0aa6bd.png[/img]中任意两个顶点在[img=66x72]17d60436de24e06.png[/img]中无边相连。以下关于图的顶点覆盖和独立集的描述，正确的有（ ） 未知类型：{'options': ['若存在图的最小顶点覆盖问题最坏情况比为[img=46x52]17d60436eb25c5b.png[/img]的算法，也可得到图的最大独立集问题最坏情况比为[img=46x52]17d60436eb25c5b.png[/img]的算法。', '若求任意图的最小顶点覆盖是NP-难问题，则求任意图的最大独立集也是NP-难问题。', '若[img=72x72]17d60436b0aa6bd.png[/img]是[img=66x72]17d60436de24e06.png[/img]的顶点覆盖，则[img=156x75]17d604370e60f5f.png[/img]是[img=66x72]17d60436de24e06.png[/img]的独立集。', '若存在求任意图的最小顶点覆盖的算法，也可得到求任意图的最大独立集的算法。'], 'type': 102}