修剪网络中节点的算法，实现最大隔离数（python networkx）
Algorithm to prune nodes in network, achieve maximum number of isolates (python networkx)
我有网络（大&小），我需要对其进行修剪，直到只剩下孤立的网络。我想最大化隔离的数量。有没有算法可以做到这一点？如果它更复杂？ （例如，在底部也可能有连接的节点）
考虑这个简单的例子：
import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (2,4), (3,5), (3,6), (4,7), (4,8),
(1,2+9), (2+9,3+9), (2+9,4+9), (3+9,5+9), (3+9,6+9), (4+9,7+9), (4+9,8+9) ])
这里最优解是删除节点1,3,4,11,12
这听起来像是您想要计算 Maximum Independent Set（NP-hard 对于 一般图 ）。 （维基百科还提到了名称 vertex packing）。
Networkx 有一个 approximation algorithm。
也许一个近似值对你来说不够（而且我认为没有预构建的替代方案）。
根据上面的维基百科-link，在igraph.
中有一个精确的算法可用
另请记住，此近似算法适用于一般图，因此很有可能有更好的树方法。
编辑：（不检查）This SO-answer presents an algorithm for trees（问题可能重复）。
我有网络（大&小），我需要对其进行修剪，直到只剩下孤立的网络。我想最大化隔离的数量。有没有算法可以做到这一点？如果它更复杂？ （例如，在底部也可能有连接的节点）
考虑这个简单的例子：
import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (2,4), (3,5), (3,6), (4,7), (4,8),
(1,2+9), (2+9,3+9), (2+9,4+9), (3+9,5+9), (3+9,6+9), (4+9,7+9), (4+9,8+9) ])
这里最优解是删除节点1,3,4,11,12
这听起来像是您想要计算 Maximum Independent Set（NP-hard 对于 一般图 ）。 （维基百科还提到了名称 vertex packing）。
Networkx 有一个 approximation algorithm。
也许一个近似值对你来说不够（而且我认为没有预构建的替代方案）。
根据上面的维基百科-link，在igraph.
中有一个精确的算法可用另请记住，此近似算法适用于一般图，因此很有可能有更好的树方法。
编辑：（不检查）This SO-answer presents an algorithm for trees（问题可能重复）。