当前位置: 首页 > news >正文

无向图的结合点

定义:图G(V,E)是连通图,顶点集S是V的子集,若删除S中的所有顶点,将是图不连通,称S是图G的割集。若S={v},则称v为图G的割点(或结合点)。

如果一个无向图没有结合点,该图称为双连通图

 

结合点的性质:

性质1: 当且仅当深度优先搜索树的根结点至少有两个以上儿子,则根结点是结合点。

性质2: 当且仅当深度优先搜索树中,v的每以一个儿孙结点不能通过后向边到达v结点的祖先结点,则结点v是结合点

 

在进行遍历时,有向图的边,可以分为:

   树边:深度优先搜索生成树中的边;

   后向边: 与边(u, v)相关联的顶点u和v,在深度优先搜索树中,v是u的祖先,在从(u, v)出发进行搜索时,v已被标记过为访问过的结点;

 

求结合点的方法:

对每个顶点v,设立变量pren[v]和backn[v],pren[v]是顶点v的遍历序号,backn[v]是顶点v的后向可达顶点的最小遍历序号;

初始时,backn[v] = pren[v];

若[v,w]是从顶点v出发进行搜索的边,则backn[v]是下列数值中最小者

* pren[v]

* pren[w],若(v,w)是后向边

* backn[w],若(v, w)是树边

 

只要顶点v有一个儿子w,使得backn[w]>=pren[v],则说明v的儿孙w不能通过后向边达到v的祖先,因此v是接合点。

 

算法流程:

从v顶点开始搜索:

(1)把v标记为访问过,初始化pren[v],backn[v],使得指针p指向v的邻接表;

(2)若p为空,处理搜索到的接合点的计数,算法结束;否则,令p指向的邻接点是w;若(v, w)是树边,执行步骤3),否则执行5)

(3)从w出发递归调用深度优先搜索算法,若v是根结点,按照性质1判定v是否为接合点,否则更新v的后向可达顶点的遍历序号,按性质2判定v是否为接合点;

(4)使得p指向下一个邻接点,转步骤2)

(5)若(v, w)是后向边,更新v的后向可达顶点顶点的遍历序号,转步骤4)

 

 

转载于:https://www.cnblogs.com/KennyRom/p/6142365.html

相关文章:

  • CSDN上的文章好像是hBifts的嘛。怎么连作者名字都不提一下。过份!
  • Yii2.0 API实例
  • 关于Whidbey的东西
  • AFURLRequestSerialization
  • top命令简介
  • 竟然发现在windows2003下的搜索工具不能搜索asp文件中的select文字
  • Android高级之十二讲之内存、电量、卡顿、流量
  • 邮件
  • Linux系统环境变量
  • 事务处理行为
  • LeetCode - Linked List Cycle I II
  • Google实用技巧
  • NOIP2001 一元三次方程求解[导数+牛顿迭代法]
  • InnoDB与MyISAM的区别
  • Windows XP sp2全攻略
  • [微信小程序] 使用ES6特性Class后出现编译异常
  • 【RocksDB】TransactionDB源码分析
  • 【干货分享】SpringCloud微服务架构分布式组件如何共享session对象
  • Akka系列(七):Actor持久化之Akka persistence
  •  D - 粉碎叛乱F - 其他起义
  • IP路由与转发
  • JS数组方法汇总
  • Odoo domain写法及运用
  • Python实现BT种子转化为磁力链接【实战】
  • Spark in action on Kubernetes - Playground搭建与架构浅析
  • spring + angular 实现导出excel
  • Spring框架之我见(三)——IOC、AOP
  • STAR法则
  • vagrant 添加本地 box 安装 laravel homestead
  • vue和cordova项目整合打包,并实现vue调用android的相机的demo
  • yii2权限控制rbac之rule详细讲解
  • 安卓应用性能调试和优化经验分享
  • 大数据与云计算学习:数据分析(二)
  • 基于Vue2全家桶的移动端AppDEMO实现
  • 前端临床手札——文件上传
  • 前嗅ForeSpider教程:创建模板
  • 前嗅ForeSpider中数据浏览界面介绍
  • 腾讯优测优分享 | Android碎片化问题小结——关于闪光灯的那些事儿
  • 想使用 MongoDB ,你应该了解这8个方面!
  • 新书推荐|Windows黑客编程技术详解
  • 转载:[译] 内容加速黑科技趣谈
  • kubernetes资源对象--ingress
  • mysql 慢查询分析工具:pt-query-digest 在mac 上的安装使用 ...
  • 容器镜像
  • 支付宝花15年解决的这个问题,顶得上做出十个支付宝 ...
  • ​低代码平台的核心价值与优势
  • #if #elif #endif
  • #QT(串口助手-界面)
  • (C语言)strcpy与strcpy详解,与模拟实现
  • (Python) SOAP Web Service (HTTP POST)
  • (附源码)springboot人体健康检测微信小程序 毕业设计 012142
  • (六)vue-router+UI组件库
  • (南京观海微电子)——COF介绍
  • (转)memcache、redis缓存
  • ./configure,make,make install的作用