第2 编图论第5 章.ppt

5.1 树的定义与性质 5.1.2 生成树及其应用 若连通图G有n个结点，m条边，要确定G的一棵生成树，必须删去G的m－(n－1)条边。 定义4 设T是n阶m条边的无向连通图G的一棵树, e1,e2,…,en-1为Ｔ的树枝，Sj为Ｇ的只含树枝ej的割集，则称Ｓj为Ｇ的对应生成树Ｔ的由树枝ej产生的基本割集，称{S1,S2,…,Sn-1}为对应Ｔ的基本割集系统，称n-1为割集秩,记为η(G)。 例1 n=4,m=5, 红线表示一棵生成树。树枝为:(v1,v2), (v1,v3), (v1,v4)　　 定理3 T是连通图G的生成树，则1) G的任何边割集与T至少有一条公共边。2) G的任何回路与T的补至少有一条公共边。 求最小生成树的克鲁斯克尔算法（避圈法）：1. 在G中选取最小权的边ei，置i = 1；2. 当i = n－1时结束，否则转3；3. 设已选择边为T={e1,e2,...,ei}, 在E－T中选取ei+1, 使T?ei+1无回路，且ei+1具有最小的权；4. 置i = i + 1，转2。 定义9 在根树T中，任一结点v及其所有后代导出的子图T称为T的以v为树根的子树。 定理5 若正则二叉树有n个分支点，且各分支点的层数之和为 I，各树叶的层数之和为E，则 E = I + 2n . 求带权w1≤w2≤...≤wt最优树(哈夫曼树)算法： 例2 求带权7, 10, 11, 13, 17的最优树。 前缀码问题 定理6 任意一棵二叉树都可产生一个前缀码。 定理7 任意一个前缀码都对应一棵二叉树。 已知传输符号出现的频率时，如何选择前缀码，使传输的二进制位最小？ * 第 2 编 图 论 第 5 章 树及其应用 5.1.1 树的定义与表示 定义1 连通且无回路的无向图称为树，用T表示。T中d (v)=1的结点v称为树叶。T中d(v)1的结点称为分支点或内点。每个连通分图是树的无向图称为森林。一个孤立结点称为平凡树。 树 树叶 分枝点 非树 森林 非树 树 树 定理1 给定图T=V,E，以下关于树的定义是等价的(|V|=n, |E|=m): ⑴ 无回路的连通图； ⑵ 无回路且 m = n－1； ⑶ 连通且 m = n－1； ⑷ 无回路，但增加一条新边，得到一个且仅一个回路； ⑸ 连通但删去任一边后，就不连通了； ⑹ 每一对结点有一条且仅一条通路。 推论 任何非平凡树至少有两片树叶。 证：2m = ?deg(vi)≥k + 2 (n－k) = 2n－k i 设有k个一度结点 其余 n－k个结点的度≥2 ∵m = n－1, ∴2(n－1)≥2n－k ∴k≥2 ■ 定义2 若图G的生成子图是树，则称这棵树为G的生成树。 设图G的一棵生成树为T，则T中的边称为树枝，不在T中的边称为弦，所有弦的集合称为生成树T的补。 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 G e1 e2 e3 e6 e8 e9 T e4 e5 e7 e10 T的补 定理2 连通图G至少有一棵生成树。 G只要删边去回路→连通无回路。 G T1 T2 T3 定义3 设T是n阶m条边的无向连通图G的一棵树,则G中有m-(n-1)条弦。若给T添加一条弦e，则产生包含该弦与T并具有一个圈(基本回路)的图C1，称C1为G对应生成树T及e的基本回路,称{C1,C2,…,Cm-(n-1)｝为对应生成树Ｔ的基本回路系统，并称m-(n-1)为Ｇ的圈秩,记为ξ(G)。 从树Ｔ中删除一条边，将T分成两棵树，Ｇ的顶点集划分为两个子集，联结这两个子集的边集即是对应于这条枝的割集，此即为对应于这条枝的基本割集。 在基本割集中，只有一条边为树枝。 因有n-1条枝，一般可得到n-1个基本割集，即为图Ｇ关于生成树Ｔ的基本割集系统。 v1 v2 v3 v4 只含有一条树枝的割集，即对应生成树与树枝的基本割集为:｛(v1,v2), (v２,v3)｝｛(v1,v３), (v２,v3), (v3,v4)}｛(v1,v4), (v3,v4)｝构成基本割集系统。割集秩为n-1=3。 定义５ 在图G的所有生成树中，带权最小的那棵树称为最小生成树。 2 2 2 2 3 3 1 1 红线组成最小生成树T，w(T) = 6. 5.2 根树及其应用 定义6 一个有向图，如果删去每条边的方向所得到的无向图是一棵树，则称这个有向图为有向树。 定义7 一棵非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称这棵有向树为根树。入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为内点，内点同树根统称为分支点。 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 习