博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
点双连通分量与割点
阅读量:5819 次
发布时间:2019-06-18

本文共 668 字,大约阅读时间需要 2 分钟。

前言

在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量

双连通分量一般是指点双连通分量

当然,还有一种叫做边双连通分量

点双连通分量

对于一个连通图,如果任意两点至少存在两条“点不重复”的路径,则说图是点双连通的(即任意两条边都在一个简单环中),点双连通的极大子图称为点双连通分量。

计算方法比较简单

在tarjan的过程中,如果由\(i\) dfs到\(j\),并且\(low[j]>=dfn[i]\),那么进行弹栈直到\(j\)被弹出,弹出的点加上\(i\)构成了一个点双连通分量。

(实际就是在搜索树种这个点和它下面的点构成了一个双连通分量)

注意在tarjan的过程中,我们可以选择存边,也可以存点,不过存点的话边界条件要变一下

do{    h=s.top();s.pop();    #¥%……&*(()}while(h!=edge[i].v);//warning

与二分图的关系

(1) 如果一个点双连通分量内的某些顶点在一个奇圈中(即双连通分量含有奇圈),那么这个双连通分量的其他顶点也在某个奇圈中;

(2) 如果一个点双连通分量含有奇圈,则他必定不是一个二分图。反过来也成立,这是一个充要条件。

例题

割点(割顶)

割点:对于无向图中的点\(i\),若去掉\(i\)点,无向图的连通快个数会增加,则称点\(i\)为割点

不难发现一个点是割点当且仅当他在多个点双里。

考虑之前求点双的过程,找到一个点双时,那个\(i\)就是一个割点。

根节点需要特判一下,必须要有至少\(2\)个孩子时才是割点。

例题

转载地址:http://liwdx.baihongyu.com/

你可能感兴趣的文章
《Linux内核修炼之道》 之 高效学习Linux内核
查看>>
DevOps 前世今生 | mPaaS 线上直播 CodeHub #1 回顾
查看>>
iOS 解决UITabelView刷新闪动
查看>>
让前端小姐姐愉快地开发表单
查看>>
Web前端JQuery入门实战案例
查看>>
CentOS 7 装vim遇到的问题和解决方法
查看>>
JavaScript基础教程1-20160612
查看>>
iOS \U7ea2 乱码 转换
查看>>
FCN图像分割
查看>>
ios xmpp demo
查看>>
python matplotlib 中文显示参数设置
查看>>
数据库事务隔离级别
查看>>
【ros】Create a ROS package:package dependencies报错
查看>>
kali linux 更新问题
查看>>
HDU1576 A/B【扩展欧几里得算法】
查看>>
廖雪峰javascript教程学习记录
查看>>
WebApi系列~目录
查看>>
Java访问文件夹中文件的递归遍历代码Demo
查看>>
项目笔记:测试类的编写
查看>>
通过容器编排和服务网格来改进Java微服务的可测性
查看>>