Name: Password: Sign in
离散数学 · 图 中的文章

本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

[Lecture 3] 连通性

1 无向图的连通性

1.1 通路

  • (无向图的)通路 (path) :无向图 G 中从 uvn 条边 e1e2en 构成的序列,使得 f(e1)=(x0,x1)f(e2)=(x1,x2)f(en)=(xn1,xn),其中 x0=uxn=v;没有必要区分多重边时可以用顶点序列 x0x1nn 来代表通路
  • 回路 (circuit):若通路中 u=vn>0 则该通路为回路
  • 简单通路:不包含重复边的通路或回路
  • (无向图的)连通性:无向图 G=(V,E) 中任意一对顶点存在通路,那么称 G 是连通的

定理 1:连通图每一对点间包含简单通路

要证明该定理可以考虑反证法,由于任意两点间必然存在通路,uv 间必然存在一条最短通路

x0,x1...xi,xi+1...xj...xn

假设它不是简单通路,那么通过删除该序列中 xi,xi+1...xj 所对应的边可以得到一条更短的通路,因而定理得证

1.2 连通分支

不连通的图是 nn2)个连通图的并,这些不相连通的子图即 连通分支

下图中 H1H2H3 即为 H 的连通分支

证明:一个图含有两个奇度顶点一定连通

使用反证法。假设图 G 含有两个奇度顶点 uv 不连通,那么存在 uv 分别在不同的连通分支 G1G2 上,又 G1G2 只包含一个奇度顶点,与 握手定理 矛盾。因而命题得证

1.3 割点与割边

  • 割点:删除一个顶点与它所关联的边可以得到更多的连通分支,那么这样的点为 割点
  • 割边(桥):删除一条边会得到更多的连通分支,那么这样的边即 割边

例如下图有割点 bce,割边 (a,b)(c,e)

2 有向图的连通性

  • 强连通:有向图中每一对顶点 uv 间既有从 uv 的通路也有 vu 的通路,那么该图是强连通的
  • 弱连通:有向图中每一对顶点 uv 存在通路,即弱连通忽略了连通的方向

例如下图中 G 是强连通的,而对于 H,没有从 a 到其他点的通路,因而是弱连通的

  • 极大强连通子图(强连通分支,强分支):有向图 G 的子图是强连通的,且不包含于更大的强连通子图中

3 通路与同构

3.1 简单回路的存在性

长度为 kk2) 的简单回路的存在性是一个不变量,可以用来帮助判定图的同构

上图中,GH 都有 2 个 2 度顶点,4 个 3 度顶点,H 存在长度为 3 的简单回路

v1,v6,v2,v1

G 不存在,因而 GH 不同构

3.2 连通数

连通数 即一个图中两个顶点通路的数目,可由邻接矩阵确定

定理 2:设 G 是带有相对于顶点顺序 v1v2vn 的邻接矩阵 A 的图,从 vivj 长度为 r 的不同通路的数目为 Ar 的第 (i,j) 项,其中 r 是正整数

Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号