我遇到了基于生成树的问题,即:
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]
我们所说的边缘不相交的生成树是什么意思?这是否意味着不同的树,以至于它们在所有树中都没有相同的边缘?请解释,然后它的答案应该是什么?
是。边缘不相交的生成树是没有共同边缘的生成树。边缘不相交的生成树的最大数量也称为“生成树打包数量或STP数量”。有关此的更多详细信息,可以查看本文http://www.sciencedirect.com/science/article/pii/S0012365X00000662#。
当同一图的两个生成树没有共同的边时,则称为边不相交的生成树(EDST)。 floor(n / 2)是具有n个顶点的EDST的数量。