2.4 图的连通性
一个非空图G=（V，E）的任何两个点在G中都被一条路相连，则称这个非空图是连通的。图G的一个极大连通子图称为G的一个连通分支，G的连通分支的个数记为ω（G）。G的含有奇数个顶点的连通分支称为奇分支。用O（G）表示G的奇分支的个数。图2-8展示了连通的图和不连通的图。
图2-8 一个连通图和一个有三个分支的不连通图
定义2-1 图G的顶点v称为割点，如果E可以分为两个非空子集E1和E2，使得G[E1]和G[E2]恰好有公共顶点v。若G无环且非平凡，则当且仅当ω（G-v）>ω（G）时，v是G的割点。图2-9中的5个实点即为割点。
图2-9 一个图的割点
定义2-2 没有割点的连通图称为块。
一个图的块是指该图的一个子图，这个子图本身就是块，而且是有此性质的块中的极大者。每个图都是它的块的并图，这在图2-10中作了解释。
图2-10 图G及图G的块
定义2-3 对图G，若V（G）的子集V'使得ω（G-V'）>ω（G），则称V'为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。
定义2-4 设e∈E（G），如果ω（G-e）>ω（G），则称e为G的一条割边。
图2-11中给出的图中指出了三条割边，即三条加粗边。
图2-11 图的割边
定理2-1 边e是G的一条割边当且仅当e不包含在G的任一圈中。
定义2-5 对图G，若E（G）的子集E'使得ω（G-E'）>ω（G），则称E'为图G的一个边割集。含有k条边的边割集称为k-边割集。
上面引进了图的连通概念，现在来考察图2-12的四个连通图。
图2-12 四个连通图
G1是最小连通图，删去任何一条边都将使它不连通。G2不会因单单删去一条边而不连通，但删去它的割点就能使它不连通。G3中既无割边也无割点，但G3显然不如五个顶点的完全图G4连通得那么好。因此直观看来，每个后面的图比其前面的图连通程度更强些。下面定义一种参数来度量连通图连通程度的高低。
定义2-6 如果|V|>k，并且对于任何的X⊆V都有G-X是连通的，其中|X|<k，则称G是k-连通的。同理，如果|V|>1，并且对于任何少于l条边的集合F⊆E都有G-F是连通的，则称G是l-边连通的。
在网络科学研究中，鲁棒性是一个重要的课题。对于一个给定的网络，从该网络中移走一些节点，有可能使得网络中其他节点之间的路径中断。如果节点i和j之间的所有路径都被中断，那么两个节点之间就不再连通了。如果在移走少量节点后网络中的绝大部分节点仍是连通的，那么就称该网络的连通性对节点故障具有鲁棒性。由上面的定义知道，如果一个网络是k-连通的，那么移走少于k个点后该网络仍是连通的。例如，图2-13是2-连通的。
图2-13 一个2-连通图
定理2-2 （Menger定理）图G是k-连通的充分必要条件是G中任何两个顶点之间都有k条两两内部顶点不交的路。图G是k-边连通的充分必要条件是G中任何两个顶点之间都有k条两两边不交的路。
基于Menger定理，为了计算使得网络不连通所需去掉的最少顶点数，只需求出网络中任意两个顶点之间所有的简单路径，然后求出包含路径个数的最小值，而对于这个问题存在一个经典的有效算法——Dijkstra算法。
有向图的连通性
上面关于无向图连通性的介绍都可以推广到有向图的情形。有向图的连通性是指在有向图中的一条从顶点v1到顶点vk的路径P=v1v2…vk，任意两个相邻的顶点vi和vi+1之间都有一条从vi指向vi+1的边（vi，vi+1）。由此定义可以看出，在有向图中若存在一条从顶点vi到顶点vj的路径，并不意味着一定存在一条从顶点vj到顶点vi的路径。
如果对任意顶点对u和v，既存在从顶点u到顶点v的路径，也存在从顶点v到顶点u的路径，则该有向图称为是强连通的。如果有向图不满足强连通条件，但是如果把图中所有的有向边都看作是无向边后所得到的无向图是连通的，则该有向图称为是弱连通的。在弱连通图中若存在一个子集满足:该子集中任意一组顶点对之间都有相互到达的路径存在，即该子集是强连通的，那么称最大的连通子集为该有向图的强连通分支。对任意有向图，最大的弱连通子集称为弱连通分支。