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

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

Answer 2

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

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

让我们从顶点1开始寻找图中的循环。注意，由于从顶点1到2有一条边，所以找到从1开始到结束的所有可能路径（长度>1）在顶点 2 上。现在，如果我们通过在末尾添加边 (2,1) 来扩展每条路径，我们将在顶点 1 上的简单图 G starting/ending 中找到所有可能的循环，因为它已经完成在下一个代码块中：

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"

现在select从每个循环删除一条边并生成唯一的生成树：

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
       }
    }
 }

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

How to generate and plot all spanning trees?

r

algorithm

graph-theory

igraph

spanning-tree