我有一個玩具圖g，然后我
我需要繪制所有生成樹。例如，下一個 root = 5 的樹不會被創建：
題。為小隨機圖生成所有樹的可能方法是什么？
uj5u.com熱心網友回復：
首先，我想說，我下面的解決方案是一種蠻力方法，因此只適用于小尺寸的圖形，即沒有很多頂點或弧。
如果你有大型網路，你應該參考一些更高級的演算法，例如，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
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/351991.html