0

如果我应该证明或寻找反例,请提供任何提示,至少要知道该往哪个方向走......

考虑以下两张图:

G1 (V, E1)
G2 (V, E2)

和顶点的权重函数w: (E1 \untion E2) -> R

和的2 个最小生成树T1, T2G1G1

我们定义一个新图:G(V, E1 \untion E2)

T新图中总是有一个最小生成树G(使用相同的w函数)是真的吗,这样T 的所有边都来自T1T2


如果每个 T 都有一条不包含在 T1 或 T2 中的边 e,则该声明是错误的,现在在 G1 中,我们可以删除这条边 (e),T1 的问题就解决了。但是我也不能从 G2 中删除边 e,这意味着我必须接受它并且声明是正确的,我错了吗?

注:无需详细解答,只求知道什么是对的,自己深思熟虑。

4

0 回答 0