DeTechn Blog

双连通图和关节点

若从一个连通图中删去任何一个顶点及其相关联的边,它仍为一个连通图的话,则该连通图被称为重(双)连通图。

若连通图中的某个顶点和其相关联的边被删去之后,该连通图被分割成两个或两个以上的连通分量,则称此顶点为关节点。

没有关节点的连通图为双连通图

若生成树的根结点,有两个或两个以上的分支,则此顶点(生成树的根)必为关节点;
对生成树上的任意一个非叶“顶点”,若其某棵子树中的所有“顶点”没有和其祖先相通的回边,则该“顶点”必为关节点。

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »