复习思考题15n重新画下图的平面嵌入，使其外部面的次数分别为1，3，4n上图是极大平面图 ( )n同构的两个图的对偶图一定同构 ( )n 设无向图G与K3,3同胚，至少从G中删除_条边才能使所得图为平面图 n设设G为为8阶阶极大平面图，则极大平面图，则G的面数的面数r =_R0R1R2R3第7章 树 7.1 无向树及生成树7.2 根树及其应用最小生成树问题n树是一类既简单而又非常重要的图，它是计算机中一种基本的数据结构和表示方法n在输电网络分析、有机化学、最短连接及渠道设计等领域也都有广泛的应用，如：n某一地区有若干个主要城市，拟修建高速公路某一地区有若干个主要城市，拟修建高速公路把这些城市连接起来，使得其中任何一个城市把这些城市连接起来，使得其中任何一个城市都可以经高速公路直接或间接到达另一个城市，都可以经高速公路直接或间接到达另一个城市，设已知任意两个城市之间修建高速的成本，设已知任意两个城市之间修建高速的成本，那那么应如何决定在哪些城市间修建高速公路，使么应如何决定在哪些城市间修建高速公路，使得总成本最小？得总成本最小？ 7.1 无向树及生成树n无向树无向树: 连通无回路的无向图。
连通无回路的无向图n树叶树叶: : 树中度数为树中度数为1 1的顶点n分支点分支点: : 树中度数树中度数 2 2的顶点n规定：规定：平凡图也是树，叫平凡图也是树，叫平凡树n森林森林: 每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图n声明声明:本章中所讨论的回路均指简单回路或初级回路本章中所讨论的回路均指简单回路或初级回路 (a) 树(b)森林无向树的几个等价定义定定理理7.1 设G = 是 n 阶 m 条边的无向图，则下面各命题是等价的：（1）G是树是树(连通连通、无回路无回路);（2）G中每对顶点之间具有惟一的一条路径中每对顶点之间具有惟一的一条路径;（3）G中无回路且中无回路且 m=n 1;（4）G是连通的且是连通的且 m=n 1;（5）G是连通的且是连通的且G中任何边均为桥中任何边均为桥;（6）G中无回路中无回路, 但在任两个不相邻的顶点之间加但在任两个不相邻的顶点之间加一条新边后所得图中有惟一的一个含新边的回路一条新边后所得图中有惟一的一个含新边的回路.求6个顶点的非同构无向树n顶点数n = 6，树的边数m = n-1=5n树的总度数为n树中各顶点度数分配情况可为(1)1, 1, 1, 1, 1, 5 (2) 1, 1, 1, 1, 2, 4(3) 1, 1, 1, 1, 3, 3 (4) 1, 1, 1, 2, 2, 3(5) 1, 1, 2, 2, 2, 2无向树的性质 定理定理7.2 设设T 是是 n 阶非平凡的无向树，则阶非平凡的无向树，则T 中至少中至少有两片树叶有两片树叶. 证证： 由由定理定理7.1(树的定义树的定义)可知树可知树 T 共有共有n-1条边，条边， 由握手定理得：由握手定理得： 设设 T 有有 k 片树叶，则片树叶，则 T 中的分支点为中的分支点为 n-k 个，每个分个，每个分支点的度数支点的度数 2，所有分支点度数之和，所有分支点度数之和 2(nk)，从而下式成，从而下式成立：立： 由上式解出由上式解出 k 2.例题1已知无向树 T 中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解：解：用用树的性质树的性质m=n 1和和握手定理握手定理. 设有设有k片树叶，于是片树叶，于是 n = 1+2+k = 3+k, 2m=2(n 1)=2 (3+k-1)=1 3+2 2+k 1 解出解出k=3，故，故T有有3片树叶片树叶. T的度数列为的度数列为1, 1, 1, 2, 2, 3 有有2棵非同构的无向树：棵非同构的无向树：例题2已知无向树T 有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T 的阶数n, 并画出满足要求的所有非同构的无向树. 解解：设设4度度顶顶点点的的个个数数为为 k 个个，则则n=5+1+1+k =7+k 树的树的边数边数m= (7+k)-1 =6+k 由握手定理得由握手定理得 2m=2(6+k)=5 1+2 1+3 1+4k 解出解出k=1, 则则 n = 7+k = 8. T的度数列为的度数列为1,1,1,1,1,2,3,4 有有3棵非同构的无向树棵非同构的无向树 生成树 设G为无向连通图nG的生成树: G的生成子图并且是树。
的生成子图并且是树n生成树T的树枝: G在在T中的边n生成树T的弦: G不在不在T中的边n生成树T的余树 : 所有弦的集合的导出子图所有弦的集合的导出子图n注意： 不一定连通、不一定不含回路、不一定连通、不一定不含回路、不一定不一定是树T的余树的余树G生成树生成树T生成树的存在性 n定理定理 任何无向连通图都有生成树任何无向连通图都有生成树. .n证：用破圈法. 若若图中无圈图中无圈, 则图本身就是自己的生成树则图本身就是自己的生成树. 否则删去圈上的任一条边否则删去圈上的任一条边, 这不破坏连通性这不破坏连通性, 重复进行直到无圈为止重复进行直到无圈为止,剩下的图是一棵生成树剩下的图是一棵生成树.n推论推论 设设n阶无向连通图有阶无向连通图有m条边条边, 则则m n 1. 基本回路与基本回路系统 n基本回路基本回路n设设T是连通图是连通图G的一棵生成树的一棵生成树, 对对每每一一条条弦弦e, 存存在在惟惟一一的的由由弦弦e和和T的的树树枝枝构构成成的初级回路的初级回路Ce, 称称Ce为对应于弦为对应于弦e的的基本回路基本回路.n基本回路系统基本回路系统所有基本回路的集合n求基本回路的算法求基本回路的算法: n设设弦弦e=(u,v), n先求先求T中中u到到v的路径的路径 uv, 再并上弦再并上弦e, n即得对应即得对应e的基本回路的基本回路. 基本回路与基本回路系统实例图中红边为一棵生成树,求对应它的基本回路系统。
解：解： 弦弦e, f, g对应的基本回路分别为对应的基本回路分别为 加加e 得基本回路得基本回路Ce=e b c , 加加f 得基本回路得基本回路 Cf=f a b c , 加加g 得基本回路得基本回路Cg=g a b c d , 则：则：C基基=Ce , Cf , Cg . 回路合并n合并合并回路回路C1和和C2(C1 C2): C1 C2是是C1和和C2上的边的对称差构成的上的边的对称差构成的(一条或一条或几条几条)回路回路.基本回路的性质n连通图中的任一条回路连通图中的任一条回路都可以表都可以表成成对应对应它它所所含弦的基本回路的合并含弦的基本回路的合并.例如例如, Ce = bce Cf = abcf Cg= abcdg Ce Cf = aef Ce Cg = aedg Cf Cg = fdg Ce Cf Cg = bcdgfe基本割集与基本割集系统 n基本割集基本割集n设设T是连通图是连通图G的一棵生成树的一棵生成树, 对对T的的每每一一条条树树枝枝a, 存存在在惟惟一一的的由由树树枝枝a, 其其余余的的边都是弦的割集边都是弦的割集Sa, 称称Sa为对应树枝为对应树枝a的的基本割集基本割集。
n基本割集系统是是所有基本割集的集合所有基本割集的集合n基本割集的算法基本割集的算法 设设a为为生生成成树树T的的树树枝枝, T a由由两两棵棵子子树树T1与与T2组组成成, Sa=e | e E(G)且且e的的两两个个端端点点分分别别属属于于T1与与T2 .基本割集与基本割集系统实例例 图中红边为一棵生成树, 求对应它的基本割集系统解：解： 树枝树枝a,b,c,d对应的基本割集为对应的基本割集为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S基基=Sa, Sb, Sc, Sd.基本割集的性质n连通图中的任一连通图中的任一割集割集都可以表都可以表成成对应对应它它所含所含树枝树枝的基本的基本割集割集的的对称差对称差.例如例如 ： Sa = a, f, g, Sb = b, e, f, g, Sc = c, e, f g, Sd = d, g, Sa Sb = a,b,e Sa Sc= a,e,c Sb Sd = b,e,f,d无向图与最小生成树 n定义 n对对无无向向图图或或有有向向图图的的每每一一条条边边e附附加加一一个个实实数数w(e), 称称作作边边e的权的权. n图连同附加在边上的权称作图连同附加在边上的权称作带权图带权图, 记作记作G=. n设设T是是G的的生生成成树树, T所所有有边边的的权权的的和和称称作作T的的权权, 记记作作W(T).n最小生成树: 带权图中权最小的生成树。
带权图中权最小的生成树求最小生成树的算法避圈法 (Kruskal)设设G=, 将除环外的边按权将除环外的边按权从小到大排序从小到大排序：e1, , em.(1) 取取e1在在T中中(2) 检查检查e2,若若e2与与e1不构成回路不构成回路, 则将则将e2加入加入T中中, 否则弃去否则弃去e2.(3) 检查检查e3, 重复进行直至得到生成树为止重复进行直至得到生成树为止. 实例例例 求图的一棵最小生成树求图的一棵最小生成树 W(T) =38最小生成树的应用n最小生成树聚类算法n设有一设有一组数据组数据D=a1,a2,an,D中的任意两个数中的任意两个数据据ai,aj的相似程度可以用一个相似度函数的相似程度可以用一个相似度函数d(ai,aj)来度量，称为这两个数据的距离来度量，称为这两个数据的距离n给定给定一个正整数一个正整数k(1kn)，D的一个的一个k聚类是聚类是D的一个的一个k划分划分 ，使得同一子类中的数据间的距，使得同一子类中的数据间的距离尽可能地离尽可能地“近近”，不同子类的数据间的距离尽，不同子类的数据间的距离尽可能地可能地“远远”7.2 根树及其应用n有向树: 基图为无向树的有向图基图为无向树的有向图. .n根树: 有有一一个个顶顶点点入入度度为为0, 其其余余的的入入度度均均为为1的非平凡的有向树的非平凡的有向树.n树根: 有向树中入度为有向树中入度为0的顶点的顶点.n树叶: 有有向向树树中中入入度度为为1, 出出度度为为0的的顶点顶点.n内点: 有有向向树树中中入入度度为为1, 出出度度大大于于0的顶点的顶点.n分支点: 树根与内点的总称树根与内点的总称. .根树n根树的画法:n树根放上方树根放上方, ,省去所有有向边上的箭头省去所有有向边上的箭头n如右图所示n a 是树根是树根n b, e, f, h, i 是树叶是树叶n c, d, g是内点是内点n a, c, d, g 是分支点是分支点 第第0层：层：a 第第1层：层：b，c 第第2层：层：d，e, f 第第3层：层：g，h 第第4层：层：i 树高：树高：4根树n顶点顶点v的层数的层数n在根树中，从树根到任意顶点在根树中，从树根到任意顶点v只能有唯一的一只能有唯一的一条路，这条路的长度称为条路，这条路的长度称为v的的级级(层层)数数。
n树高: 有向树中顶点的最大层数有向树中顶点的最大层数家族树n把根树看作一棵家族树:(1) 若若顶顶点点 a 邻邻接接到到顶顶点点 b, 则则称称 b 是是 a 的的儿子儿子, a 是是 b 的的父亲父亲;(2) 若若b和和c为为同同一一个个顶顶点点的的儿儿子子, 则则称称b和和c是是兄弟兄弟;(3) 若若a d且且a可可达达d, 则则称称a是是d的的祖祖先先, d是是a的的后代后代.n根子树n设设v为为根根树树的的一一个个顶顶点点且且不不是是树树根根, 称称v及及其其所所有有后后代代的的导导出出子子图图为为以以v为根的为根的. 根树的分类nr 叉树叉树:根树的每个分支点根树的每个分支点至多至多有有r 个儿子个儿子nr 叉正则树叉正则树: 根树的每个分支点根树的每个分支点恰有恰有r 个儿子个儿子nr 叉完全。