第二章 树

2.1 概念

• 不包含圈的图称为无圈图，连通的无圈图称为树
• 一个无圈图称为森林，树也是森林
  • 树和森林都是简单图
  • 树和森林都是偶图
• 平凡图称为平凡树
• 根树：一棵非平凡的有向树\(T\)，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点
• 完全\(m\)元树：对于根树\(T\)，若每个分支点至多\(m\)个儿子，称该根树为\(m\)元根树；若每个分支点恰有\(m\)个儿子，称它为完全\(m\)元树

2.2 性质

• 每棵非平凡树至少有两片树叶
• 图\(G\)是树当且仅当\(G\)中任意两点都被唯一的路连接
• 设\(T\)是\((n, m)\)树，则\(m=n-1\)
• 具有\(k\)个分支的森林有\(n-k\)条边
• 每个\(n\)阶连通图的边数至少为\(n-1\)
• 任意树\(T\)的两个不邻接顶点之间添加一条边后，可以得到唯一圈
• 设\(s=\{d_1,d_2,...,d_n \}\)是\(n\)个正整数序列，它们满足：\(d_1\geq d_2\geq ...\geq d_n,\sum d_i=2(n-1)\)，则存在一颗树\(T\)，其度序列为\(S\)

2.3 最小生成树

在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树

• Kruskal算法：
  1. 选择边\(e_1\),使得其权值最小
  2. 若已经选定边\(e_1,e_2,...,e_k\)，则从\(E-\{e_1,e_2,...,e_k \}\)中选择边\(e_{k+1}\)使得：
     • \(G(e_1,e_2,...,e_{k+1})\)为无圈图
     • \(e_{k+1}\)的权值\(w(e_{k+1})\)尽可能小
  3. 当2不能进行时，停止
• 管梅谷的破圈法