如何知道图中的哪些节点是可移动的
How to know which nodes in a graph are removable
我有一个图 g 大约有 200 个顶点和一些属性，我想知道可以删除哪些节点，即，这意味着 g 仍然是一个连接的子网络删除它们，我也想知道哪个节点将产生我需要的属性的最高增长。
举个例子可能更容易理解
g <- erdos.renyi.game(200, 0.03)
V(g)$name <- 1:vcount(my_graph)
V(g)$weight <- rnorm(200)
V(g)$RWRNodeweight <- runif(200, min=0, max=0.05)
#Criteria to meet
cumsum <- sum(V(g)$weight*V(g)$RWRNodeweight)/sqrt(sum(V(g)$RWRNodeweight^2))
我想知道哪些节点是 "removable"，即删除它们后图仍然是完全连接的然后如果删除 "removable" 节点 cumsum 增加，请删除增幅最大的一个。一旦删除了增加最高的 "removable" 节点，我想重新开始该过程，直到删除 "removable" 节点时 cumsum 没有增加
I would like to know which nodes are "removable", i.e, after removing them the graph is still fully connected
articulation.points 告诉您删除这些节点会增加连通分量数的节点列表。此列表中 不 的任何节点都可以安全删除。然后你必须遍历这个列表并计算 cumsum 的新值（一一排除每个节点）以找到最好删除哪个。
您可以计算 spanning tree 然后您可以删除末尾的节点（具有单个顶点的节点），直到达到单个节点（如果需要）。
我有一个图 g 大约有 200 个顶点和一些属性，我想知道可以删除哪些节点，即，这意味着 g 仍然是一个连接的子网络删除它们，我也想知道哪个节点将产生我需要的属性的最高增长。
举个例子可能更容易理解
g <- erdos.renyi.game(200, 0.03)
V(g)$name <- 1:vcount(my_graph)
V(g)$weight <- rnorm(200)
V(g)$RWRNodeweight <- runif(200, min=0, max=0.05)
#Criteria to meet
cumsum <- sum(V(g)$weight*V(g)$RWRNodeweight)/sqrt(sum(V(g)$RWRNodeweight^2))
我想知道哪些节点是 "removable"，即删除它们后图仍然是完全连接的然后如果删除 "removable" 节点 cumsum 增加，请删除增幅最大的一个。一旦删除了增加最高的 "removable" 节点，我想重新开始该过程，直到删除 "removable" 节点时 cumsum 没有增加
I would like to know which nodes are "removable", i.e, after removing them the graph is still fully connected
articulation.points 告诉您删除这些节点会增加连通分量数的节点列表。此列表中 不 的任何节点都可以安全删除。然后你必须遍历这个列表并计算 cumsum 的新值（一一排除每个节点）以找到最好删除哪个。
您可以计算 spanning tree 然后您可以删除末尾的节点（具有单个顶点的节点），直到达到单个节点（如果需要）。