最小生成树与最短路径树之间的差异

Question

这是一个消费税:

要么证明以下内容,要么给出一个反例:

(a)无向图的最小生成树中的一对顶点之间的路径是否必须是最短(最小权重)路径？

(b)假设图的最小生成树是唯一的.在无向图的最小生成树中,一对顶点之间的路径是否必须是最短(最小权重)路径？

我的回答是

(一个)

不,例如,对于图0,1,2,0-1是4,2-2是2,2-0是5,那么0-2的真正最短路径是5,但是mst是0-1-2 ,在mst,0-2是6

(b)中

我的问题进入了这个(b).

我不明白怎么whether the MST is unique会影响最短的路径.

首先,我的理解是,当边的权重不明显时,可能同时存在多个MST,对吧？

其次,即使MST是唯一的,上述(a)的答案仍然适用于(b),对吧？

Answer 1

那么让我们来看一个非常简单的图表:

(A)---2----(B)----2---(C)
 \                    /
  ---------3----------

此图的最小生成树包含两个边A-B和B-C.没有其他边缘组形成最小生成树.

但当然,从最短路径A来C是A-C,它不会在MST存在.

编辑

因此,回答(b)部分的答案是否定的,因为存在一条不存在于MST中的较短路径.

Answer 2

关于(a),我同意.

关于(b),对于某些图表,可能存在具有相同权重的更多最小生成树.考虑具有顶点a,b,c的圆C3; 权重a-> b = 1,b-> c = 2,a-> c = 2.该图有两个MST,{abc}和{cab}.

尽管如此,你的反例仍然存在,因为MST在那里是独一无二的.