最小生成树（Kruskal和Prim）的问题求解

最小生成树（MST）是GATE的一个重要研究课题。因此，我们将讨论如何基于MST解决不同类型的问题。在理解本文之前，您应该了解MST及其算法的基础知识( 克鲁斯卡尔算法 和 普里姆算法 ).

第一类。基于MST的概念性问题- MST有一些重要的特性，根据这些特性可以提出以下概念性问题：

• 具有n个节点的MST中的边数为（n-1）。
• 图的MST的权重总是唯一的。但是，可能有不同的方法获得此权重（如果有具有相同权重的边）。
• MST的权重是MST中边的权重之和。
• 对于具有n个顶点的MST，两个顶点之间的最大路径长度为（n-1）。
• 在MST中，从一个顶点到另一个顶点只有一条路径。
• 从MST中删除任何边都会断开图形的连接。
• 对于具有不同权重的边的图，MST是唯一的。

Que–1。 设G是一个边权不同的无向连通图。设emax为权重最大的边，emin为权重最小的边。以下哪项陈述是错误的？（门CS 2000） （A） G的每个最小生成树都必须包含emin。 （B） 如果emax在最小生成树中，那么它的删除必须断开G （C） 没有最小生成树包含emax （D） G有唯一的最小生成树

解决方案： 由于边权重是唯一的，因此只有一个边emin，将添加到MST，因此选项（A）始终为真。 由于生成树的边数最少，删除任何边都会断开图的连接。因此，选项（B）也是正确的。 由于所有边权重都是不同的，G将有一个唯一的最小生成树。因此，选项（D）是正确的。 选项C为假，因为如果其他权重较小的边正在创建循环，并且添加emax之前的边数小于（n-1），emax可以是MST的一部分。

类型2。如何在给定图的情况下求最小生成树的权重—— 这是基于MST的最简单的问题类型。要用kruskal算法解决这个问题，

• 按权重的非降序排列边。
• 如果没有创建循环，则逐个添加边，直到得到n-1个边，其中n是图中的节点数。

Que–2。 考虑具有顶点集{ 0, 1, 2，3, 4 }的完全无向图。下面矩阵W中的条目Wij是边{i，j}的权重。在这个图中，生成树T的最小可能权重是多少，使得顶点0是树T中的叶节点？（门CS 2010） （A） 七, （B） 八, （C） 九, （D） 十

解决方案： 在具有5个顶点（v1到v5）的图的邻接矩阵中，按非降序排列的边是：

(v1,v2), (v1,v4), (v4,v5), (v3,v5), (v1,v5), 
(v2,v4), (v3,v4), (v1,v3), (v2,v5), (v2,v3) 

如上所述，顶点v1是一个叶节点，它应该只有一条边与之关联。因此，我们将最终考虑它。考虑到顶点v2到v5，非递减顺序的边是：

(v4,v5), (v3,v5), (v2,v4), (v3,v4), (v2,v5), (v2,v3)

添加前三条边（v4，v5）、（v3，v5）、（v2，v4），不会创建循环。此外，我们还可以使用edge（v1，v2）将v1连接到v2。总重量是这4条边的重量之和，即10。

类型3。对于给定的图，使用Kruskal算法可以得到多少最小生成树——

• 如果所有边的权重都不同，则最小生成树是唯一的。
• 如果两个边具有相同的权重，那么我们必须考虑两种可能性并找到可能的最小生成树。

Que–3。 下面加权图的不同最小生成树的数量为_________________ （A） 四, （B） 五, （C） 六, （D） 七,

解决方案： 有5条边的权重为1，将它们全部添加到MST中不会创建循环。 由于图有9个顶点，因此我们需要总共8条边，其中5条已经添加。在剩下的3条边中，有一条边是固定的，用f表示。

对于剩余的两条边，一条从c、d或e中选择，另一条从a或b中选择。剩余的黑色边将始终创建循环，因此不考虑它们。所以，可能的MST是3*2=6。

类型4。在给定的序列中，哪一个不是使用Kruskal算法添加到MST的边序列—— 要解决这类问题，请尝试找出Kruskal可以生成的边序列。不匹配的序列将是答案。

Que–4。 考虑下面的图表： 以下哪一项不是使用Kruskal算法添加到最小生成树的边序列？（GATE-CS-2009） （A） （b，e）、（e，f）、（A，c）、（b，c）、（f，g）、（c，d） （B） （B，e）、（e，f）、（a，c）、（f，g）、（B，c）、（c，d） （C） （b，e）、（a，C）、（e，f）、（b，C）、（f，g）、（C，d） （D） （b，e）、（e，f）、（b，c）、（a，c）、（f，g）、（c，D）

解决方案： Kruskal算法按权重的非降序添加边，因此，我们首先按权重的非降序对边进行排序，如下所示：

(b,e), (e,f), (a,c), (b,c), (f,g), (a,b), (e,g), (c,d), (b,d), (e,d), (d,f).

首先，它将在MST中添加（b，e）。然后，它会加上（e，f）和（a，c）（或者（e，f）后跟（a，c），或者反之亦然），因为两者的权重相同，加上它们不会产生循环。 然而，在选项（D）中，（b，c）在添加（a，c）之前已添加到MST中。所以它不可能是Kruskal算法产生的序列。