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