从网络中选取最大节点数，使 none 连接 1 度
Picking maximum number of nodes from network so that none are connected by 1 degree
我有以下网络或图形问题。
从网络中选择最大数量的节点，使得没有节点以 1 度连接。例如，从这些边给出的网络：
a - b
b - c
我可以选择 b，或者我可以选择 a 和 c。 c 会更好。
这个网络问题有名称吗？我可以使用什么算法来解决它？
这似乎是 Independent Set Problem, which is the complement of the Clique Problem，即在图中找到一个节点子集，使得每个节点都直接连接到该子集中的所有其他节点。
您可以通过 "inverting" 图将您的问题简化为集团问题，即在所有未连接的节点之间添加边，并删除所有旧边，然后找到一个 maximum clique of that complement graph。
问题是 NP 完全问题，尽管似乎有一些聪明的算法，其指数的基数相当 "low"。如果次优解决方案也是可以接受的，您可以尝试贪婪，首先选择边数最少的节点（在原始图中），添加更多未连接到任何所选节点的低度节点，以便-far.
我有以下网络或图形问题。
从网络中选择最大数量的节点，使得没有节点以 1 度连接。例如，从这些边给出的网络：
a - b
b - c
我可以选择 b，或者我可以选择 a 和 c。 c 会更好。
这个网络问题有名称吗？我可以使用什么算法来解决它？
这似乎是 Independent Set Problem, which is the complement of the Clique Problem，即在图中找到一个节点子集，使得每个节点都直接连接到该子集中的所有其他节点。
您可以通过 "inverting" 图将您的问题简化为集团问题，即在所有未连接的节点之间添加边，并删除所有旧边，然后找到一个 maximum clique of that complement graph。
问题是 NP 完全问题，尽管似乎有一些聪明的算法，其指数的基数相当 "low"。如果次优解决方案也是可以接受的，您可以尝试贪婪，首先选择边数最少的节点（在原始图中），添加更多未连接到任何所选节点的低度节点，以便-far.