我的教科书有一个问题,如下所示;假设我有一个最短的路径矩阵S
,可能如下所示:
还有一棵树T
,由最短路径矩阵S
(如最小生成树)构成的最短路径组成。
树具有以下属性; n - 1个边,所有节点相互连接。
然后,任务是通过矛盾来证明,如果条目S_{ij}
具有最小值,那么该条目必须是树T
中的边缘。我不太明白有什么证据可以证明。我认为它的方式是,如果我们假设T
不包含来自S
的最小元素,那么我们将在末尾有一个矛盾,因为将有一条路径大于用最小元素选择的路径。这对我来说似乎不是一个证据,即使它是,我也看不出如何概括证明。
由于T是树,因此每对节点之间只存在一条路径。如果节点i
和j
没有通过边连接,那么连接它们的路径必须至少有一个节点,称之为k
。比S_{ij}
(i
和j
之间的路径长度持有):
S_{ij} = S_{ik} + S_{kj} >= S_{ij} + S_{ij} = 2 * S_{ij}
这是一个矛盾。