PDF《图的连通性》

14 割边(桥;

cut edge, bridge) ? 定义:设G是图,e∈EG, 若p(G-e)>p(G), 则称e是G 中的割边. (注意:只需考虑割边所在的连通分支,以下讨论不妨只考虑连 通图)

15 割边 割边与回路 ? e是割边当且仅当e不在G的任一简单回路上.(注意: 割点没有相应结论) ? 证明: ?: 假设C是包含e=xy的初级回路, 令C-e=P, P是不含e的xy-路径. 对G中任意顶点u,v, 若uv-通路中不含e, 则该通路也是G-e中的 uv-通路;

若uv-通路中含e, 则将所有的e均替换为P,得到G-e 中的uv-通路,∴G-e仍连通,与e是割边矛盾. ?: 假设e=xy不是割边.则G-e仍连通,设P是G-e中的xy-路径, P中不含e, 则:P+e是G中的简单回路,矛盾.

16 有关割边的四个等价命题 ? 以下四个命题等价: (1) e是割边. (2) e不在G的任一简单回路上.(注意:割点没有相应结论) (3) 存在V的分划{V1, V2}, 使得?u∈V1, w∈V2, uw-通路均 包含e. (4) 存在顶点u,w,使得任意的uw-通路均包含e.

17 连通图"连接的牢固度"不一样 ? 图G1中删除任意一条边都不连通了. ? 图G2则至少删除两条边,或删除中间那个顶点,才不连通. ? 图G3删除任意一个点依然连通. ? 图G4至少要删除四条边才可能不连通,且不可能通过删除 顶点使其不连通.

18 G4 G3 G2 G1 图的(点)连通度 (注意:若G是顶点数不少于2的非完全图,删除足够数量的 点一定能使图变成不连通图或者平凡图.) ? 定义:使非平凡连通图G成为不连通图或者平凡图需要 删除的最少顶点数称为图G的(点)连通度,记为κ(G). (注意:这不意味着任意删除κ(G)个点就一定会使该图不连通) ? 约定:不连通图或平凡图的连通度为0,而κ(Kn)=n-1 ? 若图G的连通度不小于 k, 则称G是k-连通图;

(k-连通图,即κ(G)?k:删除少于k个顶点,它依然连通.) ( κ(G)=k: k-连通图,且有k个顶点,删除它们就不连通.)

19 图的边连通度 (注意:若G是顶点数不少于2的连通图,删除足够数量的边 使得图变成不连通.) ? 类似地,使非平凡连通图G变成不连通 需要删除的最 少边数称为图G的边连通度.记为?(G). (注意:这不意味 着任意删除?(G)条边就一定会使该图不连通) 约定:不连通图或平凡图的边连通度为0.?(Kn)=n-1 若图G的边连通度不小于k, 则称G是k-边连通图. (k-边连通图,即?(G) ?k:删除少于k条边,它依然连通.) (?(G) =k: k-边连通图,且有k条边,删除它们就不连通.)

20 关于连通度的例子 ? W6(轮):?=?=3 =? ? C6(圈):?=?=2 =? ? K2,3(完全二部图):?=?=2 =? ? G:?=1,?=2,?=3

21 ?表示图中最小顶点度 K2,3 G C6 W6

22 连通度的上限(续) ? 若图G是非平凡的, 则?(G)? ?(G) ? ?(G) ? 易证λ(G) ? ?(G).设F为E的极小子集使得G-F不连 通,只需证明κ(G)≤ |F|. ? 若G中存在不与F中的边相关联的点,设为v.令C 为G-F中v所在的连通分支.F中的任一边,其两个 端点不会都在C中(F的极小性).C中与F中边相 关联的顶点(集合)分隔v与G-C,κ(G)≤|F|.

23 连通度的上限(续) ? 若G中的各顶点均和F中的某条边关联.对任意顶点 v,令C是G-F中包含v的连通分支.考虑v的任一邻居 w.若w在C中,则w必定和F中的某条边关联;

若w 在G-C中,则边vw属于F.因此,|N(v)| ≤ |F|, 即dG(v) ≤ |F|. ? 若V-N(v)-v≠Ф, 则删除N(v)后, v和V-N(v)-v不连通,从而κ(G)≤ |F|. ? 若V-N(v)-v=Ф,则取其它节点以满足1)的条件.若所 有节点均有V-N(u)-u=Ф,则图G为完全图,有κ(G)=λ(G)=|G|-1.

24 连通度的上限(续) dG(v) ≤ |F| 达到连通度上限的图 ? 设G是简单图,|G|=n?3, 且?G?n-2, 则?(G)=?G (注意:任一点最多与一个点不相邻,此时?(G)也必为?G) ? 证明:设V'?VG, 使得G-V'含两个连通分支G1, G2, 不妨设 |G1|?|G2|,则|G1|?(n-|V'|)/2.