如果我应该证明或寻找反例,请提供任何提示,至少要知道该往哪个方向走......
考虑以下两张图:
G1 (V, E1)
G2 (V, E2)
和顶点的权重函数w: (E1 \untion E2) -> R
和的2 个最小生成树T1, T2
。G1
G1
我们定义一个新图:G(V, E1 \untion E2)
说T
新图中总是有一个最小生成树G
(使用相同的w
函数)是真的吗,这样T 的所有边都来自T1
或T2
?
如果每个 T 都有一条不包含在 T1 或 T2 中的边 e,则该声明是错误的,现在在 G1 中,我们可以删除这条边 (e),T1 的问题就解决了。但是我也不能从 G2 中删除边 e,这意味着我必须接受它并且声明是正确的,我错了吗?
注:无需详细解答,只求知道什么是对的,自己深思熟虑。