如何知道圖中的哪些節點是可移動的

我有一個圖形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))

我想知道哪些節點是「可移動」，即消除他們的圖形仍然是完全連接，然後，如果刪除「可移動後「節點cumsum增加，刪除增加最多的節點。一旦與漲幅最高的「可移動」節點被刪除我想重新開始的過程，直到出現在cumsum沒有增加時，「可移動」節點被移除

來源

2015-11-24 user2380782

算法問題...檢查其他SE網站。 – smci

你節點有什麼屬性？您可以在刪除節點後運行DFS或BFS，以檢查到達的節點數是否爲| | V（g）| - （n + 1）|'，其中n是已刪除節點的數量。 –

@MarcoGetrost，我的節點有兩個屬性，'weight'和'RWRnodeweight'，用於計算'cumsum' – user2380782

我想知道哪些節點是「可移動「，即在刪除它們之後，圖表仍然完全連接

articulation.points告訴您其刪除將增加連接組件數量的節點列表。在此列表中的任何節點而不是都可以安全地刪除。然後你必須遍歷這個列表並計算新值cumsum（不包括每個節點一個接一個），以找出哪一個最好刪除。

來源

2015-11-24 09:51:51

謝謝@Tamas作爲答案，'articulation.points'給了我一個很好的起點 – user2380782

您可以計算spanning tree，然後您可以刪除末端節點（具有單個頂點的節點），直到您達到單個節點（如果需要）。

來源

2015-11-24 10:09:40

如何知道圖中的哪些節點是可移動的

回答

相關問題