如何生成并绘制所有的生成树？

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的树没有被创建：

问题。 有没有一种可能的方法可以为小型随机图生成所有树？

- Nick

---

你从哪里得到11棵树？你循环从1到n = 5，所以最终得到5棵树。你有5个顶点，拉普拉斯矩阵的维度为5 x 5，并且有5个根节点用于广度优先搜索。 - Maurits Evers

@MauritsEvers，为了找到给定图中的总生成树数量，我计算了拉普拉斯矩阵中(1,1)元素的余子式'det(lap_mat[-1,-1])'。这个数字等同于图中的总生成树数量。 - Nick

我认为我们彼此之间存在误解。您循环遍历所有顶点，由于您有5个顶点，因此会生成5个图形，而不是11个。这是您的玩具图形设计所致，我不确定您想要做什么。我的意思是，根据XY问题，问题似乎并不是绘图，而是其他问题。也许您正在询问如何计算所有生成树？ - Maurits Evers

@Szabolcs 是的，现在问题更清晰了。最初并不明显 OP 的困惑是如何计算所有生成树（ST）。有关生成 ST 的算法的评论是Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review。许多方法使用 BFS 生成初始 ST；然后可以从此初始 ST 生成所有其他 ST。我建议看一下这篇评论。在 R 中实现其中一种方法应该不会太难。 - Maurits Evers

我提出了一个功能请求：https://github.com/igraph/igraph/issues/1827 @Nick 如果您能评论一下您的动机，这将有助于优先处理此问题。 - Szabolcs

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

- ThomasIsCoding

Answer 2

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

1. For the original graph G, we have |V(G)| = 5, |E(G)| = 6

   

2. A spanning tree T of graph G will have exactly V(G)-1=4 vertices.

3. But that does not mean that we can arbitrarily select and delete any 2 edges from G to obtain a spanning tree T. For example, if we choose to remove the edges (1,5) and (2,5), we shall obtain the following disconnected graph, which is not a tree:

   

4. Let's find the cycles in the graph starting from vertex 1. Note that since there is an edge from vertex 1 to 2, finding all possible paths (of length >1) starting from 1 and ending on vertex 2. Now, if we extend each of the paths by adding the edge (2,1) in the end, we shall find all possible cycles in the simple graph G, starting/ending on vertex 1, as it's done in the next code block:

   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='|'))    
         }
      } 
   }
   

   Two of the cycles found in the graph are shown below:

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

5. Now select one edge from each cycle to delete and generate a unique spanning tree:

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

- Sandipan Dey

---

你的解决方案非常有趣，但是能否在通用情况下分享你的解决方案呢？例如，当三角形1-2-5不存在时。 - Nick

@Nick 如果图中存在多个环，通常需要从每个环中移除一条边来生成生成树。如果我们有n个不相交的环，其中第i个环有m_i条边，则移除边的方式有m_1.m_2...m_n种，最终得到该数量的生成树。如果这些环共享边缘，则需要单独处理这些边缘。例如，给定的图包含3条边和4条边的两个环，并且它们之间有一条公共边(1,2)，因此我们将有3 * 4-1 = 11个生成树。 - Sandipan Dey

如果图形中有一个包含m个节点的单一循环，我们可以恰好拥有m个生成树，因为有m种方法可以从循环中删除单个边缘并使图形无环。 - Sandipan Dey

当三角形1-2-5不存在时，图仅包含长度为4的一个循环，因此可以从循环中以4种方式删除边以创建4个生成树。 - Sandipan Dey