基本信息
文件名称：图论连通性分析与关键点边判定方法.pdf
文件大小：698.28 KB
总页数：14 页
更新时间：2025-09-12
总字数：约1.63万字
文档摘要
7.23——知识总结
图论——连通性
有向图的连通性
讲图的连通性前，我们需要介绍几个定义：
①如果去掉一边使该图不连通，那么称这种边为关键边，也称为“桥”；去掉关键边的
操作称之为关键边割。
②如果去掉一点使该图不连通，那么称这种节点为关键点；去掉关键点的操作称之为关
键点割。
让我们先讲讲无向图的连通性的问题。如上所知，一个无向图中有一定数量的关键点和关
键边，那么我们有什么方法去找到图中所有的关键点和关键边呢？我们最快想到的方法就是
枚举，每次删除一条边或一个点，然后在用一个bfs遍历整个图，看看是不是整个图都被遍
历到