最小生成树和最短路径树的区别

2018-06-12 07:47:21

这是一个消费税：

要么证明以下内容，要么给出一个反例：

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

（b）假设图的最小生成树是唯一的。无向图的最小生成树中的一对顶点之间的路径是否必须是最短（最小权重）路径？

我的答案是

（一个）

否，例如，对于图0,1,2,0-1是4,1-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），对吗？

关于（a），我同意。

关于（b），对于一些图，可能会有更多的具有相同权重的最小生成树。考虑一个顶点为a，b，c的圆C3; 权重a-> b = 1，b-> c = 2，a-> c = 2。此图有两个MST，{abc}和{cab}。

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

所以让我们看看一个非常简单的图表：

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

该图的最小生成树由两个边AB和BC 。没有其他边形成最小生成树。

但是，当然，从A到C的最短路径是AC ，这在MST中不存在。

编辑

因此，回答（b）部分的答案是否定的，因为存在不在MST中的较短路径。

不是与起始节点相关的MST？
然后他试图从MST开始节点获得最短路径。因此，是的，最短路径由MS从A开始给出！

链接地址: http://www.djcxy.com/p/35261.html