1

假设给你一个黑盒子，它可以在恒定时间内解决一个派系问题。

你给黑盒子一个有界 k 的无向图 G，它输出“是”或“否”，即图 G 有一个至少有 k 个顶点的团。

你将如何使用这个黑盒在多项式时间内找到最大团的顶点？

4

1 回答 1

1

作为提示，想想如果从图中选择一个节点，将其删除，然后检查是否仍然存在 k-clique，会发生什么情况。黑匣子要么说有，要么说没有。如果仍然存在 k-clique，你会学到什么？如果没有，你会学到什么？

希望这可以帮助！

于 2014-11-03T19:03:08.450 回答