什么是连通度介绍

连通图G的连通程度通常叫做连通度(Connectivity)。连通度有两种，一种是点连通度，另一种是边连通度。通常一个图的连通度越好，它所代表的网络越稳定。

连通度基本概念

连通度知识储备

如果在图G中删去一个结点x后，图G的连通分支数增加，即

，则称结点x为G的割点(cut vertex)。如果在图G中删去一条边e后，图G的连通分支数增加，即

，则称e为G的割边(cut edge)或桥。

没有割点的非平凡连通图称为块( block)。G中不含割点的极大连通子图称为图G的块。

若H是图G的块，则H自身不含割点且满足：若向H中再添加边，但不添加结点，那么H就不是G的子图了；若向H中再增加结点或边将H扩大为更大的连通图，那么H就会含有割点。

例如，图1所示图G的块如图2所示。

如果图G的顶点集的一个真子集T满足G-T不连通或是平凡图，则称T为G的一个点割( vertex cut)。如果图G的边集的一个真子集S满足G-S不连通或是平凡图，则称S为G的一个边割(edge cut)。

连通度定义

设G是连通图，称

为G的点连通度( vertex connectivity)或连通度；称

为G的边连通度(edge conncctivity)。

连通度相关定理

连通度定理1

对一个图G，有

。其中

是图G的最小顶点度。

证明 若G不连通，则

．故上式成立。若G连通，则：

(1)先证

。

设x是G中度数最小的顶点，即

，设所有与x关联的边集为S (x)，显然x是图G-S(x)的一个孤立结点。于是

。

(2)再证

。

当

时，显然有

。

假设对所有

的图G，有

。再设

，S是H的一个边割，且

。若边

，易知

，故由假设知

，并设T是

的一个点割，且

。而此时

就是H的一个点割，即

由归纳法原理知

。证毕。

连通度定理2

定义如果无向图G的连通度

，则称图G是n连通的或G为n连通图。若

，则称图G是n边连通的或G为n边连通图。

设图G是n连通的，

，则

。

证明 假设G有一个顶点y且

，即y与n一1条边关联。设与y关联的n一1个顶点构成的集合为S，显然S是G的一个点割。因而

。这与

矛盾。

连通度定理3

若G是2边连通图，则G有强连通的定向图。

证明 设G是2边连通图，则G必含有圈。先取一个圈

，归纳地定义G的连通子图序列

如下：

；若

不是G的生成子图，设

是在G中而不在

中的一个顶点，则存在从

到

的边的不重路

和

，定义

，由于

，这个序列必然终止于G的一个生成子图

。现依次给每个

定向：首先让

的定向图

成为一个有向圈；对

，设已有定向图

，让

成为以

为起点的有向路，而

成为以

为终点的有向路得

，易见

是强连通有向图

。因此最后的

是强连通有向图。由于

是G的生成子图，所以G有强连通的定向图。显然，一个图G有强连通的定向图的必要条件是G为2边连通的。否则G中有割边，这与G有强连通的定向图矛盾。证毕。