离散数学 第四篇 图论03 树

离散数学

树的定义、性质

叶：度数为1的结点
森林：每个联通分支都是树的无向图

树没有环和平行边，一定是简单图
任何非平凡树都没有度数为0的结点

树是边数最多的无回路图
是边数最少的连通图

任意非平凡树至少有两片叶

无向树的等价定义

设无向图$G=<V,E>,|V|=n,|E|=m$

生成树

树枝生成树中的边
弦原图中有的，却不在生成树中的边
生成树的补弦的集合

图G存在生成树的充要条件

G是连通的

求生成树的算法

1、破圈法
2、避圈法
3、广度优先算法

最小生成树

生成树的权：每个树枝的权之和

求最小生成树的算法

1、Kruskal算法
2、Prim算法