图论 第6章 树和割集.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度顶点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为一个连通图。