图论第6章树和割集.ppt

第六章第六章 树和割集树和割集 内容内容 树及其性质、生成树、割集树及其性质、生成树、割集树及其性质、生成树、割集树及其性质、生成树、割集第一节第一节 树及其性质树及其性质1.1 1.1 树和森林树和森林定义定义定义定义1 1 1 1 连通且无圈的无向图称为无向树，简称树，连通且无圈的无向图称为无向树，简称树，连通且无圈的无向图称为无向树，简称树，连通且无圈的无向图称为无向树，简称树，记为记为记为记为T T T T。定义定义定义定义2 2 2 2 无圈的无向图称为无向森林，简称森林无圈的无向图称为无向森林，简称森林无圈的无向图称为无向森林，简称森林无圈的无向图称为无向森林，简称森林。1.2 1.2 树的特征性质树的特征性质 定理定理1 1 设设G=(V,E)G=(V,E)是一个是一个(p,q)(p,q)图，则下列命题等价：图，则下列命题等价：(1)G(1)G是树；是树；(2)G(2)G的任两个不同顶点间有唯一的一条路联结；的任两个不同顶点间有唯一的一条路联结；(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 极小连通图极小连通图定义定义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(v)=maxd(v,u)e(v)=maxd(v,u)称为称为v v在在G G中的偏心率。中的偏心率。数数r(G)=mine(v)r(G)=mine(v)称为称为G G的半径。的半径。满足满足r(G)=e(v)r(G)=e(v)的顶点的顶点v v称为称为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有几个有几个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为一个连通图。为一个连通图。