随机删除n条边而不断开连接图

Question

我在R中使用igraph包。我有一个连接图G=(V,E)，我如何随机删除一些边（如n < |E|）但不断开给定的图。换句话说，我不能删除任何bridges。关于如何完成的任何提示？

Answer 1

一个简单的方法是保持随机选择和删除套n节点，直到你发现了一组不增加图形组件数量：

remove.edges <- function(g, n) { 
    num.tries <- 0 
    while (TRUE) { 
    num.tries <- num.tries + 1 
    g2 <- delete.edges(g, E(g)[sample(seq_along(E(g)), n)]) 
    if (no.clusters(g2) == no.clusters(g)) { 
     print(paste("Total number of tries:", num.tries)) 
     return(g2) 
    } 
    } 
} 

让我们尝试一下用样品图表：

library(igraph) 
set.seed(144) 
g <- erdos.renyi.game(10, 0.4) 
g2 <- remove.edges(g, 5) 
# [1] "Total number of tries: 3" 

这可能是一个大的，稀疏图配上大n值非常低效的。在这种情况下，您可能需要在每次迭代时运行类似Tarjan's Bridge-Finding Algorithm的内容，并将您的随机选择限制为不成为桥梁。不幸的是，我无法在R中找到该算法的实现，因此您可能需要执行一些实现才能使其工作。

Answer 2

一种简单的技术是找到图中的一个周期，并从该循环中除去的边缘。要找到一个循环，我会先进行深度搜索，直到找到您之前在搜索中看到的节点。

例如，如果你是在节点x在执行DFS和您发现x的邻居节点y，那么如果x也已经在DFS树存在，你找到了一个循环。此时，您可以安全地移除此循环中的任何边缘，而不会成为桥梁。如果图形不是非常稀疏，这应该运行得非常快。

注意，在实践中，这DFS技术将往往只是类似于图形围绕一个随机游走，直到遇到一个以前看过节点。