1.9 连通性

手机作为一种通信设备，如果不能呼叫任何有效的手机号码，其用途就非常有限了；电子邮箱如果只能给少数几个邮件地址发邮件，也就没有多大用处了。从网络的角度看，这意味着手机或互联网背后的网络必须能够在任意两个节点之间建立一条路径。实际上，这是大多数网络的关键效用——确保连通性。本节我们将从图论的角度探讨连通性。

无向网络中，如果节点i和节点j之间存在一条路径，则它们是连通的。如果不存在路径（dij=∞），则它们是不连通的。图1-15a所示的网络包含两个互不连通的簇。同一个簇中的任意两个节点（例如节点4和节点6）之间存在路径，不同簇的节点（例如节点1和节点6）之间没有路径。

如果一个网络的所有节点对都是连通的，我们说该网络是连通的。如果网络中至少有一对节点是不连通的，则该网络是不连通的。很明显，图1-15a所示的网络是不连通的，我们把互不连通的两个子网络称为连通分支或簇。一个连通分支是网络节点的子集，该子集满足“任意两个节点之间存在路径”的性质，且在不破坏该性质的前提下无法再增加任何节点。

如果网络中包含两个连通分支，只需要选择合适的位置放置一个链接，就能使网络变成连通的（图1-15b）。这样的链接被称为桥。一般而言，桥是指断开之后网络就不再保持连通的链接。

对于小网络而言，目测就可以帮助我们判断其是否是连通的。对于有数百万个节点的网络而言，判断其连通性则是一个有挑战性的问题。不过，数学工具和计算机算法可以帮助我们找出网络中的连通分支。例如，对于不连通的网络，其邻接矩阵可以通过重排的方式变成分块对角阵的形式——所有非零元素形成沿对角线排列的方块（图1-15a）。每一个方块对应着一个连通分支。我们可以使用线性代数工具来判定邻接矩阵是否是分块对角阵，从而找出网络的连通分支。

图1-15 连通网络和不连通网络

（a）包含两个连通分支的小网络。实际上，第一个连通分支（1,2,3）中的任意节点对之间都存在路径，第二个连通分支（4,5,6,7）也一样。然而，不同连通分支的节点之间不存在路径。

图的右边部分是该网络的邻接矩阵。如果网络是不连通的，则邻接矩阵可以通过重排变成一个分块对角阵——所有非零元素形成沿对角线排列的方块。

（b）增加一个链接（灰色）使网络从不连通变成连通的，这样的链接通常被称为桥。添加该链接之后，网络中每一对节点之间都存在路径了。因此，其邻接矩阵不能写成分块对角阵的形式了。

实际上，对于大网络而言，找出其连通分支的更高效的方法是BFS算法（边栏1.6）。