MST表示：最小生成树。
给出图g =（V，E）。将顶点任意划分为2个不相交的集合V1和V2。 令E1是V1中两个入射顶点的所有边 令E2是V2中两个入射顶点的所有边 设E3是在V1中有一个入射在V2中是一个入射的所有边
现在在子图（V1，E1）上构造一个MST M1，在子图（V2，E2）上构造一个MST M2。然后在连接M1和M2的E3中添加最低的权重边。这是在原始图g上构造MST的结果吗？
zhi686 回答：子图上的MST递归构造
我的回答是否。
考虑图形G：{顶点：{A，B，C，D}边：{AB = 1，BD = 10，DC = 3，AC = 2}}。当它分为V1 = {A，C} V2 = {B，D} E1 = {AC} E2 = {BD} E3 = {AB，CD}时，根据描述，MST为{AC，AB，BD }，而真正的MST是{AB，AC，CD}。
回想一下Kruskal算法：边缘按权重按升序排序，并且不会形成循环，MST中已经存在的边缘将被逐一添加。 MST是树，因此将选择| E | -1边（假定MST中没有孤立的顶点）。如果| E1 | 1，则当在整个图G上实施Kruskal算法时，E3中的多个边将被添加到MST。 MST由M1 M2和E3中最小的边构成，可能会丢失一些边。
此外，如果我们在整个图形G上实施Kruskal算法，则可能会添加多个E3中较小的边（我们称它们为E3'）。如果我们分别在V1 E1和V2 E2上实施Kruskal算法，则比E3’大的边将添加到M1，M2。并且只会添加E3（E3’）中的最小边。因此，第二个MST的总重量大于第一个MST，这不是真正的MST。
是否有单独建立MST的情况与在整个图表上建立MST的情况相同吗？
-
当E3仅具有一条边缘时：
当在整个图形G上实施Kruskal算法时，该边将被添加到MST，因为它不会与任何边形成循环。而且不会影响其他任何方面的决定。
-
当M1，M2都是没有隔离的连接树时 E3中的顶点和至少| E3 | -1个边是 E。
在整个图形上实施Kruskal算法时，E3中的最小边将添加到MST。它不会影响在其后添加的E1或E2中任何其他边上的决策。因为它不会与E1或E2中的任何边形成循环。并且不会添加E3中的其他边，因为它们是Kruskal算法中要考虑的最后一条边，它们将与MST中已经存在的边形成一个循环。