algorithm - 从网络中选取最大数量的节点，使得没有节点以 1 度连接

Question

我有以下网络或图形问题。

从一个网络中，选择最大数量的节点，使得没有节点以 1 度连接。例如，从由这些边给出的网络:

a - b
b - c

我可以选择 b，也可以选择 a 和 c。 c 会更好。

这个网络问题有名称吗？我可以使用什么算法来解决它？

Answer 1

这似乎是 Independent Set Problem , 这是 Clique Problem 的补码，即在图中找到一个节点子集，使得每个节点都直接连接到该子集中的所有其他节点。

您可以通过“反转”图形将问题简化为集团问题，即在所有未连接的节点之间添加边，并删除所有旧边，然后找到 maximum clique其中complement graph .

问题是 NP 完全问题，尽管似乎有一些聪明的算法，其指数基数相当“低”。如果次优解决方案也是可以接受的，您可以尝试贪婪，首先选择边数最少的节点(在原始图中)，添加更多未连接到任何所选节点的低度节点，以便-远。