图论基础概念
2026-03-10
前言
这里主要用于记载一些图论基础概念(放在一起方便看)。
连通性定义
强连通分量 在一张有向图中,联通分量定义为有一个节点 u 和其他节点 v 构成的,能够从 u 到 v 也能够从 v 到 u 的连通块。
强连通分量则是极大联通分量,也就是其中最大的那个。
在 DFS 时,找到的一个没搜索过的点与搜过的点的边成为树边,一个节点 u 到其父亲的边叫做返祖边,u 到之前搜过的,不为其父节点的点的连边称为横插边,u 到其子树中一个节点的边叫做前向边。
双连通分量 在无向图中,由于每个点一定是双连通的,所以在有向图中的定义不起作用,需要一些新的定义。
桥:如果一张联通的无向图中的一条边被删除后会导致原图变成两部分,则称这条边叫作桥。
割点:如果一张联通的无向图中的一个点被删除后导致原图变成两部分,则称这个点为割点。
相似的,我们定义边双连通分量(E-DCC)表示不包含桥的最大联通块;点双连通分量(V-DCC)表示不包含割点的最大联通块。
由于它的特殊性,割点一定是至少两个边双连通分量的一部分。
注意
割点和桥并没有紧密的联系,如:两个割点中间的边不一定是桥,因为有可能有别的边连接两边;同样的,一个桥的两边也不一定是割点。
