1

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

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

(如果一个子集中的顶点至少有 2 个相邻的顶点和至少 2 个不相邻的顶点,我们就称它为“好顶点”。)

示例 1:

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

例子

output: []

示例 2:
示例2

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

因为对于输出中的每个顶点,它至少有 2 个顶点连接,并且至少有 2 个顶点没有与之连接。

4

2 回答 2

3

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

从图中删除所有不正确的顶点。当你这样做时,以前正常的顶点可能会因为没有邻居或非邻居而不再正常;这些顶点也不能在输出中,所以像对待任何其他不正常的顶点一样对待它们并将它们也删除。继续前进,直到所有剩余的顶点都正常。

输出剩余顶点的集合。

于 2016-04-05T02:36:30.450 回答
0
  1. 删除具有少于两个邻居的顶点。

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

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

step1和step3中的remove过程是递归过程。它必须删除顶点,直到没有一个可以被删除。

于 2016-04-05T02:53:26.827 回答