图的连通性

引入

联通分量

在无向图中,可达关系满足自反性,对称性和传递性,是一个等价关系
从等价关系可以定义等价类,把相互可达的节点称为一个联通分量

无向图

割点和桥

如果删除某个点$x$后,$G$的联通分量数目增加,称$x$为图的割点
如果删除某条边$E$后,$G$的联通分量数目增加,称$E$为图的桥

$x$为割点的条件
$x$是dfs树的根,且x有两个及以上子节点
$x$非根,且$x$存在子节点$v$,满足$low[v]\geq dfn[x]$

$E=(u,v)$为桥的条件
$E$不存在重边
满足$low[v]> dfn[x]$

点双联通分量

若$G$中无割点,称$G$为点双连通图。$G$中任意两点间存在至少两条不经过重复点的路径
若$G$中无桥,称$G$为边双连通图。$G$中任意两点间存在至少两条不经过重复边的路径
除了桥外,每条边恰好属于一个边双联通分量,但不同点双联通分量可能会有公共点,可以证明公共点最多只有一个且为割点

有向图

强连通分量

若$G$中任意两点可达,称$G$为强连通图
对$SCC$缩点后原图变为$DAG$

分享到: