图的连通性基础

一 无向图的连通性

在无向图中，如果从节点 vi 到节点 vj 有路径，则称节点 vi 和节点 vj 是连通的。如果图中任意两个节点都是连通的，则称图为连通图。下图就是一个连通图。

无向图G的极大连通子图成为图G的连通分量。极大连通子图是图G连通子图，如果再向其中加入一个节点，则该子图不连通。连通图的连通分量就是它本身；非连通图则有两个以上的连通分量。

例如，下图有3个连通分量

二 有向图的连通性

在有向图中，如果图中任意两个节点从 vi 到 vj 都有路径，且从 vj 到 vi 也有路径，则称图 G 为强连通图。

有向图 G 的极大连通子图被称为 G 的强连通分量。极大强连通子图是图 G 的强连通子图，如果再向图中加入一个节点，则该子图不再是强连通的、

下图中，a 图是强连通图，b 不是强连通图，c 是 b 的强连通分量。

三 无向图的桥和割点

桥是连接河两岸的交通要道，桥断了，则河两岸不再连通。在图中，桥也有同样的含义，如下图所示，去掉 5-8 后，图分裂为两个互不连通的子图，边 5-8 为图 G 的桥，同样，边 5-7 也为图 G 的桥。

如果去掉无向连通图 G 中的一条边 e 后，图 G 分裂为两个互不相连的子图，那么 e 为图 G 的桥或割边。

在日常网络中有很多路由器使网络连通，有的路由器坏了也无关紧要，网络仍然连通，但若非常关键的路由器坏了，则网络将不再连通。如下图中，如果节点 5 的路由器坏了，图 G 将不再连通，会分裂为 3 个互不相连的子图，则节点 5 称为图 G 的割点。

如果去掉无向连通图 G 中的一个点 v 及与 v 关联的所有边后，图 G 分裂为两个或两个以上不相连的子图，那么 v 为图 G 的割点。

注意：删除边时，只把边删除即可，不要删除与边关联的点；而删除割点时，要删除该点及其关联的所有边。

割点与桥的关系：有割点不一定有桥，有桥一定有割点，桥一定是割点依附的边。

四 无向图的双连通分量

如果在无向图中不存在桥，则称它为边双连通图。在边双连通图中，在任意两个点之间都存在两条及以上路径，且路径上的边互不重复。

如果在无向图中不存在割点，则称它为点双连通图。在点双连通图中，如果节点数大于2，则在任意两个点间都存在两条或以上的路径，且路径上的点互不重复。

无向图的极大双连通子图被称为边双连通分量。无向图的极大点双连通子图称为点双连通。两者被统称为双连通分量。

五 双连通分量的缩点

把每一个边双连通分量都看作一个点，把桥看作连接两个缩点的无向边，可得到一棵树，这种方法被称为 e-DCC 缩点。

例如，在下图中有两个桥：5-7 和 5-8，将每个桥的边都保留，将每个桥的边都保留，将桥两端的边双连通分量缩为一个点，生成一棵树。

注意：边双连通分量是删除桥之后留下的连通块，但点双连通分量并不是删除割点后留下的连通块。

在图 G 中有两个割点（5和8）及4个点连通分量，如下图所示。

把每一个点双连通分量 v-DCC 都看作一个点，把割点看作是一个点，每个割点都包含它的 v-DCC连接一条边，得到一棵树，这种方法被称为 v-DCC 缩点。

例如，在图 G 中有两个割点 5 和 8，前 3 个点双连通分量都包含 5，因此从 5 向它们引一条边，后两个点双连通分量都包含 8，因此从 8 向它们引一条边。