《图论 第6章 树和割集》由会员分享，可在线阅读，更多相关《图论 第6章 树和割集（6页珍藏版）》请在金锄头文库上搜索。
1、集合论与图论,刘峰2006.4,第六章 树和割集 内容 树及其性质、生成树、割集第一节 树及其性质 1.1 树和森林 定义1 连通且无圈的无向图称为无向树，简称树，记为T。 定义2 无圈的无向图称为无向森林，简称森林。 1.2 树的特征性质,定理1 设G=(V,E)是一个(p,q)图，则下列命题等价：(1) G是树；(2) G的任两个不同顶点间有唯一的一条路联结；(3) G连通且 p=q+1；(4) G无圈且 p=q+1；(5) G无圈且任加一条边得到有唯一圈；(6) G连通且任去掉一条边得不连通图。推论1 任一非平凡树中至少有两个度为1的顶点。推论2 任一非平凡树都是偶图。推论3 任一非平凡
2、树都是2-色的。,1.3 极小连通图 定义2 若连通图G中去掉任一条边后得到一个不连通图，则称G 为极小连通图。 推论4 图G是树当且仅当G是极小连通图。1.4 树的中心 定义3 设G=(V，E)是连通图，vV，数 e(v)=maxd(v,u) 称为v在G中的偏心率。数 r(G)=mine(v) 称为G的半径。满足r(G)=e(v)的顶点v称为G的中心点。G的所有中心点组成的集合称为G的中心，G的中心记为C(G)。定理2 每棵树的中心或含有一个顶点，或含有两个邻接的顶点。,1.5 例题 例1 分别画出具有4、5、6个顶点的所有树(同构的只算一个)。 例2 设T是一棵树，T有3个度为3顶点，1个
3、2度顶点，其余均是 1度顶点。则 （1）求T有几个1度顶点？ （2）画出满足上述要求的不同构的两棵树。 1.6 关于树的问题的解题模式（等式与不等式 ） 使用公式如下： （1）q=p-1 （2）deg v=2q （3）根据具体的题设条件进行特殊的不等式的放缩解题关键 例3 设G是一棵树且(G)k，证明：G中至少有k个1度顶点。,1.7 生成树（包含所有顶点的树）定义1 设G=(V,E)是一个图，若G的一个生成子图 T=(V,F)是树，则称T是G的生成树。定义2 设G=(V，E)是一个图，若G的一个生成子图T=(V，F)是一个森林，则称T是G的生成森林。1.8 生成树存在问题 定理1 图G有生成树的充分必要条件是G为一个连通图。,
