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

Question

我正在使用igraph R 中的包。我有一个连通图 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 中找到该算法的实现，因此您可能需要执行一些实现才能使其正常工作。