21-图连通性070101.ppt

图的连通性 信号处理中的数学方法 第2-3讲 上一讲内容的回顾 通路与回路 连通与连通图 扩大路径证明法 最短通路问题与Dijstra算法 图的连通性 割点 割边(桥) (点)连通度 边连通度 Whitney定理 边的删除与连通分支数量的增加 设?(G)表示图G中连通分支数，则： ?(G)? ?(G-e) ? ?(G)+1, 其中e是G中任意一条边 第一个“不大于”显然成立(删除e只会影响e所在的那一个连通分支)。 第二个“不大于”成立: 注意在图中任意两点之间加一条边，最多只能将两个 连通分支连成一个。因此假设删除某条边会使连通分支增加不止一个，考虑再将该边添回去将导致矛盾。 点的删除与连通分支数量的增减 ?(G-v) (其中v是G中任意一个顶点)的情况比较复杂 （注：删除顶点意味着同时删除该点关联的边） 图的连通分支数 可能会…… 减少 (删除孤立点) 不变 (例如：删除悬挂点) 增加任意 有限多个 (例如：star) （孤立点） （悬挂点） 割点 定义：G是图，v∈VG, 若?(G-v)?(G), 则称v是割点 (注意：只需考虑割点所在的连通分支，以下讨论不妨只考虑连通图) 割点 关于割点的三个等价命题 以下三个命题等价： v是割点。 存在V-{v}的分划{V1, V2}, 使?u∈V1, w∈V2, uw-通路均包含v。 存在顶点u,w(u≠v, w≠v)，使得任意的uw-通路均包含v。 证明：(略) (1)?(2): ∵v是割点，G-v至少存在两个连通分支，设其中一个的顶点集是V1。令V2=V-(V1∪{v}), 则?u∈V1, w∈V2, u,w一定在G-v的不同的连通分支中。∴在G中，任何uw-通路必含v。 (2)?(3): 注意：(3)是(2)的特例。 (3)?(1): 显然，在G-v中已不可能还有uw-通路，∴G-v不连通，∴v是割点。 割边 定义：设 G是图，e∈EG, 若 ?(G-e) ?(G), 则称 e 是G中的割边。 (注：只需考虑割边所在的连通分支，以下讨论不妨只考虑连通图) 割边 有关割边的四个等价命题 以下四个命题等价： (1) e是割边。 (2) e不在G的任一简单回路上。(注：割点没有相应结论) (3) 存在V的分划{V1, V2}, 使得?u∈V1, w∈V2, uw-通路均包含e。 (4) 存在顶点u,w，使得任意的uw-通路均包含e。 证明： (1)?(2): 假设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是割边矛盾。 (2)?(1): 假设e=xy不是割边。则G-e仍连通，设P是G-e中的xy-路径，P中不含e, 则：P+e是G中的简单回路，矛盾。 连通图“连接的牢度”不一样 图a中删除任意一条边都不连通了。 图b则至少删除两条边，或删除当中那个顶点才不连通 图c删除任意一个点都不可能不连通。 图d少要删除四条边才可能不连通，且不可能通过删除顶点使其不连通。 (a) (d ) (c ) (b ) 图的连通度 (注：若G是顶点数不少于2的非完全连通图，删除 足够数量 的点一定能使图成为不连通图或者平凡图。) 定义：使非平凡连通图G成为不连通图或者平凡图 需要删除的最少顶点数称为图G的(点)连通度，记为κ(G)。(注意：这不意味着任意删除κ(G)个点就一定会使该图不连通) 约定：不连通图或者平凡图的连通度为0。 若图G的连通度不小于 k, 则称G是k-连通图； (也就是说：连通度为k 图是1-, 2-, 3-,...,(k-1)-连通图，或者说：对k-连通图，如果删除少于k个顶点，它一定还连通。) 图边连通度 (注：若G是顶点数不少于2的非完全连通图，删除足够数量 的边一定能使图成为不连通图。) 类似地，使非平凡连通图G成为不连通图 需要删除的最少 边数称为图G的边连通度。记为?(G)。 (注：这不意味着 任意 删除 ?(G)个点就一定会使该图不连通) 约定：不连通图或者平凡图的边连通度为0。 若图G的边连通度不小于 k, 则称G是k-边连通图。 (也就是说：边连通度为 k 图是1-, 2-, 3-,...,(k-1)-连通图，或者说：对k-边连通图，如果删除少于k条边，它一定还连通。) 关于连通度的例子 W6(轮)：?=?=3 =? C6(圈)：?=?=2 =? K2,3(二分完全图)：?=?=2 =? G：?=1，?=2，?=3 这里?