Mag*_*gam 4 math tree proof minimum-spanning-tree
图形可以有许多不同的最小生成树(MST),但不同的MST可以有不同的边缘权重集吗？例如,如果MST使用边缘权重{2,3,4,5},则每个其他MST是否必须具有边缘权重{2,3,4,5},或者某些其他MST是否可以使用不同的权重集合？
给我这个想法的是,只有当边的权重不同时,图才没有唯一的MST.
套装必须具有相同的重量.这是一个简单的证明:假设他们没有.让T1和T2为具有不同多边缘权重的图G的MST.
将这些边缘按重量的升序排序.由于两个权重的多重不同,请查看权重首先发散的位置.在T1或T2中最终会有一些最小权重w*(假设WLOG,它在T1中),其中T1和T2具有相同数量的所有权重小于w*的边缘,但T1具有更多权重w的边缘*比T2.直观地,权重w*的边缘是T1"超前"T2的地方.
现在,考虑T1中权重w*的边集; 我们称他们为W*.考虑将任何这些边添加到T2时会发生什么.每次我们这样做,它将在T2中关闭一个周期.注意,新添加的边e不能是该周期的最大权重边; 如果是,那么通过循环属性我们可以保证e不会出现在任何MST中,但我们知道它在一个(即T1)中.因此,在重量大于或等于w*的循环中必须存在一些边缘.
如果其中一条边的权重严格大于w*,那么我们可以通过删除该边来降低T2的成本.但这是不可能的,因为我们知道T2是MST.
因此,我们知道循环中存在一些权重等于w*的其他边缘.如果这些边缘中的任何一条不在T1中,则选择任何一条边并将其移除.请注意,我们刚刚在T2中交换了一条边,用于T1中的等权边.因为T1中的权重w*比T2中更多,所以我们不能永远这样做,最终我们将遇到周期关闭并且所有最大权重边缘都是重量w*的情况从T1.
那么在这种情况下会发生什么？好吧,想想当我们添加触发此问题的边缘时关闭的周期C. 我们将展示在这种情况下,T1不能是MST,与我们最初的假设相矛盾,并给出了我们想要的结果.
设C*是C中边缘的集合,其成本小于w*.按重量顺序处理这些边缘,一次将它们添加到T1.每次我们这样做,我们都会关闭一个周期.该循环中的最大权重边缘不能是我们从T2添加的边缘(因为否则边缘不应该首先在T2中的循环属性).因此,最大权重边缘的权重要大于T2的边缘(在这种情况下我们删除它,与T1是MST相矛盾)或者它具有相同的权重.最终,我们最终转换T1,使其具有与T2相同的成本小于w*的边缘.但这是一个问题,因为在那一点上我们知道我们会在T1中产生周期C,这意味着T1不是MST.这给了我们所需要的矛盾.
希望这可以帮助!