8-9 树与生成树
树是一种特殊的图, 它是图论中重要的概念之一, 它有 着广泛的应用.在计算机科学中有如判定树、语法树、分 类树、搜索树、目录树等等. 一.树 (Tree) (a) 1.树的定义:一个连通无回路的 无向图T,称之为树. 如(a) 2.叶结点:度数为1的结点, 称为叶结点. (b) 3.分支结点(内结点):度数大于1的结点. 4.森林:一个无向图的每个连通分支都是树.如(b)
三.赋权图的最小生成树 1.定义:一棵生成树中的所有边的权之和称为该生成树的 权. 具有最小权的生成树,称为最小生成树. 最小生成树很有实际应用价值.例如结点是城市名,边的权 表示两个城市间的距离, 从一个城市出发走遍各个城市, 如何选择最优的旅行路线.又如城市间的通信网络问题,如 何布线,使得总的线路长度最短. 例如:右图所示 2 v3 v2 2.求最小生成树算法 3 5 1 1 2 7 ---Kruskal算法: 7 v1 8 v8 v5 3 v4 (贪婪算法) 4 3 4 6 2 4 v7 v6 6
Kruskal算法: 设G是有n个结点,m条边(m≥n-1)的连通 图. S=Φ i=0 j=1
将所有边按照权升序排序: e1, e2, e3,… ,em S=S∪{ai} j=j+1 ai=ej i=i+1
|S|=n-1
N
Y
输出S
停பைடு நூலகம்
N
取ej使得 S∪{ ej}有回路? Y
j=j+1
|S|=n-1, 说明是树 最后S={a1, a2, a3,… ,an-1}
5.与树定义等价的几个命题 定理1给定图T, 以下关于树的定义是等价的. ⑴ T无回路的连通图. ⑵T无环且每对结点之间有一条且仅有一条路. ⑶ T无回路但在任一对不相邻的顶点间添加一条 新边e，则T+e包含唯一的回路. ⑷ T连通的,且每条边都是割边. ⑸ T连通的且m=n-1. ⑹ T无回路且m=n-1. 证明:⑴⑵:已知T是连通无回路图,所以T中无环。 若T中存在两条不同的u-v路P1和P2，则存在 P1的一条边e=xy，它不是P2的边，因此(P1 P2)-e连通，所以， (P1 P2)-e存在一条x-y 路P，故P+e是T的圈，矛盾。
二. 生成树 在图论的应用中,找出一个连通图的所有不同的生成树,以 及找出最小生成树是很有意义的. 1.定义:如果图G的生成子图是树,则称此树为G的生成树. 2.弦:图G中,不在其生成树里的边,称作弦. 所有弦的集合, 称为该生成树的补. v1 定理2 连通图G中至少有一棵生成树. v2 v3 证明:如果G中无回路, 则G本身就是树. v5 如果G中有回路,可以通过反复删去回路 v4 中的边,使之既无回路,又连通.就得到生成树. 思考题:设G是有n个结点,m条边的连通图, 问要删去多少 条边,才得到一棵生成树?
⑸ T连通的且m=n-1. ⑹ T无回路且m=n-1. ⑸⑹:只需证明T无回路。对T关于顶点 数归纳。 当n=1或n=2时，显然成立。 假设nk时结论成立，往证n=k+1时成 立。 因为T连通，所以(T)1，由m=n-1及 d(v)=2m得，T中至少存在一点u，使 得d(u)=1。考虑T’=T-u，显然T’连通， 且|E(T’)|=|V(T’)|-1，由归纳假设，T’ 无回路，所以T无回路。
Prin算法(边割法)
⑵T无环且每对结点之间有一条且仅有一条路. ⑶ T无回路但在任一对不相邻的顶点间添加一条 新边e，则T+e包含唯一的回路. ⑷ T连通的,且每条边都是割边. ⑵⑶:显然T无回路，否则对回路上的任一对顶 点都至少存在两条路，与⑵矛盾。设u，v是T 中任意两个不相邻的点，令e=uv，由⑵，T中 有一条唯一的u-v路，所以T+e中包含唯一的回 路。 ⑶⑷:因为T无回路，所以T的每条边都是割边； 若T不连通，设T1，T2是T的两个分支，设 uV(T1), vV(T2), 则uvE(T)，显然T+uv 不存在回路，与⑶矛盾。
⑷ T连通的,且每条边都是割边. ⑸ T连通的且m=n-1. ⑷⑸:关于点数用归纳法证明。 当n=1或2时，T是平凡图或K2，显然有m=n-1。 假设nk时结论成立，往证n=k+1时成立。 当n=k+1时。取T的一条边e，由⑷，e是割边， 所以T-e有两个分支T1和T2， 因为|V(T1)|k, |V(T2)|k, 所以，由归纳假设，有 |E(T1)|=|V(T1)|-1， |E(T2)|=|V(T2)|-1 故m=|E(T1)|+|E(T2)|+1 =|V(T1)|-1+ |V(T2)|-1+1 =n-1。
边按升序排序:边(vi, vj)记成eij e34 e23 e38 e17 边 e28 权 1 1 2 2 2
e24 3
e45 3
e57 3
e16 4
e35 e46 e67 e58 e12 e18 边 e78 e56 4 5 6 6 7 7 8 权 4 2 v3 v2 3 5 1 1 7 2 7 v1 8 v8 v5 3 v4 4 3 4 2 v3 v2 6 2 4 1 1 v7 v 6 6 v1 v8 v5 3 v4 4 3 2 v7 v6
⑹ T无回路且m=n-1. ⑴ T无回路的连通图. ⑹⑴:假设T不连通，设T1, T2,…, Tk为T的连通分支，则 k2。对任意的Ti，Ti是无回路的连通图，所以Ti是树， 由⑹得， |E(Ti)|=|V(Ti)|-1 故m=i=1k|E(Ti)|=i=1k|V(Ti)|-k =n-k<n-1 矛盾。 定理2：每一非平凡树至少有两片树叶。 证明：设T是一非平凡树，则m=n-1。 因为T连通且非平凡，所以(T)1。 设T有k片树叶，则剩余的n-k个顶点的度至少为2。由 d(v)=2m得，k+2(n-k)m=2(n-1), 所以 k2。