数据结构与算法_连通图

1.连通图和连通分量

连通图：无向图中，如果顶点vi到vj有路径，则称vi和vj是连通的。如果图中任何两个顶点都是连通的，则称G为连通图。如下图

    连通分量：无向图G的极大连通子图称为G的连通分量。极大连通子图的意思是：该子图是     G的连通子图，如果再加入一个顶点，该子图不连通。

    对于连通图，则其连通分量就是它自己，对于非连通图，则有两个以上连通分量。

2.强连通图和强连通分量

强连通图：有向图中，如果图中任何两个顶点vi到vj有路径，且vi到vj也有路径，则称G为强连通图。

强连通分量：有向图G的极大连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，如果再加一个顶点，该子图不再是强连通的。

如下图所示，（a）是强连通图，（b）不是强连通图，（c）是（b)的强连通分量。

3.无向图的桥与割点

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

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

    在日常网络中，有很多路由器使网络连通，有的路由器坏掉也无伤大雅，网络仍然连通，但是非常关键结点的路由器坏了，网络将不再连通。如图所示，如果5号结点的路由器坏了，图G不再连通，分裂成3个不相连的子图，5号结点为图G的割点。

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

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

割点与桥的关系：

1）有割点不一定有桥，有桥一定存在割点。

2）桥一定是割点依附的边。

4.无向图的双连通分量

5.双连通分量的缩点

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

    例如,如图所示，图中有两个桥，5-7,5-8，每个桥的边保留，桥两端的边双连通分量缩为一个点，这样生成一个树。

    如图所示，图G的点双连通分量有4个：

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