前期需掌握内容：
6.4图的应用-最小生成树(建立交通网问题)
6.4.1概念回顾
生成树：所有顶点均由边连接在一起,但不存在回路的图。
- 一个图可以有许多棵不同的生成树
- 所有生成树具有以下共同特点
- 生成树的顶点个数与图的顶点个数相同;
- 生成树是图的极小连通子图,去掉一条边则非连通;
- 一个有n个顶点的连通图的生成树有n-1条边;
- 在生成树中再加一条边必然形成回路。
- 生成树中任意两个顶点间的路径是唯一的;
6.4.2最小生成树
给定一个无向网络,在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树。 
6.4.3最小生成树的典型用途
欲在n个城市间建立通信网,则n个城市应铺n-1条线路;
但因为每条线路都会有对应的经济成本,而n个城市最多有n(n-1)/2条线路,那么,如何选择n-1条线路,使总费用最少?
显然此连通网是一个生成树
6.4.4数学模型:
- 顶点一表示城市,有n个;
- 边表示线路,有n-1条;
- 边的权值一表示线路的经济代价;
- 连通网--表示n个城市间通信网。
6.4.5构造最小生成树Minimum Spanning Tree
MST性质
构造最小生成树的算法很多,其中多数算法都利用了MST的性质。
MST 性质:
设N = (V, E)是一个连通网,U是顶点集V的一个非空子集。
若边(u, v)是一条具有最小权值的边,其中u∈U, v∈V-U,则必存在一棵包含边(u, v)的最小生成树。
