（精）离散数学 第九章：树.ppt

9.1 无向树及生成树 树：连通而不含回路的无向图称为无向树，简称树，记作 T。 森林：连通分支数大于等于2，且每个连通分支均是树的非连通无向图。 平凡树：平凡图为平凡树。 一、树的概念 森林 树叶: 树中度数为1的顶点 分支点: 树中度数?2的顶点 树的性质： (1) G连通而不含回路； (2) 每对顶点之间具有唯一一条初级通路 (3) n = m+1 (4) 若在G中任意两个不相邻的顶点之间增加一条边，就形成唯一一条初级回路。 (5) 连通且每条边都是桥 (6) 连通但删除任何一条边后就不连通 设G=V,E是n阶m条边的无向树， 则下面各命题是等价的： 性质(7): 任一棵非平凡树 T = V,E ，至少有两片叶。 证明：设T有x片树叶，由握手定理及定理9.1知， 由上式解出x?2. 生成树：若图G为无向连通图. T为G的生成子图，且T为树，称T为G的生成树。 三、生成树及其构造方法 树枝与弦：G在T中的边称为T的树枝，G不 在T中的边称为T的弦。 余树：T的弦的集合的导出子图称为T的余树。 生成树 余树 生成树 余树 例子 无向连通图的生成树不一定唯一 生成树的余树不一定是树 带权图的最小生成树：设G = V,E,W 是带权的连通简单图， 具有权最小的生成树称为最小生成树。 T是G的一棵生成树，T中所有枝的权之和称为T的权，记作：W(T)。 四、最小生成树 方法：避圈法 在不产生回路的基础上依次画出 权值最小的边，直至画出n-1条边 为止 v1 5 6 5 6 5 4 1 v2 v4 v5 v3 2 3 例9.1.1： 5 v1 5 4 1 v2 v4 v5 v3 2 3 W(T)=1+2+3+4+5=15 6 5 1 v2 v4 v5 v3 2 3 例9.1.2： v1 5 5 1 v2 v4 v5 v3 2 3 v1 5 6 5 5 5 1 v2 v4 v5 v3 2 3 5 5 or or 5 5 1 v2 v4 v5 v3 2 3 W(T)=1+2+3+5+5=16 ！最小生成树不一定唯一 定义： 设T是n阶m条边的无向连通图G的一棵生成树，设e1?, e2?, … , e?m?n+1为T的弦. 设Cr为T添加弦er?产生的G中惟一的圈(由er?和树枝组成), 称Cr为对应弦er?的基本回路 r=1, 2, …, m?n+1. 称{C1,C2, …, Cm?n+1}为对应T的基本回路系统. 五：基本回路与基本回路系统 例9.1.3： Ca=aef Cb=bde Cc=cdf 基本回路系统为：{Ca, Cb, Cc} 定义： 设T是n阶连通图G的一棵生成树, e1?, e2?, …, e?n?1为T的树枝，Si是G的只含树枝ei?, 其他边都是弦的割集, 称Si为对应生成树T由树枝ei?生成的基本割集。 i=1, 2, …, n?1. 称{S1, S2, …, Sn?1}为对应T的基本割集系统. 六：基本割集与基本割集系统 例9.1.4： Sa={a,f,g} Sb={b,g,h} Sd={d,h,i} Sc={c,f,h} Se={e,f,i} 基本割集系统为：{Sa, Sb, Sc , Sd, Se} 课后例题：9.5，9.6，9.7，9.8 课后作业：9.1，9.3，9.4，9.5，9.6，9.7，9.8 9.2 根树及其应用 一、树的概念 有向树: 基图为无向树的有向图 根树: 有一个顶点入度为0, 其余的入度均为1的 非平凡的有向树 树根: 有向树中入度为0的顶点 树叶: 有向树中入度为1, 出度为0的顶点 内点: 有向树中入度为1, 出度大于0的顶点 分支点: 树根与内点的总称(出度大于等于1） 顶点v的层数: 从树根到v的通路长度，记作l(v) 树高: 有向树中顶点的最大层数，记作h(T) 根树的画法:树根放上方,省去所有有向边上的箭头 如右图所示 a是树根 b,e,f,h,i是树叶 c,d,g是内点 a,c,d,g是分支点 a为0层;1层有b,c; 2层有d,e,f; 3层有g,h; 4层有i. 树高为4 定义 把根树看作一棵家族树: (1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子, a 是 b 的父亲; (2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟; (3) 若a?b且a可达b, 则称a是b的祖先, b是a的后代. (4)设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树. 家族树： 有序树: 每一层的结点均有序 r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元完全正则树: 所有树叶层数相同都等于树高的r元