北京理工大学《离散数学》第7章 树-2012-2013-2版.pptVIP

波兰符号法与逆波兰符号法 用2元有序正则树表示算术运算算式如下: 以中序行遍方 式将运算符和数标记在顶点上, 即将运算符放在分支点上, 数放在树叶上, 每个运算符对它所在分支点的2棵子树进 行运算, 并规定左子树是被除数或被减数. 例4 右图表示算式 ((b+(c+d))?a)?((e?f)?(g+h)?(i?j)) * 欢迎辞 定义6.10 设G=V,E, G ?=V ?,E ?是2个图(同为无向图,或同为有向图) 若V ??V且E ??E, 则称G ?为G的子图, G为G ?的母图, 记作 G ??G 若G ??G 且V ?=V, 则称G ?为G的生成子图 若V ??V或E ??E, 称G ?为G的真子图 设V ??V且V ???, 以V ?为顶点集, 以两端点都在V ?中的所有 边为边集的G的子图称作V ?的导出子图, 记作G[V ?] 设E ??E且E ???, 以E ?为边集, 以E ?中边关联的所有顶点为 顶点集的G的子图称作E ?的导出子图, 记作G[E ?] * r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元完全正则树: 所有树叶层数相同的r元正则树 r元有序树: 有序的r元树 r元正则有序树: 有序的r元正则树 r元完全正则有序树: 有序的r元完全正则树 * 第7章 树及其应用 第7章 树及其应用 7.1 无向树 7.2 根树及其应用 7.1 无向树 7.1.1 无向树的定义及其性质 7.1.2 生成树与基本回路和基本割集 7.1.3 最小生成树 无向树的定义 无向树: 连通无回路的无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数?2的顶点 例如 (a) (b) (b)为森林 12阶树 无向树的性质 定理7.1 设G=V,E是n阶m条边的无向图, 下面各命题是 等值的： (1) G是树(连通无回路); (2) G中任意两个顶点之间存在惟一的路径; (3) G是连通的且m=n?1; (4) G中无回路且m=n?1; (5) G中无回路, 但在任何两个不相邻的顶点之间加一条边 所得图中有惟一的一条初级回路. (6) G是连通的且G中任意一条边均为桥. 无向树的性质(续) 定理7.2 非平凡的无向树至少有两片树叶 证 设有n(n1)个顶点, x片树叶, 由握手定理和定理7.1, 有 解得 x?2. 实例 例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶 点全是树叶. 试求树叶数, 并画出满足要求的非同构的无 向树. 解 设有x片树叶,用树的性质m=n-1和握手定理,n=1+2+x=3+x 2m=2(n-1)=2?(2+x)=1?3+2?2+x 解得x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向数，如图所示。 同构：结点和边分别存在着一一对应且保持相同的关联关系 实例 例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶 点度数均为4. 试求T得阶数n. 解 设有T的阶数为n，用树的性质则边数为m=n-1，4度顶点的个数为n-(1+1+5).由握手定理得 2m=2(n-1)=5 ? 1+2?1+3 ? 1+4(n-7) 解得n=8，4度顶点为1个. T的度数列为1, 1, 1, 1,1,2, 3,4 生成树 定义7.2 设G是无向连通图, 若G的生成子图T是一棵树, 则 称T是G的生成树. G在T中的边称作T的树枝,不在T中的边 称作T的弦. T的所有弦的集合的导出子图称作T的余树 例如 图中黑边构成生成树 红边构成余树 注意: 余树一般不是树 生成树的存在性 定理7.3 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 不破坏连通性, 重复进行直到 无圈为止, 得到图的一棵生成树. 推论1 设n阶无向连通图有m条边, 则m?n?1. 推论2 设n阶无向连通图有m条边, 则它的生成树的余树 有m?n+1条边. 最小生成树 图G的每一条边e附加一个实数w(e), 称作边e的权. 图G连 同附加在边上的权称作带权图, 记作G=V,E,W. 设H是G的子图, H所有边的权的和称作H的权, 记作W(H). 最小生成树: 带权图权最小的生成树 避圈法 (Kruskal) (1) 将所有非环边按权从小到大排列, 设为e1, e2, …, em (2) 令T = ? (3) For k=1 to m Do 若ek与T 中的边不构成回路, 则将ek加入T 中 实例 例5 求图的一棵最小生成树 W(T