PDF《图的连通性》

图的连通性

1 回顾 ? 图的定义 ? 用图建模 ? 图的表示 ? 图的运算 ? 图的同构

2 ? 通路与回路 ? 无向图的连通性 ? 连通度 ? 2-连通图 ? 有向图的连通性 ? 无向图的定向

3 提要 ? 定义:图G中从v0到vn的长度为n的通路是G的n条边 e1,…, en的序列,满足下列性质 ? 存在vi?V (0?i?n), 使得vi-1和vi是ei的两个端点 (1?i?n).

? 相关点 ? 回路:起点与终点相同,长度大于0. ? 不必区分多重边时,可以用相应顶点的序列表示通路. ? 长度为0的通路由单个顶点组成. ? 简单通路:边不重复,即,?i, j, i?j ? ei?ej ? 初级通路:点不重复,亦称为 路径

4 通路的定义 ? 简单通路:a, d, c, f, e. 长度为4. ? 回路:b, c, f, e, b.长度为4. ? 通路:a, b, e, d, a, b. 长度为5. ? 不是通路:d, e, c, b.

5 c b a f e d 通路(举例) ? 定义:有向图G中从v0到vn的长度为n的通路是G的n条边e1,…, en的序列,满足下列性质 ? 存在vi?V (0?i?n), 使得vi-1和vi分别是ei的起点和终点 (1?i?n). ? 相关点 ? 回路:起点与终点相同,长度大于0. ? 不必区分多重边时,可以用相应顶点的序列表示通路. ? 长度为0的通路由单个顶点组成. ? 简单通路: 边不重复,即,?i, j, i?j ? ei?ej ? 初级通路:点不重复

6 通路的定义(有向图) ? 简单通路:v1, v4, v2, v3. 长度为3. ? 回路: v2, v1, v4, v2.长度为3. ? 通路: v2, v3, v1, v4, v2, v3 . 长度为5.

7 v1 v2 v3 v4 通路(举例) ? 设图G的邻接矩阵为A ? (Ak)i,j: vi到vj的长度为k的通路个数 ? (Ak)i,i: vi到vi的长度为k的回路个数 ? 同构图的不变量:长度为k的回路的存在性.

8 通路与同构

9 u6 u2 u1 u5 u3 u4 v6 v2 v1 v5 v3 v4 u2 u5 u1 u3 u4 v2 v5 v1 v3 v4 通路与同构 ? 定义:无向图G称为是连通的,如果G中任意两个不 同顶点之间都有通路.

10 a c b e d a c b e d G1 G2 无向图的连通性 ? 连通分支 ? 极大连通子图 ? 每个无向图是若干个互不相交的连通分支的并. ? 顶点之间存在通路 是一个等价关系,任一等价类上 的导出子图即为一个连通分支. ? 若图G中存在从u到v的通路,则一定有从u到v的简 单通路. ? 证明:最短通路必是简单的,事实上,它没有重复顶点.

11 连通分支 ? 设p(G)表示图G中连通分支数 ? p(G-v)(其中v是G中任意一个顶点)的情况比较复杂 (注意:删除顶点意味着同时删除该点关联的边) ? 连通分支的数量可能会…… ? 减少 (删除孤立点) ? 不变 (例如:删除悬挂点) ? 增加很多个 (例如:star)

12 (孤立点) (悬挂点) 点的删除与连通分支数量的增减 割点(cut vertex, articulation vertex) ? 定义:G是图, v∈VG, 若p(G-v)>

p(G), 则称v是割点 (注意:只需考虑割点所在的连通分支,以下讨论不妨只 考虑连通图)

13 割点 ? 以下三个命题等价: (1) v是割点. (2) 存在V-{v}的分划{V1, V2}, 使?u∈V1, w∈V2, uw-通路均包含v. (3) 存在顶点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 是割点.

14 关于割点的三个等价命题 边的删除与连通分支数量的增加 ? 设p(G)表示图G中连通分支数,则: p(G)? p(G-e) ? p(G)+1, 其中e是G中任意一条边 ? 第一个 不大于 显然成立(删除e只会影响e所在的那一个 连通分支). ? 第二个 不大于 成立: 注意在图中任意两点之间 加一条边,最多只能将两个连通分支连成一个.

15 ? 定义:设G是图,e∈EG, 若p(G-e)>

p(G), 则称e是G中 的割边. (注意:只需考虑割边所在的连通分支,以下讨论不妨只考虑连 通图)

16 割边 割边(桥;

cut edge, bridge) ? 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中的简单回路,矛盾.

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

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

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

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

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

21 例?W6(轮):?=?=3 =? ? C6(圈):?=?=2 =? ? K2,3(完全二部图):?=?=2 =? ? G:?=1,?=2,?=3

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

23 关于连通度的定理(续)

24 dG(v) ≤ |F| 关于连通度的定理(续) ? 若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.

25 例?设G是简单图,|G|=n?3, 且?G?n-2, 则?(G)=?G (注意:任一点最多与一个点不相邻,此时?(G)也必为?G) ? 证明:设V'

?VG是使得G不连通的最小点集, 不妨设G1为G-V'

得到的连通分支中最小的那个,则有|G1|?(n-|V'

|)/2.

26 ? |G1| ? ?G ? ?v∈G1d(v)? |G1|?(|G1| -1)+ |G1| ? |V'

| ? ?G ? |G1| -1+ |V'

| ? (n-|V'

|)/2 + |V'

| -1 ? 2?G ? n-2 + |V'

|? ?G+ |V'

| , 所以 |V'

| ??G 即?(G) ? ?G G1 V'

G2 Whitney定理 (现象:对图G中任意两点u,v, 如果点不相交的uv-通路有k条,显然,要使u,v不连通, 至少须删除k个顶点.) ? Whitney定理: 图G(|G|?3)是2-连通图 当且仅当 G中任意两点被至少2条 除端点外顶点不相交的路径所连接. 注: G中任意两点被至少2条除端点外顶点不相交的路径所连接 等价 于 任意两点均处在同一初级回路中 .

27 ? ?显然 ? ?:设u,v是图G中的任意两点.下面对距离d(u,v)进行归纳. 当d(u,v)=1, uv?EG, 因为G是2-连通图,G-uv仍连通,则G中除边uv外, 必有另一条不含uv的路径. 假设当d(u,v)........