algorithm - 树中边的反证法

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}

这是矛盾的。