How to generate and plot all spanning trees?-CodePudding

I have a toy graph g, then I have found

I need to plot all spanning trees. For example, the next tree with root = 5 is not created:

Question. What is a possible way to generate all trees for small random graph?

CodePudding user response：

First of all, I would say, my solution below is a brute-force method, thus only working well for graphs of small size, i.e., not many vertices or arcs.

If you have large networks, you should refer to some more advanced algorithms, e.g., https://link.springer.com/article/10.1007/s40747-018-0079-7

Since you have 6 arcs and 5 vertices, you only need to remove 2 arcs out of 6 to find the spanning tree. There would be combn(6,2) options, and you can delete those edge combinations one by one to check if a spanning tree remains

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

which gives all 11 spanning trees

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