Tagged

Algorithm

A collection of 3 posts

Algorithm

算法:无向图的割点、桥与双连通分量

概念 对于无向图\(G\),删除顶点\(v\)和其相连的边后\(G\)所包含的连通分量增多,则称\(v\)为关节点 (articulation point) 或割点 (cut point)。同理,删除边\(e\)和其相连的顶点后图包含的连通分量增多,则\(e\)是割边 (cut edge) 或桥 (bridge)。 割点形式化的定义:\(A\)是割点当且仅当存在两个点\(u,v\),使得\(u\)到\(v\)的每条路径都会经过\(A\)(去掉\(A\)后,\(u\)到\(v\)没有路径)。 不含任何割点的图称为双连通图。任一无向图都可视作若干个极大双连通子图组合而成,每一个子图称为双连通分量 (bi-connected component)