r - 如何生成和绘制所有生成树？

Question

我有一个玩具图g，然后我通过拉普拉斯算子的辅因子找到了生成树的数量。数字是 11。

library(igraph)
set.seed(2)
n <- 5   #  n=5
m <- 6   #  m=6
g <- erdos.renyi.game(n, p.or.m=m, type="gnm" , directed=FALSE, loops=FALSE)

lap_mat <- laplacian_matrix(g)   
print(paste("number of spanning trees by cofactor = ", det(lap_mat[-1,-1])))
# 11

我有n=5顶点，我绘制了原始图：

par(mfrow=c(2, 3))
layout <- layout.fruchterman.reingold(g)
plot(g, main="Original graph", vertex.size = 40, layout = layout)

graph.bfs()然后使用函数创建了 5 个生成树：

for (i in 1:n) {
  r <- graph.bfs(g, root=i, order=TRUE, father=TRUE)
  h <- graph(rbind(r$order, r$father[r$order, na_ok = TRUE])[, -1], directed=FALSE)
  plot(h, main=paste("Spanning tree for root=", i), vertex.size = 40, layout = layout)
}

我需要绘制所有生成树。例如，不创建根 = 5 的下一棵树：

问题。为小型随机图生成所有树的可能方法是什么？

score 2 · Accepted Answer

首先，我想说，我下面的解决方案是一种蛮力方法，因此只适用于小尺寸的图，即没有很多顶点或弧。

如果你有大型网络，你应该参考一些更高级的算法，例如，https://link.springer.com/article/10.1007/s40747-018-0079-7

由于您有 6 条弧和 5 个顶点，因此您只需从 6 条弧中删除 2 条即可找到生成树。会有combn(6,2)选项，你可以一一删除那些边组合，检查是否还有生成树

Filter(
  function(x) length(decompose(x)) == 1,
  combn(
    ecount(g),
    ecount(g) - vcount(g) + 1,
    FUN = function(x) delete.edges(g, E(g)[x]),
    simplify = FALSE
  )
)

这给出了所有 11 棵生成树

[[1]]
IGRAPH 9692f3d U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9692f3d:
[1] 2--4 3--4 1--5 2--5

[[2]]
IGRAPH 969368e U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 969368e:
[1] 1--3 3--4 1--5 2--5

[[3]]
IGRAPH 969368e U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 969368e:
[1] 1--3 2--4 1--5 2--5

[[4]]
IGRAPH 96938fa U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 96938fa:
[1] 1--3 2--4 3--4 2--5

[[5]]
IGRAPH 96938fa U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 96938fa:
[1] 1--3 2--4 3--4 1--5

[[6]]
IGRAPH 9693ded U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9693ded:
[1] 1--2 2--4 3--4 2--5

[[7]]
IGRAPH 969404b U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 969404b:
[1] 1--2 2--4 3--4 1--5

[[8]]
IGRAPH 96942b7 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 96942b7:
[1] 1--2 1--3 3--4 2--5

[[9]]
IGRAPH 9694527 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9694527:
[1] 1--2 1--3 3--4 1--5

[[10]]
IGRAPH 9694527 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9694527:
[1] 1--2 1--3 2--4 2--5

[[11]]
IGRAPH 9694797 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9694797:
[1] 1--2 1--3 2--4 1--5

score 1 · Accepted Answer

首先让我们注意以下几点：

对于原始图 G，我们有 |V(G)| = 5, |E(G)| = 6
图 G 的生成树 T 将恰好有 V(G)-1=4 个顶点。
但这并不意味着我们可以从 G 中任意选择和删除任意 2 条边来得到生成树 T。例如，如果我们选择删除边 (1,5) 和 (2,5)，我们将得到跟随断开的图，它不是一棵树：

让我们在图中找到从顶点 1 开始的循环。请注意，由于从顶点 1 到 2 有一条边，因此找到从 1 开始到顶点 2 结束的所有可能路径（长度 >1）。现在，如果我们扩展每个通过在最后添加边 (2,1) 来计算路径，我们将在简单图 G 中找到所有可能的循环，从顶点 1 开始/结束，就像在下一个代码块中所做的那样：

cycle_edges <- c()
C <- list() # all possible cycles staring / ending on vertex 1
for (path in all_simple_paths(g, 1, 2, mode="out")) {
   pn <- length(path)
   if (pn > 2) { # not a single edge
      cycle <- c(as.vector(path), 1)
      name <- paste(cycle, collapse='')
      C[[name]] <- c()
      for (i in 1:pn) {
         C[[name]] <- c(C[[name]], paste(cycle[i], cycle[i+1], sep='|'))    
      }
   } 
}

图中的两个循环如下所示：

C
# $`13421`
# [1] "1|3" "3|4" "4|2" "2|1"    
# $`1521`
# [1] "1|5" "5|2" "2|1"

现在从每个循环中选择一个边来删除并生成一个唯一的生成树：

par(mfrow=c(4,3))
count <- 1
for (e1 in C[[1]]) {
   for (e2 in C[[2]]) {
      if (e1 != e2) { # make sure not to remove same edge twice
         g1 <- g %>% delete_edges(c(e1, e2))
         plot(g1, main=paste("spanning tree", count), layout = layout)
         count <- count + 1
       }
    }
 }

r - 如何生成和绘制所有生成树？

2 回答 2

Related

Reference