最小生成树的概念

一、最小生成树的概念

引例 （管道铺设）某煤气公司准备在几个社区间铺设煤气管道，现已测得几个小区间的距离，如图9-19所示.请你设计一个管道铺设方案，使铺设成本最低.

要使铺设成本最低，必须使管道的总长度最短，同时任意两个小区间必须有一条管道而且只需有一条管道连接，因此考虑问题时，要把图9-19中的某些边去掉，使剩下的边满足：（1）任意两点间能找到一条路而且只能找到一条路；（2）这些边的权数之和是最小的，也就是说，去掉原图中某些边后，剩下的图必须是一个权数和最小的没有圈的连通图.

一般我们称：

不含圈的连通图为树；

任意一个连通图去掉一些边后形成的树，称为原图的生成树；

在图的生成树中，权数之和最小的生成树称为连通图的最小生成树.

例1 在如图9-20所示的三个图中，哪些是树，哪些不是树？

解 在图9-20（a），图9-20（b）中不含有圈，而且都是连通图，所以图9-20（a），图9-20（b）都是树；但图9-20（c）则不是树，因为其中含有圈v1→v2→v4→v3→v1.

例2 试找出图9-21的两棵生成树.

解 根据生成树的定义，就是要去掉图中的一些边，使图中不再含有圈，同时仍保持图的连通性，因此可得到图9-21的两棵生成树，如图9-22和图9-23所示.

试找出图9-21更多的生成树.

根据前面的论述，我们可得到如下重要结论：

（1）树中任意两顶点之间至多只有一条边；

（2）树中边数比顶点数少1；

（3）树中任意去掉一条边，就变为不连通图，因此，它是边数最少的连通图；

（4）树中任意添一条边，就会构成一个圈，因此它是边数最多的无圈连通图.

在讨论实际问题时，往往需要找连通图的最小生成树.下面我们介绍连通图最小成

树的两种求法.