树木边缘矛盾的证明

Question

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

还有一棵树T，由最短路径矩阵S（如最小生成树）构成的最短路径组成。

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

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

Answer 1

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

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

这是一个矛盾。