《图论第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为一个连通图。为一个连通图。