离散数学图连通性PPT课件.pptx

"离散数学图连通性PPT课件" 本资源是一个关于离散数学图连通性的PPT课件，总共28页，涵盖了图的连通性、通路与回路、连通图、点割集与边割集等重要概念。 图的连通性 图的连通性是指图中的顶点之间是否存在路径。如果从顶点u到v存在通路，则称u和v是连通的。连通关系R={<u,v>| u,v∈V且u与v连通}是一个等价关系。连通图是任意两点都连通的图。 通路与回路 通路是指图中的顶点和边交替序列。若通路中所有顶点各异，则称为初级通路或路径。长度为奇数的圈称作奇圈，长度为偶数的圈称作偶圈。若通路中所有边各异，则称为简单通路，否则称为复杂通路。 定理6.3 在n阶图中，若从顶点u到v(u≠v)存在通路，则从u到v存在长度小于等于n-1的初级通路。 定理6.4 在n阶图中，若存在v到自身的简单回路，则一定存在v到自身长度小于等于n的初级回路。 无向图的连通性 设无向图G=<V,E>, u,v∈V。u与v连通iff u与v之间有通路。连通图是任意两点都连通的图。 连通分支 设无向图G=<V,E>, V/R={V1,V2,…,Vk}，G的连通分支为G[V1],G[V2],…,G[Vk]。连通分支数p(G)=k，G是连通图iff p(G)=1。 短程线与距离 u与v之间的短程线是u与v之间长度最短的通路。u与v之间的距离d(u,v)是u与v之间短程线的长度。 点割集与边割集 设无向图G=<V,E>, v∈V, e∈E, V'⊆V, E'⊆E。记G-v:从G中删除v及关联的边；G-V':从G中删除V'中的所有顶点及关联的边；G-e:从G中删除e；G-E':从G中删除E'中的所有边。如果p(G-V')>p(G)且∀V''⊆V', p(G-V'')=p(G)，则称V'为G的点割集。若{v}为点割集，则称v为割点。 实例说明 Kn无点割集n阶零图既无点割集，也无边割集。若G连通，E'为边割集，则p(G-E')=2若G连通，V'为点割集，则p(G-V')≥2。 这个PPT课件详细地介绍了图的连通性、通路与回路、连通图、点割集与边割集等重要概念，并提供了实例说明，帮助学生更好地理解离散数学图连通性。