GitHub同步更新（已分类）：Data_Structure_And_Algorithm-Review
公众号：URLeisure 的复习仓库
公众号二维码见文末
以下是本篇文章正文内容，下面案例可供参考。
一、无向图的连通分量
-
无向图中，如果从节点 Vi 到节点 Vj 有路径，则称节点 Vi 和节点 Vj 是连通的。
-
如果图中任意两个节点都是连通的，则图 G 为
连通图。如图。
连通性的相关知识
-
极大连通子图是图 G 的连通子图，如果再向其中加入一个节点，则该子图不连通； -
无向图 G 的极大连通子图被称为图 G 的
连通分量； -
连通图的连通分量就是它本身；
-
非连通图则有两个以上的连通分量，如下图。
二、有向图的强连通分量
-
在有向图中，如果图中的任意两个节点， Vi 到 Vj 有路径，Vj 到 Vi 也有路径，则称图 G 为
强连通图。 -
有向图 G 的极大连通子图被称为图 G 的强连通分量。 -
如下图。（a）是强连通图，（b）不是强连通图，（c）是（b）的强连通分量。
三、无向图的桥
-
桥，架在水上或空中以便通行的建筑物。如果桥断了，两岸则不再连通。
-
图论中，如果在去掉无向连通图 G 中的一条边 e 后，图 G 分裂为两个不相连子图，那么 e 为图 G 的
桥或割边。 -
如图。
去掉边 2-4 或 2-7 后，将形成两个不相连的子图。所以 2-4 和 2-7 为图 G 的 桥或割边。
四、无向图的割点
-
网络中有很多路由器使网络连通，如果关键节点的路由器坏了，将导致网络不再连通。
-
如果在去掉无向连通图 G 中的一个点 v 及与 v 关联的所有边后，图 G 分裂为两个或两个以上不相连的子图，那么 v 为图 G 的
割点。 -
如图。
连通图去掉节点 V2 或 V7 后将形成几个不相连的子图。则 V2 和 V7 都为图 G 的 割点。
五、无向图的割点和桥的关系
- 有割点不一定有桥，有桥一定有割点；
- 桥一定是割点依附的边。
六、无向图的双连通分量
-
无向连通图中不存在桥，则称它为
边双连通（至少有两条路径）图。 -
在边双连通图中，任意两个点之间都存在两条及以上路径，且路径上的边互不重复。
-
无向连通图中不存在割点，则称它为
点双连通（至少有两条路径）图。 -
在点双连通图中，如果节点数大于 2，则任意两个点间都存在两条或以上路径，且路径上的点互不重复。
-
无向图的极大边双连通子图被称为
边双连通分量，记为e-DCC。无向图的极大点双连通子图被称为点双连通分量，记为v-DCC。 -
二者统称为
双连通分量 DCC。
1.边双连通分量缩点（e-DCC 缩点）
-
把每一个边双连通分量 e-DCC 都看作一个点，把桥看作连接两个缩点的无向边，就得到一棵树，这种方法被称为e-DCC 缩点。 -
如图。
图中有两个桥 2-4 和 2-7 ，保留作为边，桥两端的边双连通分量缩为一个点，生成一棵树。
2.点双连通分量缩点（v-DCC 缩点）
-
把每一个点双连通分量 v-DCC 都看作一个点，把割点看作一个点，每个割点都向包含它的 v-DCC 连接一条边，就得到一棵树，这种方法被称为v-DCC 缩点。 -
如图。
先找出图 G 所有的双连通分量，再按照定义，构成一棵树。
关注公众号，感受不同的阅读体验
文章来源：https://www.toymoban.com/news/detail-434698.html
下期预告：图的连通性_Tarjan算法文章来源地址https://www.toymoban.com/news/detail-434698.html
到了这里，关于【数据结构】图-图的连通性（图解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
