离散数学高等里离散数学-课件-CHAP7.ppt

离散数学 第七章图的连通性 §7.1 点连通度和边连通度 割点 设G是个连通图，V? ? V(G) 。如果G –V?不连通，则称V?为G的一个顶点割。 特别，当V? = {v}时，称v为G的割点。 实际上，顶点割是若删去它们就会使图不连通的顶点的集合，而割点是若删去此一顶点就会使图不连通的顶点。 顶点割中的顶点都是战略要地，而割点就更是兵家必争的咽喉要塞。 点连通度 定义7.1.1：设G为连通的非完全图，令 ?(G)=min{|V? |? V?是 G的顶点割}， 称?(G)为G的点连通度，简称为G的连通度。 为统一起见，规定?(Kn)=n–1，当G为平凡图或非连通图时，?(G)=0 . k––连通图：对图G，若?(G)?k ?0，则称图G为k––连通图。 显然，k––连通图必是一个(k–1)––连通图,所有非平凡的连通图都是1––连通图。 割边 边割：设G是个连通图，E? ? E(G) 。如果G –E?不连通，则称E?为G的一个边割。 特别，当E? = {e}时，称e为G的割边。 实际上，边割是若删去它们就会使图不连通的边的集合，而割边是若删去此一边就会使图不连通的边。 边割中的边都是战略要道，而割边就更是要命的瓶颈。 边连通度 定义7.1.2：设G为非平凡连通图，令 ?(G)=min{|E? |? E?是 G的边割}， 称?(G)为G的边连通度。 当G为非连通图或平凡图时，规定?(G)=0。 k––边连通图：如果?(G) ? k，则称图G为k––边连通图。 连通度的例子 点连通度不大于边连通度 定理7.1.1：对任何图G， ?(G) ? ?(G)? ?(G)。 证明：如果图G是不连通图或者是平凡图，则有 ?(G)=?(G)=0? ?(G)； 任给一个连通图G，若?(G)=k，则存在边割E’，| E’| = k。现取E’中每一条边的一个端点构成顶点集V’，即V’={u | (u, v)∈E’且v?V’}。显然|V’| ? k 。而G－V’是不连通的，即V’是G的一个顶点割。所以?(G) ? |V’| ? ?(G)。 若G是非平凡图，则因为每一个顶点所关联的边构成一个边割，故有 ?(G)? ?(G)。 综上所述，有?(G) ? ?(G)? ?(G)。 连通度不大于平均度 定理7.1.2：任何图G(p,q)，有 ?(G) ? ?(G) ? ?2q/p? 其中 ?x? 表示不超过x的最大整数。 证明：因为2q是G的顶点度之和，2q/p 是G的顶点的平均度，而?(G)是G的最小 度，又?(G)是整数，所以，?(G) ? ?2q/p? 故由定理7.1.1有：?(G) ? ?(G) ? ?2q/p? 。 连通图的充分条件 定理7.1.3 设G(p, q)是简单图，若?(G) ? ?p/2? ，则G必连通。 证明：假设G不连通，则由?(G) ? ?p/2? 可知，G的每一个连通分支至少有?p/2? +1个顶点*，即 ?(p+2)/2? 个顶点。 断集 断集：设G是一个图，??V1，V2 ?V(G)，令[V1,V2]={(u,v) ∈E(G) | u∈V1, v∈ V2}，并称[V1,V2]为G的一个断集。 若?(G) 0，则存在断集[V1,V2]，使得| [V1,V2]| = ?(G) 。 边连通度最大的充分条件 定理7.1.4 ：若简单图G(p,q)满足?(G) ? ?p/2? ,则 ?(G) = ?(G) 。 边连通度最大的充分条件 定理7.1.4： 如果简单图G(p,q)满足?(G) ? ?p/2? ,则 ?(G) = ?(G) 。 证明：… … 2q1? |V1| ?(G) –?(G) ，于是， 边连通度最大的充分条件 定理7.1.4： 如果简单图G(p,q)满足?(G) ? ?p/2? ,则 ?(G) = ?(G) 。 证明：… …所以，|V1| ?(G)，|V2| ?(G)。 § 7.2 块 不可分图与块 定义7.2.1：没有割点的非平凡连通图。图G的极大不可分子图称为G的一个块。 例如，下图中的G3和G4是不可分图，当然也是块。 G1和G2的块如(a)、(b)所示： 不可分图是2—连通图 若图G是不可分的，则G中无割点，所以?(G) ≥2，G是2—连通图。反之依然。 注意2—边连通图不一定是不可分的。如图G2是边2—连通图，但却存在割点，因而是可分的。 内不交的通路 定义7.2.2：设通路P、Q是图G中的两条(u,v) ––通路，如果除端点u，v外，P和Q没有其他公共顶点，则称P和Q内部不相交，简称内不交。 所谓内不交的