集合论与图论第七章.ppt

集合论与图论第七章_21089。,简称树。一个没有圈的不连通的无向图称为无向森林,简称森林;=(V,E)是一个(p,q)图,则下列各命题等价:(1)G是树(2)G的任意两个不同顶点间有唯一的一条路联结;(3)G是连通的且p=q+1;(4)G中无圈且p=q+1;(5)G中无圈且G中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图;(6)G是连通的,并且若p≥3,则G不是Kp,G中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图。。,如果去掉G的任意一条边后得到的都是不连通图。。=(V,E)是连通图,vV,数称为v在G中的偏心率,vv点的偏心率是3,,满足r(G)=e(v)的顶点v称为G的中心点,G的所有中心点组成的集合称为G的中心,G的中心记为C(G),或含有两个邻接的顶点v4v5v3v2v1离中心最远的点满足什么性质?都是一度顶点;v4v3v2如果把1度顶点都去掉,会不会引起中心点的变化?不会引起中心点的变化。v5v6v4v3v2,或含有两个邻接的顶点。[证]显然,一个顶点的树有一个中心,两个顶点的树有两个中心,这时定理成立;设v是中心,则v只有到达一个一度顶点时,其偏心率才能达到最大值。把所有的一度顶点全去掉,则其中心的偏心率都少1。每次把所有的一度顶点全去掉,并不引起中心的变化。每次把所有的一度顶点全去掉,经有限步必可得到一个只有一个顶点的树,或只有两个顶点的树。,使得每条边的两个端点不同色。由第六章第4节中偶图的充分必要条件是图中所有圈都是偶数长可得树是偶图。因此树可用两种颜色染色,并且每条边的两个端点不同色。、若图G有生成树,则G是连通的,所以不连通图没有生成树,=(V,E)是一个图,G的一个生成子图T=(V,F)如果是树,则称T是G的生成树。2、连通图都有生成树吗?。(p,q)连通图,则q≥p-1。,若G的生成子图F是一个森林,则F称为G的一个生成森林。任意图都有生成森林。