新型图论第3章.pptVIP

第三章 图的连通度;§3.1 割边、割点和块;定理1 e是图G的割边当且仅当e不在G的任何圈中。;推论 设e是连通图G的任意一条边，若e含在G的某圈中，则G-e仍连通。;说明：(1) 若ω(G-v)＞ω(G), 则 v 必为G 的割点；;证明 必要性 因v是G的割点，故G-v至少含两个连通分支，设V1是其中一个连通分支的顶点集，V2为其余分支的顶点集。对x∈V1，y∈V2，因在G-v中x与y不连通，而在G中x与y连通（因 G连通）所以v在每一条 (x, y) 路上。;例 图G如图（a）所示，G的所有块如图（b）所示。;定理4 设图G的阶至少为3，则G是块当且仅当G无环并且任意两点都位于同一个圈上。;设对满足d(u,v) k的任意两点u和v结论成立。;这样，x 将 C 划分为两条 (u, x) 路 P1 和P2，不妨设 w 在P2 上，如下图所示。;推论 设G的阶至少为3，则G是块当且仅当G无孤立点且任意两条边都在同一个圈上。;§3.2 连通度;所以 V’ 是2顶点割; 同时, v5 , v6 是割点。;定义2 对n阶连通图G，若G存在顶点割，则称G的最小顶点割中的点数为G的连通度；否则称n-1为其连通度。G的连通度记为κ(G)，简记为κ；对非连通图G定义κ(G) = 0。;若一个图的连通度至少为k，则称该图是k连通的。于是，非平凡连通图均是1连通的；图G是2连通的当且仅当 G 连通、无割点且至少含有3个点。; e1 e2 G1 G2 G3 G4;若一个图的边连通度至少为k，我们也称该图是k边连通的。易知, 非平凡连通图均是1边连通的; 图G是2边连通的当且仅当G连通、无割边且至少含有两个点。;当λ(G) =1时，κ(G) =λ(G) =1。;κ(G)≤|V(G)|-1= | S | +1≤k;定理7 设G是具有 m条边的n阶连通图，则 κ≤;证明 若G 不连通，则G至少有两个连通分支，从而必有一个分支H 满足 |V(H)|≤ 。;证明 任意删去G中k-1个点，记所得之图为H，则; 有关图的连通性的一个基本的也是十分重要的结果是由门格尔（Menger）于1927年所得到。该定理首先揭示了图的连通度与顶点间的不相交路的数目之间的关系。;（2） 设x和y是图G中的两个不同点，则G中分离x和y的最少边数等于边不重的(x, y) 路的最大数目。;推论1 对k≥2，图G 是 k 连通的当且仅当G 至少有k+1个点并且G 中任意两个不同顶点间均存在 k 条内部不相交的路；G是 k 边连通的当且仅当G 至少有 k 个点并且G 任意两个不同顶点间均存在 k 条边不重的路。; 若 x 与 y 相邻，则删去连接 x 与 y 的边之后所得的图G′的连通度至少为 k-1，从而G′中分离 x 与 y 至少需 k-1个点，于是由定理10，G′中存在 k-1 条独立的 (x, y) 路，这k-1条独立的 (x, y) 路连同 xy 便是 G 中 k 条独立的 (x, y) 路。;一个通讯网络可模型化为一个图，图中的点代表通讯站，边代表通讯线。这样，图的点（边）连通度对应了网络中容许失灵的通讯站（线）数目的一个界限。即图的连通度对应系统的可靠性。;说明：(1) 对k =1，此问题即为求最优树的问题；;Hk,n的构造:;情况3. k = 2r +1，n为奇。先作H 2r, n ，再添加边 0 － ,;§3.4 图的宽距离宽直径简介;若一个网络是k连通的，则可保证在任意两点之间，数据可以沿着k条互不干扰的路平行地传输。;宽直径的相关概念;定义2 设x, y ∈V(G), 定义x与y间所有宽度为w的容器的长度的最小值d w( x , y)为x与y间w宽距离，即：;定义3 设G是w连通的，G的所有点对间的w宽距离的最大值，称为G的w宽直径，记为d w (G)。即：; 解: (1) n点圈Cn的宽直径。;对于任意的 w(2≦w≦n-1), 任意点对间的w宽距离为2。;定理1 对于任意连通图G，若图G的w直径存在，则：;Thank you!