无向图的连通性 设无向图G=<VE>, u与v连通:若u与ν之间有通路.规定u与自身总连通 连通关系R={<,|,∈且~w是V上的等价关系 连通图:平凡图,任意两点都连通的图 连通分支:关于R的等价类的导出子图 设VR={V1,V2,…,Vh},GIV1l,GIV2l,…GIVA是G的 连通分支,其个数记作p(O=k G是连通图台→p(G)=1
6 无向图的连通性 设无向图G=<V,E>, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系 R={<u,v>| u,v V且uv}是V上的等价关系 连通图: 平凡图, 任意两点都连通的图 连通分支: V关于R的等价类的导出子图 设V/R={V1 ,V2 ,…,Vk }, G[V1 ], G[V2 ], …,G[Vk ]是G的 连通分支, 其个数记作p(G)=k. G是连通图 p(G)=1
短程线与距离 u与之间的短程线:l与υ之间长度最短的通路 与v连通) 与之间的距离d(u,v):u与之间短程线的长度 若u与v不连通,规定l(u,y)=∞ 性质: d(u,y)≥20,且d(un,y)=0分>u=v d(u, v)=(v,u) d(u, v)+(v, m)2d(u, w)
7 短程线与距离 u与v之间的短程线: u与v之间长度最短的通路 (u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长度 若u与v不连通, 规定d(u,v)=∞. 性质： d(u,v)0, 且d(u,v)=0 u=v d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)
点割集 记G-v:从G中删除ν及关联的边 GV:从G中删除V中所有的顶点及关联的边 G-e:从G中删除e G-E:从G中删除E中所有边 定义设无向图G=<V,E>,VcV若p(G-V)>p(O且 VcV,p(G-V)=p(G),则称V为G的点割集.若 吵为点割集,则称p为割点
8 点割集 记 G−v: 从G中删除v及关联的边 G−V: 从G中删除V中所有的顶点及关联的边 G−e : 从G中删除e G−E: 从G中删除E中所有边 定义 设无向图G=<V,E>, VV, 若p(G−V)>p(G)且 VV , p(G−V)=p(G), 则称V为G的点割集. 若 {v}为点割集, 则称v为割点