图论第六章树和割集.ppt

集合论与图论 刘峰 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-色的。 1.3 极小连通图 定义2 若连通图G中去掉任一条边后得到一个不连通图，则称G 为极小连通图。 推论4 图G是树当且仅当G是极小连通图。 1.4 树的中心 定义3 设G=(V，E)是连通图，v∈V，数 e(v)=max{d(v,u)} 称为v在G中的偏心率。 数 r(G)=min{e(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个2度顶点，其余均是 1度顶点。则 （1）求T有几个1度顶点？ （2）画出满足上述要求的不同构的两棵树。 1.6 关于树的问题的解题模式（等式与不等式 ） 使用公式如下： （1）q=p-1 （2）∑deg v=2q （3）根据具体的题设条件进行特殊的不等式的放缩[解题关键] 例3 设G是一棵树且Δ(G)≥k，证明：G中至少有k个1度顶点。