应用离散数学六.ppt

图中最大的没有割点的连通子图称为块。 * * * 桥的定义？ * IG(v)是v的关联集 * Kn是n-1正则图 * * * 证明自学 * * * * * * * * * * * 扇形割集(fan cutset) IG(v)不一定是边割集(不一定极小) IG(v)不是边割集 ? v是割点 扇形割集: E’是边割集?E’?IG(v) 例: {(a,g),(a,b)},{(g,a),(g,b),(g,c)},{(c,d)}, {(d,e),(d,f)}, {(a,b),(g,b),(g,c)} * 应用离散数学 第六章 第2讲 * a b c g d f e ??? 关联集: IG(v) = { e | e与v关联 } 割点 割点 点连通度(vertex-connectivity) 点连通度: G是无向连通非完全图, ?(G) = min{ |V’| | V’是G的点割集 } 规定: ?(Kn) = n-1, G非连通: ?(G)=0 例: ?(G)=1, ?(H)=2, ?(F)=3, ?(K5)=4 * 应用离散数学 第六章 第2讲 * G H F 边连通度(edge-connectivity) 边连通度: G是无向连通图, ?(G) = min{ |E’| | E’是G的边割集 } 规定: G非连通: ?(G)=0 例: ?(G)=1, ?(H)=2, ?(F)=3, ?(K5)=4 * 应用离散数学 第六章 第2讲 * G H F k-连通图, k-边连通图 k-连通图(k-connected): ?(G)?k k-边连通图(k-edge-connected): ?(G)?k 例: 彼得森图 ?=3, ?=3; 它是1-连通图, 2-连通图,3-连通图, 但不是4-连通图; 它是1-边连通图, 2-边连通图,3-边连通图,但不是4-边连通图 * 应用离散数学 第六章 第2讲 * 点连通度 边连通度 Whitney定理 定理10: ?????. 证明: 不妨设G是3阶以上连通简单非完全图. (???) 设d(v)=?, 则|IG(v)|=?, IG(v)中一定有边割集E’, 所以??|E’|?|IG(v)|=?. (???) 设E’是边割集,|E’|=?,从V(E’)中找出点割集V’,使得|V’|??, 所以??|V’|??. * 应用离散数学 第六章 第2讲 * ?为图的最小度。 ?为点连通度 ?为边连通度 Whitney定理(续) 证明(续): (???) 设G-E’的2个连通分支是G1,G2. 设u?V(G1),v?V(G2),使得(u,v)?E(G). 如下构造V’’:?e?E’, 选择e的异于u,v的一个端点放入V’’. |V’’|?|E’|. G-V’’?G-E’=G1?G2, u和v在G-V’’中不连通, 所以V’’中含有点割集V’. 所以 ??|V’|?|V’’|?|E’|=?. # * 应用离散数学 第六章 第2讲 * u v 具体的构造策略 引理1 引理1: 设E’是边割集,则p(G-E’)=p(G)+1. 证明: 如果p(G-E’)p(G)+1, 则E’不是边割集, 因为不满足定义中的极小性. # 说明: 点割集无此性质 * 应用离散数学 第六章 第2讲 * 引理2 引理2:设E’是非完全图G的边割集, ?(G)=|E’|,G-E’的2个连通分支是G1,G2,则存在u?V(G1),v?V(G2),使得(u,v)?E(G) 证明: (反证)否则?(G)=|E’| =|V(G1)|?|V(G2)|?|V(G1)|+|V(G2)|-1=n-1, 与G非完全图相矛盾! # 说明: a?1?b?1?(a-1)(b-1)=ab-a-b+1?0 ? ab?a+b-1. * 应用离散数学 第六章 第2讲 * ?为边连通度 任意两点都连同 推论 推论: k-连通图一定是k-边连通图. # * 应用离散数学 第六章 第2讲 * 根据Whitney定理和k-连通图、k-边连通图的概念，可证 自学 有向图的连通性及其分类 可达； 短程线；距离 连通图，强连通图，弱连通图，单向连通图 连通性判别法 * 应用离散数学 第六章 第2讲 * Hassler Whitney(1907~1989) 美国数学家,曾获得Wolf奖 主要研究拓扑学. 20世纪30年代发表了十几篇图论论文,定义了“对偶图”概念,推动了四色定理的研究. 一生的最后20年致力于数学教育,提倡应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技巧和结果. * 应用离散数学 第六章 第2讲 * Whitney的看法 应当让年轻人用自己的直觉(intuition)