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

Question

我有一个玩具图 g，然后我找到了 the number of spanning trees by cofactor of the Laplacian .数字是 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() function 创建了 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)
}

我需要绘制所有生成树。例如，下一个 root = 5 的树不会被创建:

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

Answer 1

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

如果你有大型网络，你应该引用一些更高级的算法，例如，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