离散八.ppt

有向树 一个有向图D ，如果它的基图为无向树，则称D为有向树. 在有向树中，最重要的是根树. 根树的定义 定义 一个顶点的入度为0，其余顶点的入度均为1的有向树称为根树. 在根树中，入度为0的顶点称为树根； 入度为1，出度为0的顶点称为树叶； 入度为1，出度大于0的顶点称为内点； 内点和树根统称为分支点. 树根到任意顶点v的路径长度称为v的层数，记作l(v). 称层数相同的顶点在同一层上，层数最大的顶点的层数称为树高，记h(T)为根树T的高度. 例 a为树根; d,e,h,j,k,l为树叶； b,c,f,i为内点； a,b,c,f,i为分支点； 根树T的高度h(T)=4 a b c d e f h i j k l 根树T 第1层 第0层 第2层 第3层 第4层 一棵根树可看成一棵家族树 在非平凡根树T中，若顶点a邻接到b，则称b为a的儿子， a为b的父亲；若b,c的父亲相同，则称b,c为兄弟；若a?d，且a可达d ，则称a为的d祖先， d为a的后代. 根子树、有序树 在根树T中，?a?V(T)，称a及其后代的导出子图为T的根子树. 每一层上的顶点(边)都标定次序的根树称为有序根树. R叉树、r叉正则树、r叉完全正则树 定义 设T为一棵非平凡根树，若T的每个分支点至多有r个儿子，则称T为r叉树；若T的每个分支点恰有r个儿子，则称T为r叉正则树；若T为r叉正则树，且所有树叶的层数均为树高，则称T为r叉完全正则树. 例 2叉树 2叉正则树 2叉完全正则树 第八章 树 无向树 无向树的定义 定义 一个连通且无回路的无向图称为无向树，简称为树，记作T. 树中度数为1的顶点称为树叶; 度数大于1的顶点称为分支点. 平凡图称为平凡树. 每个连通分支都是树的非连通无向图称为森林. 例 平凡树 树 森林 a b c d e f g 无向树的等价定义 定理8.1 设G=?V,E?是无向图，?V?=n，?E?=m，以下各命题等价 (1) G连通且不含回路 (G是树). (2) G的每对顶点之间有唯一的一条路径. (3) G是连通的，且m= n-1. (4) G中无回路，且m= n-1. (5) G中无回路，但在G的任何两个不相邻顶点.间增加一条新边，就得到唯一的一条初级回路. (6) G是连通的，但删除任何一条边后，所得图不连通，即G的每条边都为桥. (1) G连通且不含回路 (G是树).(2) G的每对顶点之间有唯一的一条路径. 证 (1)?(2) 设u,v为G中任意两顶点，由G 连通知u,v 之间有通路，因而必有路径. 若路径多于一条，则必形成回路，与G 中无回路矛盾，故u,v 之间有唯一的一条路径. (2) G的每对顶点之间有唯一的一条路径.(3) G是连通的，且m= n-1. (2)?(3) 由于G的每对顶点之间有路径，因此G中任意两顶点均是连通的，故G是连通的.下面用归纳法证m=n-1. 当n=1时， G为平凡树， m=0，结论成立. 假设n?k时，结论成立. 那么当n=k+1时，设e=(u,v)为G中一条边，由(2)知u,v 之间除路径uev 外，无其它路径，因而G-e得两个连通分支G1和G2, 设它们的顶点数和边数分别为n1 ,n2 ; m1 ,m2 .显然n1? k ， n2? k，由假设 m1=n1-1,m2= n2 –1, 故m=m1+m2+1=n1-1+n2–1+1=n-1. (3) G是连通的，且m= n-1.(4) G中无回路，且m= n-1. (3)?(4) 若G中有回路，从回路中删去任意一条边后，所得图仍然是连通的， 若所得图仍有回路，再从回路中删去一条边，直到所得图无回路为止. 设共删去r(r?1)条边所得图为G1, G1无回路,但仍然是连通的，即G1为树. 由(1)?(2) ?(3)，因此G1中m1=n1–1，而n1=n ， m1=m-r，于是 m-r=n–1，即m=n–1+r (r?1) ，与已知矛盾，故G中无回路. (4) G中无回路，且m= n-1.(5) G中无回路，但在G的任何两个不相邻顶点间增加一条新边，就得到唯一的一条初级回路. (4)?(5) 由(4)