图的连通性基本概念

Published on 2016 - 06 - 22

连通图与非连通图

如果无向图G中任意一对顶点都是连通的,则称此图是连通图(Connected Graph);相反,如果一个无向图不是连通图,则称为非连通图(Disconnected Graph)。对非连通图G,其极大连通子图称为连通分量(Connected Component,连通分支),连通分支数记为w(G)。

当无向图为非连通图时,从图中某一顶点出发,利用深度优先搜索或广度优先搜索算法不可能遍历到图中的所有顶点,只能访问到该顶点所在的极大连通子图(即连通分量)中的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历,就可以访问到所有顶点。

例如,图1(a)所示的非连通无向图包含两个连通分量:顶点A、B、C和E组成的连通分量,顶点D、F、G和H组成的连通分量。对该图进行DFS遍历时,从顶点A出发可以遍历到第1个连通分量上的各个顶点,从顶点D出发可以遍历到第2个连通分量上的各个顶点,其DFS遍历过程如图1(b)所示。

在用程序实现中,需要对无向图的每一个顶点进行检测:若已被访问过,则该顶点一定是落在图中已求得的连通分量上;若还未被访问,则从该顶点出发遍历,可求得图的另一个连通分量。

假设用邻接矩阵存储图(设顶点个数为n),下面的伪代码从每个未访问过的顶点出发进行DFS搜索,可以遍历到所有顶点,并可以求得连通分量的个数。

观察图2所示的一些无向图。尽管这些无向图都是连通图,但其中某些图看起来比其他图“更为连通”,而某些图的连通性是如此“脆弱”,以至于移去某个顶点或某条边就导致图不连通。这意味着有必要引入一些能反映无向连通图连通程度的量,即顶点连通度与边连通度。

无向图的点连通性

所谓点连通性(Vertex Connectivity),就是与顶点有关的连通性。研究无向图的点连通性,通常是通过删除无向图中的顶点(及与其所关联的每条边)后,观察和分析剩下的无向图连通与否。

割顶集与顶点连通度

关于割顶集和顶点连通度有如下两种定义方式。

  • 方式一:设V′是连通图G的一个顶点子集,在G中删去V′及与V′关联的边后图不连通,则称V′是G的割顶集(Vertex-cut Set)。如果割顶集V′的任何真子集都不是割顶集,则称V′为极小割顶集。顶点个数最小的极小割顶集称为最小割顶集。最小割顶集中顶点的个数,称作图G的顶点连通度(Vertex Connectivity Degree),记做κ(G),且称图G是κ-连通图(κ-Connected Graph)
  • 方式二:设连通图G的阶数为n,去掉G的任意k-1个顶点(及相关联的边)后(1≤k≤n),所得到的子图仍然连通,而去掉某k个顶点(及所关联的边)后的子图不连通,则称G是κ-连通图,k称作图G的顶点连通度,记做κ(G)。

如果割顶集中只有一个顶点,则该顶点可以称为割点(Cut-Vertex)或关节点

规定,对n阶完全图Kn,κ(Kn)=n-1;对非连通图和平凡图,κ(G)=0。

如图3(a)所示的连通图,删除任意一个顶点(或两个顶点)都不会使剩下的子图不连通,而删除某3个顶点,就能使得剩下的子图不连通。例如,删除顶点子集{v2,v6,v8}及其所关联的边(在图3(a)中用粗线标明),剩下的子图如图3(b)所示,为非连通图。因此原图的顶点连通度κ(G)=3,该图是3-连通图。

关节点的另外一种定义方式:在一个无向连通图G中,当删去G中的某个顶点v及其所关联的边后,可将图分割成2个或2个以上的连通分量,则称顶点v为割点,或者称为关节点。例如图4(a)所示的无向连通图中,顶点5,4,6,8都是关节点。

点双连通图与点双连通分量

点双连通图:如果一个无向连通图G没有关节点,或者说点连通度κ(G)>1,则称G为点双连通图,或者称为重连通图

为什么称为点双连通图呢?因为在这种图中任何一对顶点之间至少存在2条无公共内部顶点(即除起点和终点外的顶点,n≥3)的路径,在删去某个顶点及其所关联的边时,也不会破坏图的连通性。例如,图3(a)中,顶点v1和v4之间存在3条无公共内部顶点的路径:(v1,v2,v3,v4)、(v1,v5,v6,v7,v4)和(v1,v8,v9,v10,v4)。

在一个表示通信网络的连通图中是不希望存在关节点的。在这种图中,用顶点表示通信站点,用边表示通信链路。如果一个通信站点是关节点,它一旦出现故障,将导致其他站点之间的通信中断。如果通信网络是点双连通图,那么某个站点一旦出现故障,也不会破坏图的连通性,整个系统还能正常运行。

点双连通分量:一个连通图G如果不是点双连通图,那么它可以包括几个点双连通分量,也称为重连通分量(或块)。一个连通图的重连通分量是该图的极大重连通子图,在重连通分量中不存在关节点。例如图4(a)所示的连通无向图包含6个重连通分量,如图4(b)所示。从图4(b)可以看出,割点可以属于多个重连通分量,其余顶点属于且只属于一个重连通分量。

无向图的边连通性

所谓边连通性(Edge Connectivity),就是与边有关的连通性。研究无向图的边连通性,通常是通过删除无向图中的若干条边后,观察和分析剩下的无向图连通与否。

割边集与边连通度

与割顶集和顶点连通度类似,割边集和边连通度也有如下两种定义方式。

  • 方式一:设E′是连通图G的边集的子集,在G中删去E′后图不连通,则称E′是G的割边集(Edge-Cut Set)。如果割边集E′的任何真子集都不是割边集,则称E′为极小割边集。边数最小的极小割边集称为最小割边集。最小割边集中边的个数,称作图G的边连通度(Edge Connectivity Degree),记做λ(G),且称图G是λ-边连通图(λ-Edge-Connected Graph)
  • 方式二:设连通图G的边数为m,去掉G的任意λ-1条边后(1≤λ≤m),所得到的子图仍然连通,而去掉某λ条边后得到的子图不连通,则称G是λ-边连通图,λ称作图G的边连通度,记作λ(G)。

如果割边集中只有一条边,则该边可以称为割边(Bridge)或桥

如图5(a)所示的连通图,删除任意一条边(或两条边)都不会使剩下的子图不连通,而删除某3条边,就能使得剩下的子图不连通。例如,删除边子集{(v2,v3),(v5,v6),(v8,v9)},剩下的子图如图5(b)所示,为非连通图,因此原图的边连通度λ(G)=3,该图是3-边连通图。

割边同样也有另外一种定义方式:在一个无向连通图G中,当删去G中的某条边e后,可将图分割成两个或两个以上的连通分量,则称边e为割边,或者称为桥。例如图4(a)所示的无向连通图中,边(v1,v5)、(v4,v6)、(v8,v9)和(v8,v10)都是割边。

边双连通图与边双连通分量

边双连通图:如果一个无向连通图G没有割边,或者说边连通度λ(G)>1,则称G为边双连通图。

为什么称为边双连通图呢?因为在这种图中任何一对顶点之间至少存在两条无公共边的路径(允许有公共内部顶点),在删去某条边后,也不会破坏图的连通性。例如,图5(a)中,顶点v8和v4之间存在两条无公共边的路径:(v8,v5,v6,v3,v4)和(v8,v9,v6,v7,v4),这两条路径有一个公共内部顶点(当然这两个顶点之间还存在其他路径)。

边双连通分量:一个连通图G如果不是边双连通图,那么它可以包括几个边双连通分量。一个连通图的边双连通分量是该图的极大重连通子图,在边双连通分量中不存在割边。在连通图中,把割边删除,则连通图变成了多个连通分量,每个连通分量就是一个边双连通分量。例如,图6(a)所示的连通无向图存在两条割边,(4,10)和(6,10),把这两条割边删除后,得到3个边双连通分量,如图6(b)所示。

无向图顶点连通性和边连通性的联系

顶点连通度和边连通度的联系

关于图的顶点连通度和边连通度,有如下定理。

定理1(顶点连通度、边连通度与图的最小度的关系) 设G为无向连通图,则存在关系式:

割边和割点的联系

仔细观察图4(a)和6(a)中的割边和割点,两者之间有紧密的联系。具体可以用下面的定理来描述。

定理2(割边和割点的联系) 设v是图G中与一条割边相关联的顶点,则v是G的割点当且仅当deg(v)≥2。

有向图的连通性

由于有向图的边具有方向性,所以有向图的连通性比较复杂。根据有向图连通性的强弱可分为强连通、单连通和弱连通。

强连通(Strongly Connected):若G是有向图,如果对图G中任意两个顶点u和v,既存在从u到v的路径,也存在从v到u的路径,则称该有向图为强连通有向图。对于非强连通图,其极大强连通子图称为其强连通分量。

单连通(Simply Connected):若G是有向图,如果对图G中任意两个顶点u和v,存在从u到v的路径或从v到u的路径,则称该有向图为单连通有向图。

弱连通(Weak Connected):若G是有向图,如果忽略图G中每条有向边的方向,得到的无向图(即有向图的基图)连通,则称该有向图为弱连通有向图。

强连通图一定也是单连通图和弱连通图,单连通图一定也是弱连通图。例如,图7(a)所示的连通图G1是强连通图,任何一对顶点间都存在双向的路径。图7(b)所示的有向图G2是单连通图,任何一对顶点间至少存在一个方向上的路径。图7(c)所示的有向图G3是弱连通图,基图连通,但顶点6和5之间不存在有向路径。

参考文档