Question

关于最小生成树的说法正确的是

Answer 1

下列关于最小生成树的叙述中，正确的是 

Ⅰ．最小生成树的代价唯一 

Ⅱ．权值最小的边一定会出现在所有的最小生成树中

 Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同

 Ⅳ．使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同

 A．仅Ⅰ B．仅Ⅱ C．仅Ⅰ、Ⅲ D．仅Ⅱ、Ⅳ

正确答案A

生成树的定义

一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。

生成树的属性

一个连通图可以有多个生成树；

一个连通图的所有生成树都包含相同的顶点个数和边数；

生成树当中不存在环；

移除生成树中的任意一条边都会导致图的不连通， 生成树的边最少特性；

在生成树中添加一条边会构成环。

对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边；

对于包含n个顶点的无向完全图最多包含 nn−2 颗生成树。

最小生成树

所谓一个 带权图 的最小生成树，就是原图中边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。