标题党,之前我也写过一篇比较全的,但是对于初学者不友好。传送门?
双连通分量(Biconnected component):
1.边双联通 E-BCC
2.点双连通 V-BCC
双连通分量分为点双连通(V-BCC)和边双连通(E-BCC),这是图论学习中一个很重要的知识点,也是图的变形转化的一个主要方法。通过V-BCC缩点可以求割边(桥),也可以通过E-BCC缩点求割点。这是我们今天讲的主要的内容。
1.边双连通分量
先说不好理解的定义:若一个无向图的点两两间都有两条不重合的路径,那么我们就称这个无向图是边-双连通的。
我们看看这个定义又是什么意思,任意两点都有两条不重合的路径,就是说任意点都有两条边可以到达,那么任意去掉一条边,肯定还有另一条边连接,也就是说这个图中不存在割边。所以这个图是边双连通图。
我们画个图来理解:
这下来大家应该明白什么边双连通了,接下来讲边双连通分量(分支) 。
所谓分支就是一个子图,那么边双连通分支就是说原图中最大的一个双连通分支的子图。一定是最大不然会影响结果。比较好理解,直接上图。
这个图有两个双连通分量, 边双连通分量,就是这么多内容。我们再讲讲边双连通分量缩点。
如果将双连通分支用一个点表示,那么就叫做E-DCC缩点。经过缩点后建的图必然不存双连通分量,图中存在的边都不在双连通分支中,也就是说缩点后的边都是桥。
2.点双连通分支
定义:任意两条边都在一个简单环中。
就是说没有割点。还是画图吧!
这两个最大连通子图就是点双联通分支,类比边双连通分支。
也就是说经过缩点后的图中的点除了只有一条边的的点都是割点。
我们下一期讲Tarjan算法求双连通分量。