找出无向图的最大子集

Find out largest subset of an Undirected Graph

输入:顶点列表和邻接列表。

输出:好的顶点的最大子集。

(我们称子集中的一个顶点为 "good vertex",如果它在该子集中至少有 2 个相邻顶点和至少 2 个不相邻顶点。)

示例 1:

Vertexes: [1, 2, 3, 4, 5]
Relations: [(1,2), (1,3), (3,4), (3,5), (4,5)]

output: []

示例 2:

output: [1,2,3,4,5,6]

因为对于输出中的每个顶点,它至少有 2 个顶点与其相连,并且至少有 2 个顶点与其不相连。

如果一个顶点在图中有至少两个邻居和至少两个非邻居,则称它为 "okay"。顶点必须可以在输出中。

从图中删除所有不合格的顶点。执行此操作时,之前正常的顶点可能不再正常,因为它们 运行 超出了邻居或非邻居;这些顶点也不能在输出中,所以像对待任何其他不正常的顶点一样对待它们并将它们也移除。继续下去,直到所有剩余的顶点都可以。

输出剩余顶点的集合。

  1. 删除少于两个邻居的顶点。

  2. 构建左顶点的补边(关系)。补集在源关系集中没有相同的关系,但有其他关系。将原点关系集与补集结合起来,就变成了与左顶点的全关系的关系集。

  3. 删除补码中相邻点少于两个的顶点。结果顶点是输出。

step1和step3中的remove过程,是递归过程。它必须移除顶点,直到无法移除顶点为止。