关于最小生成树的算法证明，我的答案正确吗？

Question

这是问题，我承认这是作业题，我不是在寻找答案，而是我只想知道我是否在朝着正确的方向前进，如果我不正确，请指出我正确的方向方向。

问题:证明如果加权图中没有两条边具有相同的权重，则入射到顶点 v 的权重最小的边被包含在每个最小生成树 (MST) 中。

我的回答:给定一个顶点 (V) 和一个加权图 (G)，我们注意到 ∃(存在)和与 V 相关联的边 (E)，即加权最小的边。请注意，我们将有两个不同的顶点，它们将具有相同的最小权重边。这对我们来说不是问题，如果其中一个顶点包含在最小生成树中，另一个就会到。如果我们开始构建 MST，在一个实例中，最小加权边必须包含在 MST 中，因为必须包含具有最小边的一个(或两个)顶点以获得 MST(因为 a 的定义MST 声明我们必须找到从根到所有顶点的最小路径)

我不太确定我的回答是否有效，你认为我如何证明它就足够了吗？

Answer 1

你的证明是无效的，原因是你的证明中有很多不精确的陈述，还有一些谎言。例如你说“MST 的定义是我们必须找到从根到所有顶点的最小路径”，而 MST 的定义是它是最小权重的生成树。

您使用“具有最少边的顶点”必须在 MST 中这一事实，但很难看出相关性，因为 每个 顶点都出现在 MST 中(根据生成的定义树)。

写证明的技巧是用你的语言非常精确，并根据你证明的事情做出逻辑步骤(或者如果你正在应用一个众所周知的定理，那么一个很好的引用)。了解并使用您正在使用的行话的确切定义非常重要(这里可能是“最小”、“跨越”和“树”)。

对于这个证明，正如 Keith 所说，您想尝试反证法。也就是说，如果存在不包含最小权重边的生成树，那么您可以找到权重较低的生成树。也许首先证明一棵生成树必须有多少条边，以及图中是否每棵具有该条边数的树都必须是生成树，这可能会有所帮助。您应该清楚树的定义是什么，因为在证明中需要它:您将采用不包含边缘的生成树，以某种方式修改它，并表明它具有较低的权重并且仍然是生成树。