离散数学─图论初步 南京大学计算机科学与技术系

Presentation on theme: "离散数学─图论初步 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─图论初步 南京大学计算机科学与技术系
图的连通性 离散数学─图论初步 南京大学计算机科学与技术系

2 内容提要 通路与回路 通路与同构 无向图的连通性 连通度 2-连通图 有向图的连通性 无向图的定向

3 通路的定义 定义：图G中从v0到vn的长度为n的通路是G的n条边e1,…, en的序列，满足下列性质 相关点
存在viV，使得vi-1和vi是ei的两个端点 (1in)。 相关点 长度为0的通路由单个顶点组成。 不必区分多重边时，可以用相应顶点的序列表示通路。 回路：起点与终点相同，长度大于0。 简单通路： 边不重复，即，i, j, ij  eiej

4 通路（举例） 简单通路：a, d, c, f, e。 长度为4。 通路：a, b, e, d, a, b。 长度为5。
回路：b, c, f, e, b。长度为4。 不是通路：d, e, c, b。

5 通路的定义（有向图） 定义：有向图G中从v0到vn的长度为n的通路是G的n条边e1,…, en的序列，满足下列性质 相关点
存在viV ，使得vi-1和vi分别是ei的起点和终点 (1in)。 相关点 长度为0的通路由单个顶点组成。 不必区分多重边时，可以用相应顶点的序列表示通路。 回路：起点与终点相同，长度大于0。 简单通路： 边不重复，即，i, j, ij  eiej

6 通路（举例） v1 v2 v3 v4 简单通路：v1, v4, v2, v3。 长度为3。

7 通路与同构 设图G的邻接矩阵为A 同构图的不变量：长度为k的回路的存在性。 (Ak)i,j: vi到vj的长度为k的通路个数(k1)
(Ak)i,i: vi到vi的长度为k的回路个数(k1) 同构图的不变量：长度为k的回路的存在性。 B=UAU-1  Bk=UAkU-1（对角线元素之和相等？）

8 通路与同构 u6 u2 u1 u5 u3 u4 v6 v2 v1 v5 v3 v4 u2 u5 u1 u3 u4 v2 v5 v1 v3

9 无向图的连通性 定义：无向图G称为是连通的，如果G中任意两个不同顶点之间都有通路。 a c b e d a c b e d G2 G1

10 连通分支 连通分支 每个无向图是若干个互不相交的连通分支的并。 若图G中存在从u到v的通路，则一定有从u到v的简单通路。 极大连通子图
“顶点之间存在通路”是一个等价关系，任一等价类上的导出子图即为一个连通分支。 若图G中存在从u到v的通路，则一定有从u到v的简单通路。 证明：最短通路必是简单的，事实上，它没有重复顶点。

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

12 割点 定义：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中任意一条边
删除一条边，不会减少连通分支，最多增加一个； 增加一条边，最多只能将两个连通分支连成一个。

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

16 割边与回路 e是割边当且仅当e不在G的任一简单回路上。(注意：割点没有相应结论) 证明：  假设e在某个简单回路C上。易证： 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则至少删除两条边，或删除中间那个顶点，才不连通。

19 (k-连通图，即 κ(G)k：删除少于k个顶点，它依然连通。) ( κ(G)=k： k-连通图，且存在k个顶点，删除它们就不连通。)
图的(点)连通度 (注意：若G是顶点数不少于2的非完全图，删除足够数量的点一定能使图变成不连通图或者平凡图。) 定义：使非平凡连通图G成为不连通图或者平凡图需要 删除的最少顶点数称为图G的(点)连通度，记为κ(G)。 (注意：这不意味着任意删除κ(G)个点就一定会使该图不连通) 约定：不连通图或平凡图的连通度为0，而κ(Kn)=n-1 若图G的连通度不小于k, 则称G是k-连通图； (k-连通图，即 κ(G)k：删除少于k个顶点，它依然连通。) ( κ(G)=k： k-连通图，且存在k个顶点，删除它们就不连通。)

20 图的边连通度 类似地，使非平凡连通图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 表示图中最小顶点度 C6 G W6 K2,3

22 连通度的上限（续） 设G=(V, E)是非平凡的简单图, 则 (G) (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 连通度的上限（续） dG(v) ≤ |F|

24 连通度的上限（续） 若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
证明：设V’VG, 使得G-V’含两个连通分支G1, G2, 不妨设|G1||G2|，则|G1|(n-|V’|)/2。 G1 V’ G2 |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

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

27 Whitney定理的证明 显然 :设u,v是图G中的任意两点。下面对距离d(u,v)进行归纳。
当d(u,v)=1, uvEG, 因为G是2-连通图，G-uv仍连通，则G中除边uv外，必有另一条不含uv的路径。 假设当d(u,v)<k时，至少存在两条中间点不相交的通路。 若d(u,v)=k, 设u,v间的一条最短路径是u…wv, w是与v相邻的顶点。则d(u,w)<k, 由归纳假设u,w之间存在两条中间点不相交的路径，设为P, Q。因为G是2-连通图，G-w中仍有(不含w的)uv-路径P’，且它一定与P, Q有公共点(u就是一个)。 假设这样的公共点中距离v最近的 是x(不妨假设它在P上)，则Q+wv 边以及P上的ux-段+P’上的xv-段是 u,v之间两条中间点不相交的通路。 P x v u w Q

28 连通性的一般性质 Menger定理（Whitney定理的推广）
图G是k-连通图 当且仅当 G中任意两点被至少k条除端点外顶点不相交的路径所连接。 图G是k-边连通图 当且仅当 G中任意两点被至少k条边不相交的路径所连接。

29 2-连通图 命题. 一个图是2-连通的  它是一个回路(cycle), 或者在H(已有的2-连通图)上依次增加 H-path.

30 2-连通图 证明. 充分条件显然成立. 下证必要条件.
设G是2-连通的. G 必包含回路C, 设 H 是包含C，依次增加H-Path得到的极大子图. H必是G的导出子图. 倘若H  G, 则存在vG-H, wH, vwG. G是 2-连通的, G-w连通, v到H有路径P, wvP是H-Path, 矛盾. v w H

31 2-连通图

32 有向图的连通性 若将有向图D各边的方向去掉，所得的无向图(称为D的底图)连通，则D称为弱连通有向图。(见下右图: 既无uv-, 又无vu- 有向通路) u,vVD,存在一条 (u,v)-有向通路或者(v,u)-有向通路，则D称为单连通有向图。 (见下中图: 有uv-, 但无vu-有向通路) u,vVD,均存在 (u,v)-有向通路和(v,u)-有向通路，则D称为强连通有向图。 (见下左图) v u

33 强连通的充分必要条件 有向图D是强连通的当且仅当D中的所有顶点在同一个有向回路上。 证明：  显然
 设VD={v1,v2,…,vn}，令i是vi到vi+1的有向通路(i=1,…,n-1)，令n是vn到v1的有向通路，则1，2,…n依次连接是包含D中一切顶点的回路。

34 单向连通图中处处可达的顶点 若有向图D是单向连通，则非空集V'VD, v’V', 使得v'可达V'中的所有顶点(规定顶点到其自身是可达的)。 注意：当V '足够小，上述条件一定成立。 证明：（注意：按照非空子集的大小进行归纳证明） V’ ?

35 单向连通的充分必要条件 有向图D是单向连通的当且仅当D中的所有顶点在同一个有向通路上。 充分性显然，下面证明必要性
设VD={v1,v2,…vn}, 令V1=VD, 则V1中存在可达所有顶点 的顶点，不妨假设它就是v1, 令Vi+1=Vi-{vi}，其中 i=1,2,…,n-1; 而且诸Vi中均有可达该子集中所有顶点的 顶点(不妨假设其就是vi), 于是：将诸vivi+1-通路连接起 来即包含D中所有顶点的有向通路。

36 无向图的边定向 问题：何种道路网可以用规定单行道的办法来改善交通？ 在图模型中，该问题表述为：什么样的无向图G可通过边定向成强连通有向图 .

37 2-边连通与2-连通（无向图） v3 v2 v1

38 2-边连通无向图的边定向 2-边连通图中一定含回路 P v1 C1 Q
构作有向通路C2=C1+QP,..., 总会得到包括图中所有点的强连通有向图。仍未包括的边可以任意定向。

39 无向图边定向算法 输入：无自环2-边连通无向图G （设VG={v1,v2,…,vn}） 输出：以G为底图的强连通有向图 过程：
(1) 令V1={v1}, i=1。 (2) 若Vi=VG, 对未定向边任意定向，算法结束。否则转3。 (3) 取边 , 使得 (一定可取到所要的边)。 从 开始找一条初级通路或回路，满足始点和终点在Vi中，而中间点均在VG-Vi中, 加方向使之成为有向通路。 (4) Vi+1=Vi ⋃ {上述通路或回路中所有中间点}，转2。

40 无向图边定向算法(续) 示例 d f g e a b c h j i

41 作业 教材[9.4] 补充 p. 485：12, 20, 53, 56 试找出一个图G，满足： =n-3, 而(G)<。
【已知：若G是简单图，|G|=n3, 且Gn-2, 则(G)=G】 G是2-边连通图 当且仅当 G中任意两个顶点之间至少有两条不含公共边的通路。 若G是k-边连通图，从G中任意删除k条边，最多得到2个连通分支。

42 参考文献 1. 高随祥. 《图论与网络流理论》，高等教育出版社
2. Reinhard Diestel. Graph Theory. Springer, Heidelberg, (Section 1.3 and section 3.1)