边缘不相交生成树

Question

我遇到了一个基于生成树的问题，即：

what is the upper bound on the number of edge disjoint spanning trees in a
complete graph of n vertices?
(a) n      (b) n-1
(c) [n/2]  (d) [n/3]

边不相交生成树是什么意思？这是否意味着不同的树，以至于它们在所有树中没有任何相同的边缘？因为不相交意味着没有什么共同点。请解释一下，那么它的答案应该是什么？

Answer 1

是的。边不相交生成树是没有任何共同边的生成树。边不相交生成树的最大数量也称为"生成树包装编号或 STP 编号"。有关此内容的更多详细信息，您可以查看本文 http://www.sciencedirect.com/science/article/pii/S0012365X00000662#。

Answer 2

当同一图的两个生成树没有任何共同的边时，它被称为边不相交生成树（EDST）。floor（n/2） 是 n 个顶点可能出现的 EDST 数量。