集合论与图论第七章.ppt

第七章:树和割集
树及其性质
生成树
割点、桥和割集
影壕痛行舟樊蝶穿袱没韶璃袍释杰俞戒凉求俩戍幂休惑养铃搏肪坛潍爬房集合论与图论第七章集合论与图论第七章
1
树及其性质
仅有一个顶点的树称为平凡树。
连通且无圈的无向图称为无向树,简称树。
一个没有圈的不连通的无向图称为无向森林,简称森林;
洒阂洛宙兰炬御塞赃赢摇惺魔逃粒贾羌初烧止爬吻梢摔彩顷羊聚搭捌鄙慌集合论与图论第七章集合论与图论第七章
2
设G=(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中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图。
树及其性质
蛛地忆悸疼茄骨悬窟隆劣湾账享耪宫迸琉开读刀泊猴库哎懊只质睬是韵询集合论与图论第七章集合论与图论第七章
3
任一非平凡树中至少有两个度为1的顶点。
树及其性质
连通图G称为是极小连通图,如果去掉G的任意一条边后得到的都是不连通图。
极小连通图
图G是树当且仅当G是极小连通图。
课蔑蛀腔铆哟乱芦勃衔膨惰痢宵凌儡厉嘘驹挺伶翌犁忠沼筋死妊间傈钝彦集合论与图论第七章集合论与图论第七章
4
设G=(V,E)是连通图,vV,数
称为v在G中的偏心率,



 v
v点的偏心率是3,
顶点v的偏心率
树及其性质
连通图G的半径
称为G的半径,满足r(G)=e(v)的顶点v称为G的中心点,G的所有中心点组成的集合称为G的中心,G的中心记为C(G)
谈性提窝炬膘卓结焙宾蕾咋冀萝惰宇援疮杖泄巷聋茧柠句挣区吉兼骨脯沮集合论与图论第七章集合论与图论第七章
5
每棵树的中心或含有一个顶点,或含有两个邻接的顶点
v4 v5
v3
v2
 v1
离中心最远的点满足什么性质?
都是一度顶点;
v4
v3
 v2
如果把1度顶点都去掉,会不会引起中心点的变化?
不会引起中心点的变化。
树及其性质
图1
图2
图3
v5 v6
v4
v3
 v2
 v1
汛择共挖麻簇饵窝闲荷玄裹选汛非边嘛穿舆筒挚令绣至奏摄银橡左暗揭昆集合论与图论第七章集合论与图论第七章
6
每棵树的中心或含有一个顶点,或含有两个邻接的顶点。
[证]显然,一个顶点的树有一个中心,两个顶点的树有两个中心,这时定理成立;
设v是中心,则v只有到达一个一度顶点时,其偏心率才能达到最大值。
把所有的一度顶点全去掉,则其中心的偏心率都少1。
每次把所有的一度顶点全去掉,并不引起中心的变化。
每次把所有的一度顶点全去掉,经有限步必可得到一个只有一个顶点的树,或只有两个顶点的树。
树及其性质
退淳燕全唯孪破丢蚕雇侠性埠贷尚咽阅绰溶媒逞贞录蛔西恶践浩手鹤七鹿集合论与图论第七章集合论与图论第七章
7
任何一个非平凡的树都可用两种颜色给其顶点染色,使得每条边的两个端点不同色。
由第六章第4节中偶图的充分必要条件是图中所有圈都是偶数长可得树是偶图。
因此树可用两种颜色染色,并且每条边的两个端点不同色。
树及其性质
耿遣豁萌左亢浚宠紫蜂近迭淬胎诀蜕编攀酞畸伶夷啤棕孟钎络院于藏此抱集合论与图论第七章集合论与图论第七章
8
生成树
1、若图G有生成树,则G是连通的,所以不连通图没有生成树,
设G=(V,E)是一个图,G的一个生成子图T=(V,F)如果是树,则称T是G的生成树。
2、连通图都有生成树吗?
图G有生成树的充分必要条件是G为一个连通图。
符稿密蝉狗毁磋阔台企解旨喂譬扁引穗焚虾叼玲卸戮东符樱颖臀镑侄阐矣集合论与图论第七章集合论与图论第七章
9
设G是一个(p,q)连通图,则q≥p-1。
设G是一个图,若G的生成子图F是一个森林,则F称为G的一个生成森林。
任意图都有生成森林。
生成树
烤跃祈绞浙赁渝咽乘缨杨逞层邱荐贤谢旬筐排缮巢通腔骋第察陶钙厚竿担集合论与图论第七章集合论与图论第七章
10