algorithm - 如果图具有独立集，则从输出 1 的图构造一个回路

Question

假设我有一个图表，

并且从这个图中我想创建一个电路K，它的输入可以被设置，以便K输出真，如果该图有一个独立的大小≥2的集合。我在互联网 / youtube 上看到了一些关于如何解决这个问题的不错的东西。但我想知道是否有一套标准的步骤来说明如何做到这一点。

我的思考过程是这样的：让电路将边缘作为输入，如果至少有一个边缘缺失（因为这个边缘是一个独立的集合），则输出 1（真）。

但是，如果我说实话，我很难理解这一点。

标签： algorithmgraphreductionnpcircuit-diagram

Answer 1

您的方法在概念上是正确的，但还有一种更简单的方法：计算图中的边。对于 N 个节点，如果 |E| < N * (N-1) / 2，那么您至少有一组独立的大小 >= 2。正如您所指出的，所需要的只是一个缺失的边缘。

为了找到最大的独立集，有一个概念上相对简单的转换技巧：反转图形：切换所有非边和边。例如，您发布的图表包含可能的 6 条边中的 4 条。反转这个，所以你的图边只有DB和DC。

获取结果图并找到最大的集团（这上有很多材料）。那个最大的集团是最大的独立图。