首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >无向图双连通分量BCC(全网最好理解)

无向图双连通分量BCC(全网最好理解)

作者头像
风骨散人Chiam
发布2020-10-28 11:26:01
2K0
发布2020-10-28 11:26:01
举报
文章被收录于专栏:CSDN旧文CSDN旧文

不是标题党,之前我也写过一篇比较全的,但是对于初学者不友好。传送门?

双连通分量(Biconnected component):

    1.边双联通 E-BCC

    2.点双连通 V-BCC

双连通分量分为点双连通(V-BCC)和边双连通(E-BCC),这是图论学习中一个很重要的知识点,也是图的变形转化的一个主要方法。通过V-BCC缩点可以求割边(桥),也可以通过E-BCC缩点求割点。这是我们今天讲的主要的内容。

1.边双连通分量

先说不好理解的定义:若一个无向图的点两两间都有两条不重合的路径,那么我们就称这个无向图是边-双连通的。

我们看看这个定义又是什么意思,任意两点都有两条不重合的路径,就是说任意点都有两条边可以到达,那么任意去掉一条边,肯定还有另一条边连接,也就是说这个图中不存在割边。所以这个图是边双连通图。

我们画个图来理解:

 这下来大家应该明白什么边双连通了,接下来讲边双连通分量(分支) 。

所谓分支就是一个子图,那么边双连通分支就是说原图中最大的一个双连通分支的子图。一定是最大不然会影响结果。比较好理解,直接上图。

这个图有两个双连通分量, 边双连通分量,就是这么多内容。我们再讲讲边双连通分量缩点。

如果将双连通分支用一个点表示,那么就叫做E-DCC缩点。经过缩点后建的图必然不存双连通分量,图中存在的边都不在双连通分支中,也就是说缩点后的边都是桥。

2.点双连通分支

定义:任意两条边都在一个简单环中。

就是说没有割点。还是画图吧!

 这两个最大连通子图就是点双联通分支,类比边双连通分支。

也就是说经过缩点后的图中的点除了只有一条边的的点都是割点。

我们下一期讲Tarjan算法求双连通分量。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-10-19 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档