PDF《图的连通性》

图的连通性 离散数学图论初步 南京大学计算机科学与技术系 内容提要 ? 通路与回路 ? 通路与同构 ? 无向图的连通性 ? 连通度 ? 2-连通图 ? 有向图的连通性 ? 无向图的定向

2 通路的定义 ? 定义:图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 ? 初级通路:点不重复,亦称为"路径"

3 通路(举例) ? 简单通路:a, d, c, f, e. 长度为4. ? 回路:b, c, f, e, b.长度为4. ? 通路:a, b, e, d, a, b. 长度为5. ? 不是通路:d, e, c, b.

4 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

5 通路(举例) ? 简单通路:v1, v4, v2, v3. 长度为3. ? 回路: v2, v1, v4, v2.长度为3. ? 通路: v2, v3, v1, v4, v2, v3 . 长度为5.

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

7 通路与同构

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

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

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

11 (孤立点) (悬挂点) 割点(cut vertex, articulation vertex) ? 定义:G是图, v∈VG, 若p(G-v)>p(G), 则称v是割点 (注意:只需考虑割点所在的连通分支,以下讨论不妨只 考虑连通图)

12 割点 关于割点的三个等价命题 ? 以下三个命题等价: (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是割点.

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