设 G(V, E) 为无向连通有限图，权重函数为 w : E → R^+。令 T 为 G 的最小生成树。证明存在运行查找 T 的 Kruskal 算法（对于边的适当排序）。
答案：设T为G的最小生成树，设T_k为Kruskal算法在k次迭代后选择的边的集合。 我们将通过反证证明 Kruskal 算法选择的边形成 T 的子集。 为了矛盾起见，假设 Kruskal 算法没有找到 T 的子集。令 e 为 T 中 Kruskal 算法不包括的第一条边。
由于 T 是生成树，删除边 e 会将 T 断开为两个组件，例如 C1 和 C2。 克鲁斯卡尔算法第一次考虑边 e 时，它连接分量 C1 和 C2，因此它一定是在算法过程中的某个时刻选择的。 然而，Kruskal 算法始终选择连接两个不相交组件的最小权重边，因此它会在连接 C1 和 C2 的任何其他边之前选择边 e。 这与我们的假设相矛盾，即 e 是克鲁斯卡尔算法未选择的第一条边。因此，T 中的所有边都包含在 Kruskal 算法选择的边中。 由于 T 中的所有边都包含在 Kruskal 算法选择的边中，并且 Kruskal 算法构造了生成树，因此 Kruskal 算法构造了最小生成树 T。
因此，存在运行 Kruskal 算法，该算法可以使用权重函数 w 找到给定无向连通有限图 G 的最小生成树 T。
我认为这是不正确的。我很快就会评分。