对或错：对于无向图，对于每个顶点，其具有最小权重的边在最小生成树中
True or False: For an undirected graph, for every vertex, its edge with minimum weight is in a minimum spanning tree
我认为这是真的。考虑到Prim的算法，顶点的最小边要么已经在树中，要么最终会被选中。
我也尝试了很多图表，它们似乎都是正确的。
如果这个说法是假的，有人能给我一个反例吗？
谢谢。
你的证明快完成了。
证明1：Prim的算法可以从任意顶点开始，并且会立即select起始顶点的最小边，或者可以select任何最小边如果有平局。
证明 2：在 Kruskal 算法中，每个顶点的最小边之一将是第一个连接该顶点的边，如果有平局，则它可以是其中任何一个，具体取决于初始排序。
证明 2 实际上证明了一个更强的定理：每个最小生成树都将包含 每个 个顶点的最小边。
我认为这是真的。考虑到Prim的算法，顶点的最小边要么已经在树中，要么最终会被选中。
我也尝试了很多图表，它们似乎都是正确的。
如果这个说法是假的，有人能给我一个反例吗？
谢谢。
你的证明快完成了。
证明1：Prim的算法可以从任意顶点开始，并且会立即select起始顶点的最小边，或者可以select任何最小边如果有平局。
证明 2：在 Kruskal 算法中，每个顶点的最小边之一将是第一个连接该顶点的边，如果有平局，则它可以是其中任何一个，具体取决于初始排序。
证明 2 实际上证明了一个更强的定理：每个最小生成树都将包含 每个 个顶点的最小边。