极小连通图

1. 一个连通图的生成树是该连通图的的极小连通子图。（同一个连通图可以有不同的生成树，所以生成树不是唯一的）（极小连通子图只存在于连通图中）
2. 用边把极小连通子图中所有节点给连起来，若有n个节点，则有n-1条边。如下图生成树有6个节点，有5条边。
3. 之所以称为极小是因为此时如果删除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。
4. 如果在生成树上添加一条边，一定会构成一个环。

也就是说只要能连通图的所有顶点而又不产生回路的任何子图都是它的生成树。