树木边缘矛盾的证明

问题描述 投票:2回答:1

我的教科书有一个问题,如下所示;假设我有一个最短的路径矩阵S,可能如下所示:

enter image description here

还有一棵树T,由最短路径矩阵S(如最小生成树)构成的最短路径组成。

树具有以下属性; n - 1个边,所有节点相互连接。

然后,任务是通过矛盾来证明,如果条目S_{ij}具有最小值,那么该条目必须是树T中的边缘。我不太明白有什么证据可以证明。我认为它的方式是,如果我们假设T不包含来自S的最小元素,那么我们将在末尾有一个矛盾,因为将有一条路径大于用最小元素选择的路径。这对我来说似乎不是一个证据,即使它是,我也看不出如何概括证明。

algorithm graph shortest-path proof minimum-spanning-tree
1个回答
0
投票

由于T是树,因此每对节点之间只存在一条路径。如果节点ij没有通过边连接,那么连接它们的路径必须至少有一个节点,称之为k。比S_{ij}ij之间的路径长度持有):

S_{ij} = S_{ik} + S_{kj} >= S_{ij} + S_{ij} = 2 * S_{ij}

这是一个矛盾。

© www.soinside.com 2019 - 2024. All rights reserved.