1

我的问题：

令 G(V,E) 为全连接图，其中 V 是节点集，E 是链接集。如果生成树按字典顺序排序，则覆盖图中所有链接所需的最小生成树数量的上限（最坏情况）是多少？

例如，对于 |V|=4，因此 |E|=6，G(V,E) 包含以下 16 个生成树（按字典顺序）；请注意，以不同方式标记链接可能会产生不同顺序的生成树。

1 2 3

1 2 4

1 2 6

1 3 4

1 3 5

1 3 6

1 4 5

1 5 6

2 3 4

2 3 5

2 4 5

2 4 6

2 5 6

3 4 6

3 5 6

4 5 6

在这种情况下，覆盖图中所有链接所需的最小生成树数将是 5 棵生成树（{1 2 3}、{1 2 4 }、{1 2 6}、{1 3 4}、{ 1 3 5}）。所以所有的链接都包含在这 5 棵生成树中。

计算小图的生成树的数量很容易，但我对较大的图有问题，例如|V|>4。

是否有任何公式可以计算生成树的上限以覆盖图中的所有链接？

非常感谢

4

1 回答 1

0

任何 MST 中都有 V-1 条边，总共有 (V)(V-1)/2 条边。所以下限是上限（V/2）。

我认为这也是一个确切的界限。

您应该能够找到在最后一步之前不重用其他边缘的 MST 组合。考虑找到一个 MST，删除那些边，并仍然保持简化图连接，以便可以嵌入新的 MST，而不会破坏连接性。

于 2012-07-25T21:56:33.737 回答