负权重边
Negative weight edges
全题：论证如果图的所有边权重都是正的，那么连接所有顶点且总权重最小的边的任何子集一定是一棵树。举个例子说明，如果我们允许某些权重为非正数，则不会得出相同的结论。
我的回答：由于边连接所有的顶点，所以它一定是一棵树。在图形中，您可以删除其中一条边并仍然连接所有顶点。此外，图形中可以允许负边（例如 Prim 和 Kruskal 的算法）。
如果对此有明确的答案，请告诉我，并向我解释你是如何得出结论的。我对这个问题有点迷茫。
首先，树是一种图形。所以“在图中，您可以删除其中一条边并仍然连接所有顶点”是不正确的。树是没有循环的图 - 即，任何两个节点之间只有一条路径。
负权重通常可以存在于树或图中。
解决这个问题的方法是证明如果你有一个连接所有组件的图，但不是树，那么它也不是最小权重的（即，有一些其他的图做同样的事情，总权重较低。）这个结论只有在图只包含正边时才成立，所以你还应该提供一个反例 - 一个不是树的图，它是最小权重的，并且是完全连接的.
对于非负权重，添加一条边从一个节点遍历到另一个节点总是会导致权重增加，因此对于最小权重，您总是要避免这种情况。
如果允许负权重，添加边可能会导致权重降低。如果你有一个整体负权重的循环，最小权重要求你无限地停留在那个循环中（导致整个路径的无限负权重）。
全题：论证如果图的所有边权重都是正的，那么连接所有顶点且总权重最小的边的任何子集一定是一棵树。举个例子说明，如果我们允许某些权重为非正数，则不会得出相同的结论。
我的回答：由于边连接所有的顶点，所以它一定是一棵树。在图形中，您可以删除其中一条边并仍然连接所有顶点。此外，图形中可以允许负边（例如 Prim 和 Kruskal 的算法）。
如果对此有明确的答案，请告诉我，并向我解释你是如何得出结论的。我对这个问题有点迷茫。
首先，树是一种图形。所以“在图中，您可以删除其中一条边并仍然连接所有顶点”是不正确的。树是没有循环的图 - 即，任何两个节点之间只有一条路径。
负权重通常可以存在于树或图中。
解决这个问题的方法是证明如果你有一个连接所有组件的图，但不是树，那么它也不是最小权重的（即，有一些其他的图做同样的事情，总权重较低。）这个结论只有在图只包含正边时才成立，所以你还应该提供一个反例 - 一个不是树的图，它是最小权重的，并且是完全连接的.
对于非负权重，添加一条边从一个节点遍历到另一个节点总是会导致权重增加，因此对于最小权重，您总是要避免这种情况。
如果允许负权重，添加边可能会导致权重降低。如果你有一个整体负权重的循环，最小权重要求你无限地停留在那个循环中（导致整个路径的无限负权重）。